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(a)suse.com>
SUSE Labs, CR