From mboxrd@z Thu Jan 1 00:00:00 1970 From: Mathieu Desnoyers Subject: Re: RCU red-black tree (was: Re: [PATCH 4/6] kvm tools: Add rwlock wrapper) Date: Mon, 30 May 2011 07:30:38 -0400 Message-ID: <20110530113038.GB2871@Krystal> References: <4DDE97CE.4000302@redhat.com> <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> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii 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: Sasha Levin Return-path: Received: from mail.openrapids.net ([64.15.138.104]:42806 "EHLO blackscsi.openrapids.net" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1752473Ab1E3Lak (ORCPT ); Mon, 30 May 2011 07:30:40 -0400 Content-Disposition: inline In-Reply-To: <1306735631.14564.34.camel@lappy> Sender: kvm-owner@vger.kernel.org List-ID: * 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. Given we have to update the parent nodes when the interval values change, we need to work on a copy of these parent nodes to ensure that their information about the children min/max corresponds to the children's left/right pointers they contain. Any discrepancy between their left/right pointers and the children min/max value they store would be invalid from a reader's POV. I'll see if I can embed this in my tree. It should be doable with the "decay" approach I am using. We'll need a way to test this though: possibly by walking the tree with range-aware lookups that also make sure that the ranges that were promised by the upper nodes are contained within their children at all times. Thanks, Mathieu -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com