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

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

* 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