Bug in radix tree gang lookup?

I think there's a race in radix_tree_gang_lookup() (and related functions). I was trying to understand why we need the 'indirect_to_ptr()' call here:

        radix_tree_for_each_slot(slot, root, &iter, first_index) {
                results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
                if (!results[ret])
                        continue;
                if (++ret == max_items)
                        break;
        }

The slots returned are supposed to be leaf nodes, so why would they ever have the indirect bit set?

The only two cases I can think of where we'd see a slot with the indirect bit set is if we're calling radix_tree_gang_lookup() under the RCU read lock and simultaneously growing / shrinking the tree. When the tree transitions from height 0 to height 1, the 'slot' that was returned is now an internal pointer, so simply knocking off the 'indirect_to_ptr()' bit is the wrong thing to do; instead of returning a struct page pointer, we return a pointer to a radix_tree_node, which isn't good. When shrinking the tree from height 1 to height 0, we may end up looking at a pointer in to-be-freed memory, but it's still a valid pointer to a struct page, so I think we're OK in the shrink case.

The lockless page cache shows how to handle this correctly; when we see an indirect bit come back in a slot, we should retry the lookup. I think that's the right thing to do in this case, but I'd like someone to check my reasoning before I propose a patch.

I think you're right, in all you say above. And I think the last paragraph of comment above the one-level-of-indirection-different radix_tree_gang_lookup_slot() is making the same point, though its language hasn't been updated for years (it ought to say something like "radix_tree_deref_retry may require a retry").

Hugh