Re: [PATCH 4/6] kvm tools: Add rwlock wrapper

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Thu, May 26, 2011 at 07:05:08PM -0400, Mathieu Desnoyers wrote:
> * Ingo Molnar (mingo@elte.hu) wrote:
> > 
> > * Pekka Enberg <penberg@kernel.org> wrote:
> > 
> > > On Thu, May 26, 2011 at 9:11 PM, Avi Kivity <avi@redhat.com> wrote:
> > > > On 05/26/2011 09:05 PM, Ingo Molnar wrote:
> > > >>
> > > >> >
> > > >> >  I've added some rwlocks because of what Ingo said yesterday about
> > > >> >  adding/removing devices after the first initialization phase.
> > > >> >
> > > >> >  Take MMIO lock for example: Since we can now run SMP guests, we may
> > > >> >  have multiple MMIO exits (one from each VCPU thread). Each of those
> > > >> >  exits leads to searching the MMIO rbtree.
> > > >> >
> > > >> >  We can use a mutex to lock it, but it just means that those threads
> > > >> >  will be blocked there instead of concurrently searching the MMIO
> > > >> >  tree which makes the search linear instead of parallel.
> > > >> >
> > > >> >  It's hard to bring 'real' numbers at this stage because the only
> > > >> >  'real' device we have which uses MMIO is the VESA driver, and we
> > > >> >  can't really simulate many VCPUs writing to it :)
> > > >>
> > > >> I'd suggest keeping it simple first - rwlocks are nasty and will
> > > >> bounce a cacheline just as much.
> > > >
> > > > Well, this is the first case where tools/kvm can do better than qemu with
> > > > its global lock, so I think it's worth it.
> > > >
> > > >> If lookup scalability is an issue we can extend RCU to tools/kvm/.
> > > >
> > > > Definitely rcu is a perfect patch for mmio dispatch.
> > > 
> > > Userspace RCU code is here, Sasha, if you feel like tackling this:
> > > 
> > > http://lttng.org/urcu
> > > 
> > > :-)
> > > 
> > > I'm CC'ing Paul and Mathieu as well for urcu.

I am hoping we can get better convergence between the user-level and
kernel-level URCU implementations once I get SRCU merged into the TREE_RCU
and TINY_RCU implementations.  But it is early days for user-level RCU
implementations -- for example, the kernel-level implementations have
deep dependencies on being able to lock themselves cheaply to a given CPU,
which does not exist at user level.

But there seems to be an assumption that there should be only one URCU
implementation, and I am not sure that this assumption holds.  For
example, there are several in http://lttng.org/urcu, each corresponding
to different use cases.  This should not be too much of a surprise, given
that there are quite a few implementations in the Linux kernel: TINY_RCU,
TINY_PREEMPT_RCU, TREE_RCU, TREE_PREEMPT_RCU, and SRCU.  Of course,
each of the first four variants provides RCU-bh and RCU-sched, and
TINY_PREEMPT_RCU and TREE_PREEMPT_RCU provide preemptible RCU in addition.

And back in the mid-1990s, I would never have imagined a need for more
than one implementation of RCU.  ;-)

All that aside, one advantage of http://lttng.org/urcu is that it already
exists, which allows prototyping to proceed immediately.  If it turns
out that URCU doesn't help for whatever reason, then there is no point in
worrying further.  And if URCU does turn out to help, we will know more
about exactly what this particular situation requires of URCU, which
will likely help us better understand what the implemenation should
look like -- perhaps very close to one of the URCU implementations,
perhaps very close to one of the in-kernel implementations.

Seem reasonable, or am I missing something here?

							Thanx, Paul

> > I think we should rather share some of the kernel RCU code in an 
> > intelligent way
> 
> Hi Ingo,
> 
> By all means feel free to redo all the work Paul have spent care and
> time coding and testing.
> 
> > instead of bringing in yet another library which is a 
> > IIRC a distant copy of the kernel code to begin with.
> 
> This is either a lie, or immensely misinformed. You should go and look
> at the source before doing nonsensical assumptions like this. What you
> are saying cannot be further from the truth.
> 
> > 
> > That way we could lazily benefit from all the enhancements Paul does 
> > to the kernel RCU code! :-)
> 
> Maybe there is a reason why Paul have been working with me on the
> userspace RCU implementation in parallel with working on the Linux
> kernel one ?
> 
> > 
> > Note that kernel/treercu.c is pretty tied to the kernel right now, so 
> > a first approach could be to:
> > 
> >  - Check Paul's excellent documentation about RCU and make sure
> >    you don't miss Paul's excellent 3-part primer on LWN.net:
> > 
> >      http://lwn.net/Articles/262464/
> >      http://lwn.net/Articles/263130/
> >      http://lwn.net/Articles/264090/
> > 
> >    There are also lots of very good RCU articles on the LWN Kernel 
> >    Index page:
> > 
> > 	http://lwn.net/Kernel/Index/
> 
> Or just (see README)
> 
> git clone git://git.lttng.org/urcu
> cd userspace-rcu
> ./bootstrap
> ./configure
> make
> make install
> ldconfig
> 
> #include <urcu.h>
> gcc -lurcu ...
> 
> and be done with it ?
> 
> >  - Check kernel/tinyrcu.c to see how RCU is implemented in its 
> >    simplest form. :)
> 
> ...so simplistic it only works on UP systems, which are not so common
> these days on the systems targeted by kvm.
> 
> > 
> >  - Copy the tree-RCU code from kernel/treercu.c to tools/kvm/rcu/
> 
> This code is very much tied with the kernel scheduler. This is actually
> one of the main reason why we had to reimplement RCU for userspace
> rather than to "simply copy the kernel one" as you recommend.
> 
> > 
> >  - Massage it so far that it is suitable for tools/kvm/. We really
> >    only need a few core RCU facilities initially:
> > 
> >     struct rcu_head;
> > 
> >     rcu_read_lock();
> >     rcu_read_unlock();
> > 
> >     rcu_dereference()
> > 
> >     call_rcu(head, func);
> > 
> >     rcu_synchronize();
> > 
> >    The rest, _bh(), etc. are all kernelisms.
> 
> rcu_synchronize and the rcu read lock/unlock, in tree RCU, are tied to
> the scheduler to deal with preemption. User-land does not have this
> luxury.
> 
> > 
> >  - Then once it's working we could look at doing the code sharing
> >    *for real*: splitting the functionality out of the original
> >    treercu.c code into kernel/treercu-lib.c and rcuupdate-lib.h or so
> >    and include that one in tools/kvm/rcu/.
> > 
> >  - [ You might also benefit from porting rcutorture code to 
> >      user-space. It will catch RCU bugs like nothing else. ]
> 
> Userspace RCU already includes the torture test suite you are referring
> to.
> 
> > 
> > That way the 'core RCU' logic would be contained in treercu-lib.c, 
> > all kernel glue would be in kernel/rcutree.c.
> > 
> > Some other approach might be possible as well, this was just a first 
> > rough idea :)
> 
> "wheel not invented here" syndrome ?
> 
> Mathieu
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com