Skip to contentSkip to conversation

radix-tree: fix small lockless radix-tree bug

PATCH In review Nick Piggin 4 participants 7 messages Jun 12, 2008 – Jun 13, 2008 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 radix-tree: fix small lockless radix-tree bug

Hi guys,

Although this doesn't seem like cause for alarm (as per the analysis), it may still be a good 2.6.26 candidate as we should have a few more weeks of testing left.

It should definitely go in -mm with the lockless pagecache patch.

Thanks,
Nick

When shrinking a radix-tree, we do it in a lockless manner by atomically switching the root pointer away from the redundant node (one that only has a single entry in the left most slot), and switching it over to its lone child.

Because a lockless lookup may have got a reference to the parent and be in the middle of deciding what to do with it while it is being swapped away for its child. For this reason, we also have to keep it around and in a valid state for the lookup to proceed and give a valid result, for at least an RCU grace period. So we need to keep the child in the left most slot there in case that is requested by the lookup.

This is all pretty standard RCU stuff. It is worth repeating because in my eagerness to obey the radix tree node constructor scheme, I had broken this by zeroing the radix tree node before the grace period.

Fix it by clearing those fields in the RCU callback. I would normally want to rip out the constructor entirely, but radix tree nodes are one of those places where they make sense (only few cachelines will be touched soon after allocation).

This was never actually observed in any lockless pagecache testing or using the test harness, but as a rare problem testing my scalable vmap rewrite.

Fortunately, it is not a problem anywhere lockless pagecache is used in mainline kernels (pagecache probe is not a guarantee, and brd does not have concurrent lookups and deletes).

However, it would eventually pop up for someone using lockless pagecache :P

---

lib/radix-tree.c +62 -58
Index: linux-2.6/lib/radix-tree.c
===================================================================
@@ -88,6 +88,57 @@ static inline gfp_t root_gfp_mask(struct
 	return root->gfp_mask & __GFP_BITS_MASK;
 }
 
+static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
+		int offset)
+{
+	__set_bit(offset, node->tags[tag]);
+}
+
+static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
+		int offset)
+{
+	__clear_bit(offset, node->tags[tag]);
+}
+
+static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
+		int offset)
+{
+	return test_bit(offset, node->tags[tag]);
+}
+
+static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
+{
+	root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
+}
+
+static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
+{
+	root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
+}
+
+static inline void root_tag_clear_all(struct radix_tree_root *root)
+{
+	root->gfp_mask &= __GFP_BITS_MASK;
+}
+
+static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
+{
+	return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
+}
+
+/*
+ * Returns 1 if any slot in the node has this tag set.
+ * Otherwise returns 0.
+ */
+static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
+{
+	int idx;
+	for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
+		if (node->tags[tag][idx])
+			return 1;
+	}
+	return 0;
+}
 /*
  * This assumes that the caller has performed appropriate preallocation, and
  * that the caller has pinned this thread of control to the current CPU.
@@ -124,6 +175,17 @@ static void radix_tree_node_rcu_free(str
 {
 	struct radix_tree_node *node =
 			container_of(head, struct radix_tree_node, rcu_head);
+
+	/*
+	 * must only free zeroed nodes into the slab. radix_tree_shrink
+	 * can leave us with a non-NULL entry in the first slot, so clear
+	 * that here to make sure.
+	 */
+	tag_clear(node, 0, 0);
+	tag_clear(node, 1, 0);
+	node->slots[0] = NULL;
+	node->count = 0;
+
 	kmem_cache_free(radix_tree_node_cachep, node);
 }
 
@@ -165,59 +227,6 @@ out:
 }
 EXPORT_SYMBOL(radix_tree_preload);
 
