[PATCH] radix-tree: 'slot' can be NULL in radix_tree_next_slot()

[Ross Zwisler]

There are four cases I can see where we could end up with a NULL 'slot' in
radix_tree_next_slot() (there might be more):

1) radix_tree_iter_retry() via a non-tagged iteration like
radix_tree_for_each_slot().  In this case we currently aren't seeing a bug
because radix_tree_iter_retry() sets

	iter->next_index = iter->index;

which means that in in the else case in radix_tree_next_slot(), 'count' is
zero, so we skip over the while() loop and effectively just return NULL
without ever dereferencing 'slot'.

2) radix_tree_iter_retry() via tagged iteration like
radix_tree_for_each_tagged().  With the current code this case is
unhandled and we have seen it result in a kernel crash when we dereference
'slot'.

3) radix_tree_iter_next() via via a non-tagged iteration like
radix_tree_for_each_slot().  This currently happens in shmem_tag_pins()
and shmem_partial_swap_usage().

I think that this case is currently unhandled.  Unlike with
radix_tree_iter_retry() case (#1 above) we can't rely on 'count' in the else
case of radix_tree_next_slot() to be zero, so I think it's possible we'll end
up executing code in the while() loop in radix_tree_next_slot() that assumes
'slot' is valid.

I haven't actually seen this crash on a test setup, but I don't think the
current code is safe.

4) radix_tree_iter_next() via tagged iteration like
radix_tree_for_each_tagged().  This happens in shmem_wait_for_pins().

radix_tree_iter_next() zeros out iter->tags, so we end up exiting
radix_tree_next_slot() here:

	if (flags & RADIX_TREE_ITER_TAGGED) {
		void *canon = slot;

		iter->tags >>= 1;
		if (unlikely(!iter->tags))
			return NULL;

Really we want to guarantee that we just bail out  of
radix_tree_next_slot() if we have a NULL 'slot'.  This is a more explicit
way of handling all the 4 above cases.

Signed-off-by: Ross Zwisler <ross.zwisler@xxxxxxxxxxxxxxx>
---
 include/linux/radix-tree.h | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index cb4b7e8..840308d 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -463,6 +463,9 @@ static inline struct radix_tree_node *entry_to_node(void *ptr)
 static __always_inline void **
 radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
 {
+	if (unlikely(!slot))
+		return NULL;
+
 	if (flags & RADIX_TREE_ITER_TAGGED) {
 		void *canon = slot;
 
-- 
2.9.0