On Fri, Jan 13, 2012 at 10:18:06AM +0800, Liu Bo wrote:

On 01/13/2012 05:28 AM, Andi Kleen wrote:

quoted

Liu Bo [off-list ref] writes:

quoted

Here we choose extent_map firstly, since it is a "read mostly" thing,
and the change is quite direct, all we need to do is
a) to replace rbtree with skiplist,
b) to add rcu support.
And more details are in patch 2 and patch 3.

I've done some simple tests for performance on my 2-core box, there is no
obvious difference, but I want to focus on the design side and make sure
there is no more bug in it firstly.

For long term goals, we want to ship skiplist to lib, like lib/rbtree.c.

I looked at skiplists some time ago. What made them awkward for kernel
use is that you have to size the per node skip array in advance and it's
hard to resize. So you have a node that wastes memory in common small
cases, but still degenerates to linked list on very large sizes.
With fine grained locking it gets even worse because the nodes get larger.

....

quoted

But for a very scalable subsystem that's definitely a problem.

I think skiplists are not a good fit here.

....

quoted

Now replacing rbtrees is probably still a good idea, but not convinced
skiplist are suitable here. There were various other tree alternatives
with better locking.

Hi Andi,

I know what you're worried about, that still keeps biting me, too. ;)

Here we decide to make such an experiment of skiplist, since we have some
in-memory data structures that are dominated by reads, and what we want to
try is to apply RCU, a lockless read scheme, on them.

Yes, skiplist is not good enough for kernel use, but maybe RCU-skiplist can
be a candidate.

According to RCU semantic, once a RCU-skiplist is built, the "read most" thing
can ensure us that the whole skiplist will remain almost unchanged while running.
Thus, to some extent, we do not need to resize the nodes frequently.

So what do you think about this? :)

I don't think RCU lookups matter here - it's the fact that the
skiplist needs to be a pre-determined size that is the problem
because one size does not fit all users.

If you want a RCU-based tree structure for extent lookups, then an
RCU aware btree is a better bet. Dynamic resizing can be done in an
RCU aware manner (the radix trees do it) so you should probably take
the lib/btree.c code and look to making that RCU safe.  IIRC, the
implementation was based on a RCU-btree prototype so maybe you might
want to read up on that first:

http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch

FWIW, I'm mentioning this out of self interest - I need a RCU safe
tree structure to index extents for lookless lookups in the XFS
buffer cache, but I've got a long list of things to do before I get
to it. If someone else implements the tree, that's most of the work
done for me. :)

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com