-static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
-		int offset)
-{
-	__set_bit(offset, node->tags[tag]);
-}
-
-static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
-		int offset)
-{
-	__clear_bit(offset, node->tags[tag]);
-}
-
-static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
-		int offset)
-{
-	return test_bit(offset, node->tags[tag]);
-}
-
-static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
-{
-	root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
-}
-
-
-static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
-{
-	root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
-}
-
-static inline void root_tag_clear_all(struct radix_tree_root *root)
-{
-	root->gfp_mask &= __GFP_BITS_MASK;
-}
-
-static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
-{
-	return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
-}
-
-/*
- * Returns 1 if any slot in the node has this tag set.
- * Otherwise returns 0.
- */
-static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
-{
-	int idx;
-	for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
-		if (node->tags[tag][idx])
-			return 1;
-	}
-	return 0;
-}
-
 /*
  *	Return the maximum key which can be store into a
  *	radix tree with height HEIGHT.
@@ -930,11 +939,6 @@ static inline void radix_tree_shrink(str
 			newptr = radix_tree_ptr_to_indirect(newptr);
 		root->rnode = newptr;
 		root->height--;
-		/* must only free zeroed nodes into the slab */
-		tag_clear(to_free, 0, 0);
-		tag_clear(to_free, 1, 0);
-		to_free->slots[0] = NULL;
-		to_free->count = 0;
 		radix_tree_node_free(to_free);
 	}
 }
Acked-by on v1 1/1
#1 lore raw
Quoted 7 lines · Nick Piggin

Hi guys,

Although this doesn't seem like cause for alarm (as per the analysis), it may still be a good 2.6.26 candidate as we should have a few more weeks of testing left.

It should definitely go in -mm with the lockless pagecache patch.

Ouch - good one, I'll back-port it to -rt.

This reminds me, I should get back to my radix-tree path compression stuff one day.

Quoted 26 lines

When shrinking a radix-tree, we do it in a lockless manner by atomically switching the root pointer away from the redundant node (one that only has a single entry in the left most slot), and switching it over to its lone child.

Because a lockless lookup may have got a reference to the parent and be in the middle of deciding what to do with it while it is being swapped away for its child. For this reason, we also have to keep it around and in a valid state for the lookup to proceed and give a valid result, for at least an RCU grace period. So we need to keep the child in the left most slot there in case that is requested by the lookup.

This is all pretty standard RCU stuff. It is worth repeating because in my eagerness to obey the radix tree node constructor scheme, I had broken this by zeroing the radix tree node before the grace period.

Fix it by clearing those fields in the RCU callback. I would normally want to rip out the constructor entirely, but radix tree nodes are one of those places where they make sense (only few cachelines will be touched soon after allocation).

This was never actually observed in any lockless pagecache testing or using the test harness, but as a rare problem testing my scalable vmap rewrite.

Quoted 7 lines

Fortunately, it is not a problem anywhere lockless pagecache is used in mainline kernels (pagecache probe is not a guarantee, and brd does not have concurrent lookups and deletes).

However, it would eventually pop up for someone using lockless pagecache :P

Quoted 179 lines

---
Index: linux-2.6/lib/radix-tree.c
===================================================================
--- linux-2.6.orig/lib/radix-tree.c 2008-06-13 04:26:31.000000000
+1000
+++ linux-2.6/lib/radix-tree.c 2008-06-13 04:31:38.000000000 +1000

lib/radix-tree.c +19 -0
@@ -88,6 +88,57 @@ static inline gfp_t root_gfp_mask(struct
        return root->gfp_mask & __GFP_BITS_MASK;
 }
 
+static inline void tag_set(struct radix_tree_node *node, unsigned int
 tag,
+               int offset)
+{
+       __set_bit(offset, node->tags[tag]);
+}
+
+static inline void tag_clear(struct radix_tree_node *node, unsigned
 int tag,
+               int offset)
+{
+       __clear_bit(offset, node->tags[tag]);
+}
+
+static inline int tag_get(struct radix_tree_node *node, unsigned int
 tag,
+               int offset)
+{
+       return test_bit(offset, node->tags[tag]);
+}
+
+static inline void root_tag_set(struct radix_tree_root *root,

unsigned int tag)

(quoted diff) +2 -0
+{
+       root->gfp_mask |= (__force gfp_t)(1 << (tag +

__GFP_BITS_SHIFT));

lib/radix-tree.c +3 -0
+}
+
+static inline void root_tag_clear(struct radix_tree_root *root,

unsigned int tag)

(quoted diff) +2 -0
+{
+       root->gfp_mask &= (__force gfp_t)~(1 << (tag +

__GFP_BITS_SHIFT));

lib/radix-tree.c +8 -0
+}
+
+static inline void root_tag_clear_all(struct radix_tree_root *root)
+{
+       root->gfp_mask &= __GFP_BITS_MASK;
+}
+
+static inline int root_tag_get(struct radix_tree_root *root, unsigned

int tag)

