Re: RCU red-black tree (was: Re: [PATCH 4/6] kvm tools: Add rwlock wrapper)

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

* Sasha Levin (levinsasha928@gmail.com) wrote:
> On Mon, 2011-05-30 at 13:38 -0400, Mathieu Desnoyers wrote:
> > * Sasha Levin (levinsasha928@gmail.com) wrote:
> > > On Sun, 2011-05-29 at 22:54 -0400, Mathieu Desnoyers wrote:
> > > > Please note that what I currently have is a normal rbtree, not an
> > > > interval rbtree. Can you elaborate on your use-case so I can try to
> > > > figure out how we could augment it to support the interval rbtree you
> > > > need ?
> > > 
> > > We don't need anything specific for interval rbtree. The rbtree used in
> > > the kernel provides augmentation functions for insert and erase (see
> > > rb_augment_insert() and rb_augment_erase_begin() +
> > > rb_augment_erase_end()).
> > > What they basically do is call a user-provided callback for each node
> > > from the newly inserted (or deepest after deletion) node up to the root
> > > of the tree. You can see our code at 'tools/kvm/util/rbtree-interval.c',
> > > basically all we need are the 2 augmentation functions I've mentioned
> > > above.
> > 
> > Just a little question about Documentation/rbtree.txt:
> > 
> > I see that find_lowest_match(lo, hi, node) seems to use ">" and "<" to
> > compare the lo value with the max_hi and node->lo. I think it would be
> > more natural to do range comparison functions with inclusive ranges (>=
> > and <=). Or maybe I am missing something about the way find_lowest_match
> > works ?
> 
> It's just an implementation of an interval search() function. Since
> kernel rbtree users implement their own search() and insert() functions
> (look in our util/rbtree-interval.c) it shouldn't be a consideration in
> designing the tree - we (the users of urcu/rbtree) want to control the
> search code anyway.

The reason why I provide this facility as part of the RCU rbtree is
because, unlike the kernel rbtree where every user is free to use
"inheritance" to put their object in the same cache-line as the rbtree
node, the RCU implementation needs to do copies of its inner nodes, so
the rbtree user cannot expect the node pointer to stay valid. Therefore,
I use a more usual scheme where the pointer to the user-provided data
structure is kept as a "void *key" in the node. So basically, the rbtree
user don't have to provide the search, next and prev functions: this is
all done within the rbtree code, especially because these have to be
RCU-aware, and because the code that augments the rbtree with ranges
needs to be RCU-aware too.

Finally, my tests showed up that the "<= and >=" need to have the equal
for the ranges to be inclusive. I tested this by using the same
test-case as the search, duplicating the key value as both lower and
upper bound of the range searched for. (see updated rbtree2 branch for
tested range search).

My stress-test now tests the range lookups, and it passes fine so far:

e.g.   test_urcu_rbtree 6 2 200 -g 40  (on a 8-core machine)

Thanks,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com