by Nick Piggin

[permalink] [raw]

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

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

2006-03-14 12:59:37

by Wu Fengguang

[permalink] [raw]

Subject: Re: A lockless pagecache for Linux

On Tue, Mar 14, 2006 at 03:14:38PM +1100, Nick Piggin wrote:
> Christoph Lameter wrote:
> >What you are proposing is to allow lockless read operations right? No
> >lockless write? The concurrency issue that we currently have is multiple
> >processes faulting in pages in different ranges from the same file. I
> >think this is a rather typical usage scenario. Faulting in a page from a
> >file for reading requires a write operation on the radix tree. The
> >approach with a lockless read path does not help us. This proposed scheme
> >would only help if pages are already faulted in and another process starts
> >using the same pages as an earlier process.
> >
>
> Yep, lockless reads only to start with. I think you'll see some benefit
> because the read(2) and ->nopage paths also take read-side locks, so your
> write side will no longer have to contend with them.
>
> It won't be a huge improvement in scalability though, maybe just a constant
> factor.
>
> >Would it not be better to handle the radix tree in the same way as a page
> >table? Have a lock at the lowest layer so that different sections of the
> >radix tree can be locked by different processes? That would enable
> >concurrent writes.
> >
>
> Yeah this is the next step. Note that it is not the first step because I
> actually want to _speed up_ single threaded lookup paths, rather than
> slowing them down, otherwise it will never get accepted.
>
> It also might add quite a large amount of complexity to the radix tree, so
> it may no longer be suitable for a generic data structure anymore (depends
> how it is implemented). But the write side should be easier than the
> read-side so I don't think there is too much to worry about. I already have
> some bits and pieces to make it fine-grained.

Maybe we can try another way to reduce the concurrent radix tree
writers problem: coordinating and serializing writers at high level.

Since kswapd is the major radix tree deleter, and readahead is the
major radix tree inserter, putting parts of them together in a loop
might reduce the contention noticeably.

The following pseudo-code shows the basic idea:
(Integrating kprefetchd is also possible. Just for simplicity...:)

PER_NODE(ra_queue);

kswapd()
{
loop {
loop {
free enough pages for top(ra_queue)
}
submit(pop(ra_queue));
wait();
}
}

readahead()
{
assemble one ra_req

if (ra_req immediately needed)
submit(ra_req);
else {
push(ra_queue, ra_req);
wakeup_kswapd();
}
}

This scheme might reduce
- direct page reclaim pressure
- radix tree write lock contention
- lru lock contention

Regards,
Wu