(quoted diff) +2 -0
+{
+       return (__force unsigned)root->gfp_mask & (1 << (tag +

__GFP_BITS_SHIFT));

lib/radix-tree.c +7 -0
+}
+
+/*
+ * Returns 1 if any slot in the node has this tag set.
+ * Otherwise returns 0.
+ */
+static inline int any_tag_set(struct radix_tree_node *node, unsigned

int tag)

lib/radix-tree.c +8 -0
+{
+       int idx;
+       for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
+               if (node->tags[tag][idx])
+                       return 1;
+       }
+       return 0;
+}
 /*
  * This assumes that the caller has performed appropriate

preallocation, and
* that the caller has pinned this thread of control to the current
CPU.

lib/radix-tree.c +3 -0
@@ -124,6 +175,17 @@ static void radix_tree_node_rcu_free(str
 {
        struct radix_tree_node *node =
                        container_of(head, struct radix_tree_node,
 rcu_head);
+
+       /*
+        * must only free zeroed nodes into the slab.

radix_tree_shrink
+ * can leave us with a non-NULL entry in the first slot, so
clear

lib/radix-tree.c +7 -19
+        * that here to make sure.
+        */
+       tag_clear(node, 0, 0);
+       tag_clear(node, 1, 0);
+       node->slots[0] = NULL;
+       node->count = 0;
+
        kmem_cache_free(radix_tree_node_cachep, node);
 }
@@ -165,59 +227,6 @@ out:
 }
 EXPORT_SYMBOL(radix_tree_preload);
 
-static inline void tag_set(struct radix_tree_node *node, unsigned int
 tag,
-               int offset)
-{
-       __set_bit(offset, node->tags[tag]);
-}
-
-static inline void tag_clear(struct radix_tree_node *node, unsigned
 int tag,
-               int offset)
-{
-       __clear_bit(offset, node->tags[tag]);
-}
-
-static inline int tag_get(struct radix_tree_node *node, unsigned int
 tag,
-               int offset)
-{
-       return test_bit(offset, node->tags[tag]);
-}
-
-static inline void root_tag_set(struct radix_tree_root *root,

unsigned int tag)

(quoted diff) +0 -2
-{
-       root->gfp_mask |= (__force gfp_t)(1 << (tag +

__GFP_BITS_SHIFT));

lib/radix-tree.c +0 -4
-}
-
-
-static inline void root_tag_clear(struct radix_tree_root *root,

unsigned int tag)

(quoted diff) +0 -2
-{
-       root->gfp_mask &= (__force gfp_t)~(1 << (tag +

__GFP_BITS_SHIFT));

lib/radix-tree.c +0 -8
-}
-
-static inline void root_tag_clear_all(struct radix_tree_root *root)
-{
-       root->gfp_mask &= __GFP_BITS_MASK;
-}
-
-static inline int root_tag_get(struct radix_tree_root *root, unsigned

int tag)

(quoted diff) +0 -2
-{
-       return (__force unsigned)root->gfp_mask & (1 << (tag +

__GFP_BITS_SHIFT));

lib/radix-tree.c +0 -7
-}
-
-/*
- * Returns 1 if any slot in the node has this tag set.
- * Otherwise returns 0.
- */
-static inline int any_tag_set(struct radix_tree_node *node, unsigned

int tag)

lib/radix-tree.c +0 -14
-{
-       int idx;
-       for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
-               if (node->tags[tag][idx])
-                       return 1;
-       }
-       return 0;
-}
-
 /*
  *     Return the maximum key which can be store into a
  *     radix tree with height HEIGHT.
@@ -930,11 +939,6 @@ static inline void radix_tree_shrink(str
                        newptr = radix_tree_ptr_to_indirect(newptr);
                root->rnode = newptr;
                root->height--;
-               /* must only free zeroed nodes into the slab */
-               tag_clear(to_free, 0, 0);
-               tag_clear(to_free, 1, 0);
-               to_free->slots[0] = NULL;
-               to_free->count = 0;
                radix_tree_node_free(to_free);
        }
 }
maintainer
#2 lore raw
In reply to Nick Piggin
Quoted 34 lines · On Fri, 13 Jun 2008 05:03:45 +1000 Nick Piggin <[email protected]> wrote:

Hi guys,

Although this doesn't seem like cause for alarm (as per the analysis), it may still be a good 2.6.26 candidate as we should have a few more weeks of testing left.

It should definitely go in -mm with the lockless pagecache patch.

