On Mon 21-03-16 13:34:58, Matthew Wilcox wrote:
> I have a patch currently in my tree which has the same effect, but looks
> a little neater:
>
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index b77c31c..06dfed5 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -70,6 +70,8 @@ struct radix_tree_preload {
> };
> static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
>
> +#define RADIX_TREE_RETRY ((void *)1)
> +
> static inline void *ptr_to_indirect(void *ptr)
> {
> return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
> @@ -934,7 +936,7 @@ restart:
> }
>
> slot = rcu_dereference_raw(node->slots[offset]);
> - if (slot == NULL)
> + if ((slot == NULL) || (slot == RADIX_TREE_RETRY))
> goto restart;
> offset = follow_sibling(node, &slot, offset);
> if (!radix_tree_is_indirect_ptr(slot))
> @@ -1443,8 +1455,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
> * to force callers to retry.
> */
> if (!radix_tree_is_indirect_ptr(slot))
> - *((unsigned long *)&to_free->slots[0]) |=
> - RADIX_TREE_INDIRECT_PTR;
> + to_free->slots[0] = RADIX_TREE_RETRY;
>
> radix_tree_node_free(to_free);
> }
>
> What do you think to doing it this way?
>
> It might be slightly neater to replace the first hunk with this:
>
> #define RADIX_TREE_RETRY ((void *)RADIX_TREE_INDIRECT_PTR)
>
> I also considered putting that define in radix-tree.h instead of
> radix-tree.c, but on the whole I don't think it'll be useful outside
> radix-tree.h.
So after spending over and hour reading radix tree code back and forth (and
also digging into historical versions where stuff is easier to understand) I
think I can finally fully appreciate subtlety of the retry logic ;). And
actually now I think that Neil's variant is buggy because in his case
radix_tree_lookup() could return NULL if it raced with radix_tree_shrink()
for index 0, although there is valid entry at index 0.
Your variant actually doesn't make things much better. See e.g.
mm/filemap.c: find_get_entry()
pagep = radix_tree_lookup_slot(&mapping->page_tree, offset);
// pagep points to node that is under RCU freeing
if (pagep) {
page = radix_tree_deref_slot(pagep);
if (unlikely(!page)) // False since
// RADIX_TREE_INDIRECT_PTR is set
if (radix_tree_exception(page)) // False - no exeptional bit
if (!page_cache_get_speculative(page)) // oops...
What we need to do is either to make all radix_tree_deref_slot() callers
check return value immediately with something like radix_tree_deref_retry()
(but that is still prone to hard to debug bugs when someone forgets to call
radix_tree_deref_retry() in some place) or we just give up the idea of
using INDIRECT bit in exceptional entries.
Honza
--
Jan Kara <jack@xxxxxxxx>
SUSE Labs, CR
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
