Re: [patch 1/3] radix tree: RCU lockless read-side

[Nick Piggin <nickpiggin@yahoo.com.au>]

Balbir Singh wrote:
> > The "slots" member is an array, not an RCU assigned pointer. As such, after
> > doing rcu_dereference(slot), you can access slot->slots[i] without further
> > memory barriers I think?
> >
> > But I agree that code now is a bit inconsistent. I've cleaned things up a
> > bit in my tree now... but perhaps it is easier if you send a patch to show
> > what you mean (because sometimes I'm a bit dense, I'm afraid).
>
>
> Fro starters, I do not think your dense at all.

I'm glad you think so ;)

> Hmm... slot/slots is quite confusing name. I was referring to slot and
> ended up calling it slots. The point I am contending is that
> rcu_derefence(slot->slots[i]) should happen.
>
> <snippet>
> +                       __s = rcu_dereference(slot->slots[i]);
> +                       if (__s != NULL)
>                               break;
> </snippet>
>
> If we break from the loop because __s != NULL. Then in the snippet below

This is a little confusing, because technically I don't think it needs to
rcu_dereference here, either, only when we actually want to dereference
__s and read the data the other end.

rcu_dereference is perhaps an awkward interface for optimising this case.
#define rcu_make_pointer_safe_to_follow(ptr) smp_read_barrier_depends()
or
#define rcu_follow_pointer(ptr) ({ smp_read_barrier_depends(); *ptr; })
might be better

    __s = slot->slots[i];
    if (__s != NULL) {
        rcu_make_pointer_safe_to_follow(__s);
        ...

Would allow the barrier to be skipped if we're not going to follow the
pointer.

> <snippet>
>        /* Bottom level: grab some items */
>       for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
>               index++;
>               if (slot->slots[i]) {
> -                       results[nr_found++] = slot->slots[i];
> +                       results[nr_found++] = &slot->slots[i];
>                       if (nr_found == max_items)
>                               goto out;
>               }
> </snippet>
>
> We do not use __s above. "slot->slots[i]" is not rcu_derefenced() in
> this case because we broke out of the loop above with __s being not
> NULL. Another issue is - is it good enough to rcu_derefence() slot
> once? Shouldn't all uses of *slot->* be rcu derefenced?

Yes, slot is a local pointer, the address it points to will not change,
so once we have loaded it and issued the read barrier, we can follow it
from then on and reads will not find stale values.

> <suggestion (WARNING: patch has spaces and its not compiled)>
>        /* Bottom level: grab some items */
>       for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
>               index++;
> -              if (slot->slots[i]) {
> -                       results[nr_found++] = slot->slots[i];
> +             __s = rcu_dereference(slot->slots[i]);
> +             if (__s) {
> +                    /* This is tricky, cannot take the address of __s
> or rcu_derefence() */
> +                    results[nr_found++] = &slot->slots[i];
>                       if (nr_found == max_items)
>                               goto out;
>               }
> </suggestion>
>
> I hope I am making sense.

In this case I think we do not need a barrier because we are only looking
at the pointer (whether it is NULL or not), rather than following it down.
Paul may be able to jump in at this point.

I'll release a new patchset in the next couple of days and try to be more
consisten with the barriers which will hopefully make things less confusing.

Thanks,
Nick

--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/