When shrinking a radix-tree, we do it in a lockless manner by atomically switching the root pointer away from the redundant node (one that only has a single entry in the left most slot), and switching it over to its lone child.

Because a lockless lookup may have got a reference to the parent and be in the middle of deciding what to do with it while it is being swapped away for its child. For this reason, we also have to keep it around and in a valid state for the lookup to proceed and give a valid result, for at least an RCU grace period. So we need to keep the child in the left most slot there in case that is requested by the lookup.

This is all pretty standard RCU stuff. It is worth repeating because in my eagerness to obey the radix tree node constructor scheme, I had broken this by zeroing the radix tree node before the grace period.

Fix it by clearing those fields in the RCU callback. I would normally want to rip out the constructor entirely, but radix tree nodes are one of those places where they make sense (only few cachelines will be touched soon after allocation).

This was never actually observed in any lockless pagecache testing or using the test harness, but as a rare problem testing my scalable vmap rewrite.

Quoted 6 lines

Fortunately, it is not a problem anywhere lockless pagecache is used in mainline kernels (pagecache probe is not a guarantee, and brd does not have concurrent lookups and deletes).

However, it would eventually pop up for someone using lockless pagecache :P

OK, I give up. A cannot spot what you actually changed amongst all the code motion?

#3 lore raw
Quoted 41 lines · Andrew Morton
Quoted 38 lines · On Fri, 13 Jun 2008 05:03:45 +1000 Nick Piggin <[email protected]> wrote:

Hi guys,

Although this doesn't seem like cause for alarm (as per the analysis), it may still be a good 2.6.26 candidate as we should have a few more weeks of testing left.

It should definitely go in -mm with the lockless pagecache patch.

When shrinking a radix-tree, we do it in a lockless manner by atomically switching the root pointer away from the redundant node (one that only has a single entry in the left most slot), and switching it over to its lone child.

Because a lockless lookup may have got a reference to the parent and be in the middle of deciding what to do with it while it is being swapped away for its child. For this reason, we also have to keep it around and in a valid state for the lookup to proceed and give a valid result, for at least an RCU grace period. So we need to keep the child in the left most slot there in case that is requested by the lookup.

This is all pretty standard RCU stuff. It is worth repeating because in my eagerness to obey the radix tree node constructor scheme, I had broken this by zeroing the radix tree node before the grace period.

Fix it by clearing those fields in the RCU callback. I would normally want to rip out the constructor entirely, but radix tree nodes are one of those places where they make sense (only few cachelines will be touched soon after allocation).

This was never actually observed in any lockless pagecache testing or using the test harness, but as a rare problem testing my scalable vmap rewrite.

Fortunately, it is not a problem anywhere lockless pagecache is used in mainline kernels (pagecache probe is not a guarantee, and brd does not have concurrent lookups and deletes).

Quoted 5 lines
Quoted 2 lines

However, it would eventually pop up for someone using lockless pagecache :P

OK, I give up. A cannot spot what you actually changed amongst all the code motion?

The two relevant hunks:

@@ -124,6 +175,17 @@ static void radix_tree_node_rcu_free(str
{
struct radix_tree_node *node =
container_of(head, struct radix_tree_node, rcu_head);
+
+ /*

+        * must only free zeroed nodes into the slab. radix_tree_shrink
+        * can leave us with a non-NULL entry in the first slot, so clear
+        * that here to make sure.
+        */
+       tag_clear(node, 0, 0);
+       tag_clear(node, 1, 0);
+       node->slots[0] = NULL;
+       node->count = 0;
+
        kmem_cache_free(radix_tree_node_cachep, node);

}

@@ -930,11 +939,6 @@ static inline void radix_tree_shrink(str

                        newptr = radix_tree_ptr_to_indirect(newptr);
                root->rnode = newptr;
                root->height--;
-               /* must only free zeroed nodes into the slab */
-               tag_clear(to_free, 0, 0);
-               tag_clear(to_free, 1, 0);
-               to_free->slots[0] = NULL;
-               to_free->count = 0;
                radix_tree_node_free(to_free);
        }

}

So instead of clearing the first slot on free, we delay it one grace period and clear it later. So that anybody already having a pointer to the node can correctly resolve the item.

