Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1314984 > unrolled thread

Bug in radix tree gang lookup?

Back to article view | Back to linux.kernel

Contents

  Bug in radix tree gang lookup? Matthew Wilcox <willy@linux.intel.com> - 2016-01-22 14:50 +0100
    Re: Bug in radix tree gang lookup? Hugh Dickins <hughd@google.com> - 2016-01-27 05:10 +0100

#1314984 — 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.

[toc] | [next] | [standalone]

#1318598

On Fri, 22 Jan 2016, Matthew Wilcox wrote:
> 
> 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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web