Re: [PATCH 1/12] radix_tree: exceptional entries and indices

From: Hugh Dickins
Date: Fri Jun 17 2011 - 20:14:05 EST

On Fri, 17 Jun 2011, Andrew Morton wrote:
> On Tue, 14 Jun 2011 03:42:27 -0700 (PDT)
> Hugh Dickins <hughd@xxxxxxxxxx> wrote:
> > The low bit of a radix_tree entry is already used to denote an indirect
> > pointer, for internal use, and the unlikely radix_tree_deref_retry() case.
> > Define the next bit as denoting an exceptional entry, and supply inline
> > functions radix_tree_exception() to return non-0 in either unlikely case,
> > and radix_tree_exceptional_entry() to return non-0 in the second case.
> Yes, the RADIX_TREE_INDIRECT_PTR hack is internal-use-only, and doesn't
> operate on (and hence doesn't corrupt) client-provided items.
> This patch uses bit 1 and uses it against client items, so for
> practical purpoese it can only be used when the client is storing
> addresses. And it needs new APIs to access that flag.
> All a bit ugly. Why not just add another tag for this? Or reuse an
> existing tag if the current tags aren't all used for these types of
> pages?

I couldn't see how to use tags without losing the "lockless" lookups:
because the tag is a separate bit from the entry itself, unless you're
under tree_lock, there would be races when changing from page pointer
to swap entry or back, when slot was updated but tag not or vice versa.

Perhaps solvable, like seqlocks, by having two tag bits, the combination
saying come back and look again in a moment. Hah, that can/is already
done with the low bit, the deref_retry. So, yes, we could use one tag
bit: but it would be messier (could no longer use the slow-path-slightly-
modified find_get_page() etc). I thought, while we've got a nearby bit
available, let's put it to use.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at