[ltt-dev] RCU lock-free hash table and RCU Red-Black tree (was: Re: [RFC PATCH 0/7] priority-boost urcu)

[Mathieu Desnoyers]

* Paolo Bonzini (pbonzini at redhat.com) wrote:
[...]
> What we should introduce is abstractions over futexes.  This is what I  
> did to experimentally port URCU to QEMU---my secret goal since commit  
> 806f811 (use kernel style makefile output, 2010-03-01). :)  Our use of  
> futexes is exceptionally similar to a Windows manual-reset event (yes,  
> Windows:  
> http://msdn.microsoft.com/en-us/library/system.threading.manualresetevent%28v=vs.80%29.aspx). 
>  In QEMU I added the manual-reset event and use it in the implementation 
> of RCU.

Talking about qemu, have you seen my development branches with RCU
lock-free hash table and RCU red-black tree ? They are publically
available in the userspace RCU git tree:

git://git.lttng.org/userspace-rcu.git

urcu/ht (RCU lock-free hash table)
rbtree2 (RCU red-black tree)

The code works, but needs review and feedback on the API. I'm more
comfortable with the complexity level of the hash table than with that
of the red-black tree, so it might get merged into the master branch
before the rbtree. The rbtree is interesting in that it supports
range-based lookups protected only by an RCU read-side lock, very well
suited for memory map address ranges.

I'm just saying, because qemu could very certainly benefit from these
lock-free and scalable data structures.

Thanks,

Mathieu


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com