From mboxrd@z Thu Jan 1 00:00:00 1970 From: Sasha Levin Subject: Re: RCU red-black tree (was: Re: [PATCH 4/6] kvm tools: Add rwlock wrapper) Date: Mon, 30 May 2011 22:11:17 +0300 Message-ID: <1306782677.15912.6.camel@lappy> References: <1306436223.3065.36.camel@lappy> <20110526230923.GB15983@Krystal> <1306491547.3217.9.camel@lappy> <20110527131400.GC29744@Krystal> <20110529170104.GA17189@Krystal> <1306691292.14564.12.camel@lappy> <20110530025414.GA25865@Krystal> <1306735631.14564.34.camel@lappy> <20110530173844.GA13361@Krystal> <1306777969.15912.3.camel@lappy> <20110530185757.GA13903@Krystal> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Cc: Pekka Enberg , Avi Kivity , Ingo Molnar , john@jfloren.net, kvm@vger.kernel.org, asias.hejun@gmail.com, gorcunov@gmail.com, prasadjoshi124@gmail.com, "Paul E. McKenney" , Phil Howard , rp@svcs.cs.pdx.edu To: Mathieu Desnoyers Return-path: Received: from mail-wy0-f174.google.com ([74.125.82.174]:57436 "EHLO mail-wy0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751041Ab1E3TLt (ORCPT ); Mon, 30 May 2011 15:11:49 -0400 Received: by wya21 with SMTP id 21so2816182wya.19 for ; Mon, 30 May 2011 12:11:48 -0700 (PDT) In-Reply-To: <20110530185757.GA13903@Krystal> Sender: kvm-owner@vger.kernel.org List-ID: 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.