maintainer
#4 lore raw
In reply to Nick Piggin
Quoted 7 lines · On Fri, 13 Jun 2008 05:03:45 +1000 Nick Piggin <[email protected]> wrote:
lib/radix-tree.c +3 -0
@@ -124,6 +175,17 @@ static void radix_tree_node_rcu_free(str
 {
 	struct radix_tree_node *node =
 			container_of(head, struct radix_tree_node, rcu_head);
+
+	/*
+	 * must only free zeroed nodes into the slab. radix_tree_shrink

lib/radix-tree.c static void radix_tree_node_rcu_free(str · line 190

Quoted 10 lines
lib/radix-tree.c +8 -0
+	 * can leave us with a non-NULL entry in the first slot, so clear
+	 * that here to make sure.
+	 */
+	tag_clear(node, 0, 0);
+	tag_clear(node, 1, 0);
+	node->slots[0] = NULL;
+	node->count = 0;
+
 	kmem_cache_free(radix_tree_node_cachep, node);
 }

oic, that stuff got moved from the synchronous case into the RCU callback case.

#5 lore raw
Quoted 15 lines · Andrew Morton

On Fri, 13 Jun 2008 05:03:45 +1000

Quoted 12 lines · Nick Piggin
lib/radix-tree.c +8 -0
@@ -124,6 +175,17 @@ static void radix_tree_node_rcu_free(str
 {
 	struct radix_tree_node *node =
 			container_of(head, struct radix_tree_node, rcu_head);
+
+	/*
+	 * must only free zeroed nodes into the slab. radix_tree_shrink
+	 * can leave us with a non-NULL entry in the first slot, so clear
+	 * that here to make sure.
+	 */
+	tag_clear(node, 0, 0);
+	tag_clear(node, 1, 0);
Quoted 8 lines

lib/radix-tree.c static void radix_tree_node_rcu_free(str · line 190

Quoted 5 lines
lib/radix-tree.c +3 -0
+	node->slots[0] = NULL;
+	node->count = 0;
+
 	kmem_cache_free(radix_tree_node_cachep, node);
 }

oic, that stuff got moved from the synchronous case into the RCU callback case.

Yeah, it was annoying because the real change moved the first references of a couple of those up. Then we have to move all of them to keep them in one place.

The changelog I submitted looks like utter gibberish, btw. Rewritten one here which should be a bit better.

We shrink a radix tree when its root node has only one child, in the left most slot. The child becomes the new root node. To perform this operation in a manner compatible with concurrent lockless lookups, we atomically switch the root pointer from the parent to its child.

However a concurrent lockless lookup may now have loaded a pointer to the parent (and is presently deciding what to do next). For this reason, we also have to keep the parent node in a valid state after shrinking the tree, until the next RCU grace period -- otherwise this lookup with the parent pointer may not do the right thing. Notably, we need to keep the child in the left most slot there in case that is requested by the lookup.

This is all pretty standard RCU stuff. It is worth repeating because in my eagerness to obey the radix tree node constructor scheme, I had broken it by zeroing the radix tree node before the grace period.

What could happen is that a lookup can load the parent pointer, then decide it wants to follow the left most child slot, only to find the slot contained NULL due to the concurrent shrinker having zeroed the parent node before waiting for a grace period. The lookup would return a false negative as a result.

Fix it by doing that clearing in the RCU callback. I would normally want to rip out the constructor entirely, but radix tree nodes are one of those places where they make sense (only few cachelines will be touched soon after allocation).

This was never actually found in any lockless pagecache testing or by the test harness, but by seeing the odd problem with my scalable vmap rewrite. I have not tickled the test harness into reproducing it yet, but I'll keep working at it.

Fortunately, it is not a problem anywhere lockless pagecache is used in mainline kernels (pagecache probe is not a guarantee, and brd does not have concurrent lookups and deletes).

Acked-by on v1 1/1
#6 lore raw
In reply to Nick Piggin
Quoted 7 lines · Nick Piggin

Hi guys,

Although this doesn't seem like cause for alarm (as per the analysis), it may still be a good 2.6.26 candidate as we should have a few more weeks of testing left.

It should definitely go in -mm with the lockless pagecache patch.

Good catch!!!

Quoted 189 lines

Thanks,
Nick

When shrinking a radix-tree, we do it in a lockless manner by atomically switching the root pointer away from the redundant node (one that only has a single entry in the left most slot), and switching it over to its lone child.

Because a lockless lookup may have got a reference to the parent and be in the middle of deciding what to do with it while it is being swapped away for its child. For this reason, we also have to keep it around and in a valid state for the lookup to proceed and give a valid result, for at least an RCU grace period. So we need to keep the child in the left most slot there in case that is requested by the lookup.

This is all pretty standard RCU stuff. It is worth repeating because in my eagerness to obey the radix tree node constructor scheme, I had broken this by zeroing the radix tree node before the grace period.

Fix it by clearing those fields in the RCU callback. I would normally want to rip out the constructor entirely, but radix tree nodes are one of those places where they make sense (only few cachelines will be touched soon after allocation).

This was never actually observed in any lockless pagecache testing or using the test harness, but as a rare problem testing my scalable vmap rewrite.

Fortunately, it is not a problem anywhere lockless pagecache is used in mainline kernels (pagecache probe is not a guarantee, and brd does not have concurrent lookups and deletes).

However, it would eventually pop up for someone using lockless pagecache :P

---
Index: linux-2.6/lib/radix-tree.c
===================================================================

lib/radix-tree.c +62 -58
@@ -88,6 +88,57 @@ static inline gfp_t root_gfp_mask(struct
 	return root->gfp_mask & __GFP_BITS_MASK;
 }
 
+static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
+		int offset)
+{
+	__set_bit(offset, node->tags[tag]);
+}
+
+static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
+		int offset)
+{
+	__clear_bit(offset, node->tags[tag]);
+}
+
+static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
+		int offset)
+{
+	return test_bit(offset, node->tags[tag]);
+}
+
+static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
+{
+	root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
+}
+
+static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
+{
+	root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
+}
+
+static inline void root_tag_clear_all(struct radix_tree_root *root)
+{
+	root->gfp_mask &= __GFP_BITS_MASK;
+}
+
+static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
+{
+	return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
+}
+
+/*
+ * Returns 1 if any slot in the node has this tag set.
+ * Otherwise returns 0.
+ */
+static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
+{
+	int idx;
+	for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
+		if (node->tags[tag][idx])
+			return 1;
+	}
+	return 0;
+}
 /*
  * This assumes that the caller has performed appropriate preallocation, and
  * that the caller has pinned this thread of control to the current CPU.
@@ -124,6 +175,17 @@ static void radix_tree_node_rcu_free(str
 {
 	struct radix_tree_node *node =
 			container_of(head, struct radix_tree_node, rcu_head);
+
+	/*
+	 * must only free zeroed nodes into the slab. radix_tree_shrink
+	 * can leave us with a non-NULL entry in the first slot, so clear
+	 * that here to make sure.
+	 */
+	tag_clear(node, 0, 0);
+	tag_clear(node, 1, 0);
+	node->slots[0] = NULL;
+	node->count = 0;
+
 	kmem_cache_free(radix_tree_node_cachep, node);
 }
 
