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: Thu, 2 Jun 2011 10:55:15 -0400 Message-ID: <20110602145515.GA19921@Krystal> References: <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> <1306847114.25406.9.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]:33237 "EHLO blackscsi.openrapids.net" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1752184Ab1FBOzS (ORCPT ); Thu, 2 Jun 2011 10:55:18 -0400 Content-Disposition: inline In-Reply-To: <1306847114.25406.9.camel@lappy> Sender: kvm-owner@vger.kernel.org List-ID: * Sasha Levin (levinsasha928@gmail.com) wrote: [...] > Mathieu, > > I've started working on converting our MMIO code to use RCU rbtree. > > It looks like each node contains one key, and the search functions > search for a node with a key in a specific range. > > Instead, the key in interval tree nodes is a range, and when searching > we try to find which node's range contains our search param. > > For example, our MMIO mapper maps an address space into devices, so we > can have one node which holds the range (0x100-0x200) which maps to a > VGA card, a (0x400-0x500) which maps to a sound card, and so on. Then, > when a guest is running and tries to write to 0x150, we want to know > which device it maps to. Hi Sasha, I finished updating the RCU RBTree internals and API to store ranges and query points or ranges instead of simple values. My tests are passing fine so far. I also added some documentation in the code explaining how I deal with search/prev/next reads vs concurrent writers. Feedback about the API would be very welcome! It's all available in the urcu rbtree2 branch. Thanks! Mathieu -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com