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

[Sasha Levin <levinsasha928@gmail.com>]

On Mon, 2011-05-30 at 14:57 -0400, Mathieu Desnoyers wrote:
> * 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)

Alright, so if urcu has rbtrees I'll make sure tools/kvm/ starts using
urcu.

I'll send an update tomorrow once I have something working. 


-- 

Sasha.