@@ -165,59 +227,6 @@ out:
 }
 EXPORT_SYMBOL(radix_tree_preload);
 
-static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
-		int offset)
-{
-	__set_bit(offset, node->tags[tag]);
-}
-
-static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
-		int offset)
-{
-	__clear_bit(offset, node->tags[tag]);
-}
-
-static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
-		int offset)
-{
-	return test_bit(offset, node->tags[tag]);
-}
-
-static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
-{
-	root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
-}
-
-
-static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
-{
-	root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
-}
-
-static inline void root_tag_clear_all(struct radix_tree_root *root)
-{
-	root->gfp_mask &= __GFP_BITS_MASK;
-}
-
-static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
-{
-	return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
-}
-
-/*
- * Returns 1 if any slot in the node has this tag set.
- * Otherwise returns 0.
- */
-static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
-{
-	int idx;
-	for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
-		if (node->tags[tag][idx])
-			return 1;
-	}
-	return 0;
-}
-
 /*
  *	Return the maximum key which can be store into a
  *	radix tree with height HEIGHT.
@@ -930,11 +939,6 @@ static inline void radix_tree_shrink(str
 			newptr = radix_tree_ptr_to_indirect(newptr);
 		root->rnode = newptr;
 		root->height--;
-		/* must only free zeroed nodes into the slab */
-		tag_clear(to_free, 0, 0);
-		tag_clear(to_free, 1, 0);
-		to_free->slots[0] = NULL;
-		to_free->count = 0;
 		radix_tree_node_free(to_free);
 	}
 }