All of lore.kernel.org
 help / color / mirror / Atom feed
From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: Sasha Levin <levinsasha928@gmail.com>
Cc: Pekka Enberg <penberg@kernel.org>, Avi Kivity <avi@redhat.com>,
	Ingo Molnar <mingo@elte.hu>,
	john@jfloren.net, kvm@vger.kernel.org, asias.hejun@gmail.com,
	gorcunov@gmail.com, prasadjoshi124@gmail.com,
	"Paul E. McKenney" <paulmck@linux.vnet.ibm.com>,
	Phil Howard <csbetterthanjava@gmail.com>,
	rp@svcs.cs.pdx.edu
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	[thread overview]
Message-ID: <20110602145515.GA19921@Krystal> (raw)
In-Reply-To: <1306847114.25406.9.camel@lappy>

* 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

  parent reply	other threads:[~2011-06-02 14:55 UTC|newest]

Thread overview: 82+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2011-05-26 14:25 [PATCH 1/6] kvm tools: Prevent double assignment of guest memory info Sasha Levin
2011-05-26 14:25 ` [PATCH 2/6] kvm tools: Exit VCPU thread only when SIGKVMEXIT is received Sasha Levin
2011-05-26 14:25 ` [PATCH 3/6] kvm tools: Protect IRQ allocations by a mutex Sasha Levin
2011-05-26 14:25 ` [PATCH 4/6] kvm tools: Add rwlock wrapper Sasha Levin
2011-05-26 16:02   ` Pekka Enberg
2011-05-26 16:19     ` Sasha Levin
2011-05-26 18:05       ` Ingo Molnar
2011-05-26 18:11         ` Avi Kivity
2011-05-26 18:21           ` Pekka Enberg
2011-05-26 18:57             ` Sasha Levin
2011-05-26 23:09               ` Mathieu Desnoyers
2011-05-27 10:19                 ` Sasha Levin
2011-05-27 10:36                   ` Ingo Molnar
2011-05-27 15:52                     ` Sasha Levin
2011-05-27 17:10                       ` Ingo Molnar
2011-05-27 20:19                         ` Sasha Levin
2011-05-28 15:24                           ` Ingo Molnar
2011-05-28 16:44                             ` Paul E. McKenney
2011-05-28 19:45                             ` Sasha Levin
2011-05-29  6:47                               ` Avi Kivity
2011-05-29  7:19                                 ` Ingo Molnar
2011-05-29 15:31                                   ` Paul E. McKenney
2011-05-29 15:51                                     ` Paul E. McKenney
2011-05-29 19:54                                       ` Ingo Molnar
2011-05-30  3:12                                         ` Paul E. McKenney
2011-05-29 16:22                                     ` Sasha Levin
2011-05-27 13:14                   ` Mathieu Desnoyers
2011-05-29 17:01                     ` RCU red-black tree (was: Re: [PATCH 4/6] kvm tools: Add rwlock wrapper) Mathieu Desnoyers
2011-05-29 17:48                       ` Sasha Levin
2011-05-30  2:54                         ` Mathieu Desnoyers
2011-05-30  6:07                           ` Sasha Levin
2011-05-30 11:30                             ` Mathieu Desnoyers
2011-05-30 17:38                             ` Mathieu Desnoyers
2011-05-30 17:50                               ` Mathieu Desnoyers
2011-05-30 17:52                               ` Sasha Levin
2011-05-30 18:57                                 ` Mathieu Desnoyers
2011-05-30 19:11                                   ` Sasha Levin
2011-05-31 13:05                                   ` Sasha Levin
2011-05-31 13:09                                     ` Ingo Molnar
2011-05-31 13:20                                       ` Sasha Levin
2011-05-31 15:25                                         ` Ingo Molnar
2011-05-31 19:09                                           ` Prasad Joshi
2011-05-31 19:31                                             ` Ingo Molnar
2011-06-02 14:55                                     ` Mathieu Desnoyers [this message]
2011-05-30  3:38                       ` Paul E. McKenney
2011-05-30 11:18                         ` Mathieu Desnoyers
2011-05-26 20:25             ` [PATCH 4/6] kvm tools: Add rwlock wrapper Ingo Molnar
2011-05-26 23:05               ` Mathieu Desnoyers
2011-05-27  0:58                 ` Paul E. McKenney
2011-05-27  9:12                   ` Ingo Molnar
2011-05-27 12:48                     ` Mathieu Desnoyers
2011-05-27 13:19                       ` Ingo Molnar
2011-05-27 13:29                         ` Mathieu Desnoyers
2011-05-27 13:36                           ` Ingo Molnar
2011-05-27 17:22                     ` Paul E. McKenney
2011-05-27 10:25                 ` Ingo Molnar
2011-05-27 11:07                   ` Ingo Molnar
2011-05-27 11:10                     ` Ingo Molnar
2011-05-27 11:24                       ` Ingo Molnar
2011-05-27 14:18                         ` Mathieu Desnoyers
2011-05-27 14:11                     ` Mathieu Desnoyers
2011-05-28 18:12                     ` Avi Kivity
2011-05-28 18:32                       ` Ingo Molnar
2011-05-29  6:41                         ` Avi Kivity
2011-05-29  7:35                           ` Ingo Molnar
2011-05-29  7:54                             ` Avi Kivity
2011-05-29 12:37                               ` Ingo Molnar
2011-05-29 12:48                                 ` Avi Kivity
2011-05-29 14:27                                   ` Ingo Molnar
2011-05-29 15:00                                     ` Avi Kivity
2011-05-29 15:38                                       ` Paul E. McKenney
2011-05-29 19:33                                         ` Ingo Molnar
2011-05-30  3:07                                           ` Paul E. McKenney
2011-05-30  8:12                                             ` Ingo Molnar
2011-05-27 13:22                   ` Mathieu Desnoyers
2011-05-27 13:31                     ` Ingo Molnar
2011-05-28 18:14                       ` Avi Kivity
2011-05-27 13:07                 ` Ingo Molnar
2011-05-26 14:25 ` [PATCH 5/6] kvm tools: Protect MMIO tree by rwsem Sasha Levin
2011-05-26 14:25 ` [PATCH 6/6] kvm tools: Protect IOPORT " Sasha Levin
2011-05-26 16:01   ` Pekka Enberg
2011-05-26 16:19     ` Sasha Levin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20110602145515.GA19921@Krystal \
    --to=mathieu.desnoyers@efficios.com \
    --cc=asias.hejun@gmail.com \
    --cc=avi@redhat.com \
    --cc=csbetterthanjava@gmail.com \
    --cc=gorcunov@gmail.com \
    --cc=john@jfloren.net \
    --cc=kvm@vger.kernel.org \
    --cc=levinsasha928@gmail.com \
    --cc=mingo@elte.hu \
    --cc=paulmck@linux.vnet.ibm.com \
    --cc=penberg@kernel.org \
    --cc=prasadjoshi124@gmail.com \
    --cc=rp@svcs.cs.pdx.edu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.