* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Will Deacon @ 2016-01-26 12:10 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160126010646.GH4503@linux.vnet.ibm.com>
On Mon, Jan 25, 2016 at 05:06:46PM -0800, Paul E. McKenney wrote:
> On Mon, Jan 25, 2016 at 02:41:34PM +0000, Will Deacon wrote:
> > On Fri, Jan 15, 2016 at 11:28:45AM -0800, Paul E. McKenney wrote:
> > > On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
> > > > On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
> > > > > See my earlier reply [1] (but also, your WRC Linux example looks more
> > > > > like a variant on WWC and I couldn't really follow it).
> > > >
> > > > I will revisit my WRC Linux example. And yes, creating litmus tests
> > > > that use non-fake dependencies is still a bit of an undertaking. :-/
> > > > I am sure that it will seem more natural with time and experience...
> > >
> > > Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
> > > last access from a store to a load to get WRC. Plus the levels of
> > > indirection definitely didn't match up, did they?
> >
> > Nope, it was pretty baffling!
>
> "It is a service that I provide." ;-)
>
> > > struct foo {
> > > struct foo *next;
> > > };
> > > struct foo a;
> > > struct foo b;
> > > struct foo c = { &a };
> > > struct foo d = { &b };
> > > struct foo x = { &c };
> > > struct foo y = { &d };
> > > struct foo *r1, *r2, *r3;
> > >
> > > void cpu0(void)
> > > {
> > > WRITE_ONCE(x.next, &y);
> > > }
> > >
> > > void cpu1(void)
> > > {
> > > r1 = lockless_dereference(x.next);
> > > WRITE_ONCE(r1->next, &x);
> > > }
> > >
> > > void cpu2(void)
> > > {
> > > r2 = lockless_dereference(y.next);
> > > r3 = READ_ONCE(r2->next);
> > > }
> > >
> > > In this case, it is legal to end the run with:
> > >
> > > r1 == &y && r2 == &x && r3 == &c
> > >
> > > Please see below for a ppcmem litmus test.
> > >
> > > So, did I get it right this time? ;-)
> >
> > The code above looks correct to me (in that it matches WRC+addrs),
> > but your litmus test:
> >
> > > PPC WRCnf+addrs
> > > ""
> > > {
> > > 0:r2=x; 0:r3=y;
> > > 1:r2=x; 1:r3=y;
> > > 2:r2=x; 2:r3=y;
> > > c=a; d=b; x=c; y=d;
> > > }
> > > P0 | P1 | P2 ;
> > > stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
> > > | stw r2,0(r3) | lwz r9,0(r8) ;
> > > exists
> > > (1:r8=y /\ 2:r8=x /\ 2:r9=c)
> >
> > Seems to be missing the address dependency on P1.
>
> You are quite correct! How about the following?
I think that's it!
> As before, both herd and ppcmem say that the cycle is allowed, as
> expected, given non-transitive ordering. To prohibit the cycle, P1
> needs a suitable memory-barrier instruction.
>
> ------------------------------------------------------------------------
>
> PPC WRCnf+addrs
> ""
> {
> 0:r2=x; 0:r3=y;
> 1:r2=x; 1:r3=y;
> 2:r2=x; 2:r3=y;
> c=a; d=b; x=c; y=d;
> }
> P0 | P1 | P2 ;
> stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
> | stw r2,0(r8) | lwz r9,0(r8) ;
> exists
> (1:r8=y /\ 2:r8=x /\ 2:r9=c)
Agreed.
Will
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Will Deacon @ 2016-01-26 11:09 UTC (permalink / raw)
To: Peter Zijlstra
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, virtualization,
H. Peter Anvin, sparclinux, Ingo Molnar, linux-arch, linux-s390,
Russell King - ARM Linux, user-mode-linux-devel, linux-sh,
Michael Ellerman, x86, xen-devel, Ingo Molnar, Paul E. McKenney,
linux-xtensa, james.hogan, Arnd Bergmann, Stefano Stabellini,
adi-buildroot-devel, Leonid Yegoshin, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <20160126103200.GI6375@twins.programming.kicks-ass.net>
On Tue, Jan 26, 2016 at 11:32:00AM +0100, Peter Zijlstra wrote:
> On Tue, Jan 26, 2016 at 11:24:02AM +0100, Peter Zijlstra wrote:
>
> > Yeah, this goes under the header: memory-barriers.txt is _NOT_ a
> > specification (I seem to keep repeating this).
>
> Do we want this ?
>
> ---
> Documentation/memory-barriers.txt | 17 +++++++++++++++++
> 1 file changed, 17 insertions(+)
>
> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> index a61be39c7b51..433326ebdc26 100644
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -1,3 +1,4 @@
> +
> ============================
> LINUX KERNEL MEMORY BARRIERS
> ============================
> @@ -5,6 +6,22 @@
> By: David Howells <dhowells@redhat.com>
> Paul E. McKenney <paulmck@linux.vnet.ibm.com>
>
> +==========
> +DISCLAIMER
> +==========
> +
> +This document is not a specification; it is intentionally (for the sake of
> +brevity) and unintentionally (due to being human) incomplete. This document is
> +meant as a guide to using the various memory barriers provided by Linux, but
> +in case of any doubt (and there are many) please ask.
It might be worth adding you and me to the top of the file, to save Paul
Cc'ing us on questions (get_maintainer.pl points at poor old Corbet for
this file).
But yes, it seems that something like this is required.
Will
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Peter Zijlstra @ 2016-01-26 10:32 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160126102402.GE6357@twins.programming.kicks-ass.net>
On Tue, Jan 26, 2016 at 11:24:02AM +0100, Peter Zijlstra wrote:
> Yeah, this goes under the header: memory-barriers.txt is _NOT_ a
> specification (I seem to keep repeating this).
Do we want this ?
---
Documentation/memory-barriers.txt | 17 +++++++++++++++++
1 file changed, 17 insertions(+)
diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index a61be39c7b51..433326ebdc26 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -1,3 +1,4 @@
+
============================
LINUX KERNEL MEMORY BARRIERS
============================
@@ -5,6 +6,22 @@
By: David Howells <dhowells@redhat.com>
Paul E. McKenney <paulmck@linux.vnet.ibm.com>
+==========
+DISCLAIMER
+==========
+
+This document is not a specification; it is intentionally (for the sake of
+brevity) and unintentionally (due to being human) incomplete. This document is
+meant as a guide to using the various memory barriers provided by Linux, but
+in case of any doubt (and there are many) please ask.
+
+I repeat, this document is not a specification of what Linux expects from
+hardware.
+
+=====
+INDEX
+=====
+
Contents:
(*) Abstract memory access model.
^ permalink raw reply related
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Peter Zijlstra @ 2016-01-26 10:24 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160114222046.GH3818@linux.vnet.ibm.com>
On Thu, Jan 14, 2016 at 02:20:46PM -0800, Paul E. McKenney wrote:
> On Thu, Jan 14, 2016 at 01:24:34PM -0800, Leonid Yegoshin wrote:
> > On 01/14/2016 12:48 PM, Paul E. McKenney wrote:
> > >
> > >So SYNC_RMB is intended to implement smp_rmb(), correct?
> > Yes.
> > >
> > >You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
> > >smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
> >
> > If smp_read_barrier_depends() is used to separate not only two reads
> > but read pointer and WRITE basing on that pointer (example below) -
> > yes. I just doesn't see any example of this in famous
> > Documentation/memory-barriers.txt and had no chance to know what you
> > use it in this way too.
>
> Well, Documentation/memory-barriers.txt was intended as a guide for Linux
> kernel hackers, and not for hardware architects.
Yeah, this goes under the header: memory-barriers.txt is _NOT_ a
specification (I seem to keep repeating this).
> ------------------------------------------------------------------------
>
> commit 955720966e216b00613fcf60188d507c103f0e80
> Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Date: Thu Jan 14 14:17:04 2016 -0800
>
> documentation: Subsequent writes ordered by rcu_dereference()
>
> The current memory-barriers.txt does not address the possibility of
> a write to a dereferenced pointer. This should be rare,
How are these rare? Isn't:
rcu_read_lock()
obj = rcu_dereference(ptr);
if (!atomic_inc_not_zero(&obj->ref))
obj = NULL;
rcu_read_unlock();
a _very_ common thing to do?
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Peter Zijlstra @ 2016-01-26 10:19 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160126060322.GJ4503@linux.vnet.ibm.com>
On Mon, Jan 25, 2016 at 10:03:22PM -0800, Paul E. McKenney wrote:
> On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
> > On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
> > > On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
> > > > Yes, that seems a good start. But yesterday you raised the 'fun' point
> > > > of two globally ordered sequences connected by a single local link.
> > >
> > > The conclusion that I am slowly coming to is that litmus tests should
> > > not be thought of as linear chains, but rather as cycles. If you think
> > > of it as a cycle, then it doesn't matter where the local link is, just
> > > how many of them and how they are connected.
> >
> > Do you have some examples of this? I'm struggling to make it work in my
> > mind, or are you talking specifically in the context of the kernel
> > memory model?
>
> Now that you mention it, maybe it would be best to keep the transitive
> and non-transitive separate for the time being anyway. Just because it
> might be possible to deal with does not necessarily mean that we should
> be encouraging it. ;-)
So isn't smp_mb__after_unlock_lock() exactly such a scenario? And would
not someone trying to implement RCsc locks using locally transitive
RELEASE/ACQUIRE operations need exactly this stuff?
That is, I am afraid we need to cover the mix of local and global
transitive operations at least in overview.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Peter Zijlstra @ 2016-01-26 10:15 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160126061211.GK4503@linux.vnet.ibm.com>
On Mon, Jan 25, 2016 at 10:12:11PM -0800, Paul E. McKenney wrote:
> On Mon, Jan 25, 2016 at 06:02:34PM +0000, Will Deacon wrote:
> > Thanks for having a go at this. I tried defining something axiomatically,
> > but got stuck pretty quickly. In my scheme, I used "data-directed
> > transitivity" instead of "local transitivity", since the latter seems to
> > be a bit of a misnomer.
>
> I figured that "local" meant local to the CPUs participating in the
> release-acquire chain. As opposed to smp_mb() chains where the ordering
> is "global" as in visible to all CPUs, whether on the chain or not.
> Does that help?
That is in fact how I read and understood it.
^ permalink raw reply
* Re: [PATCH v3 0/4] x86: faster mb()+documentation tweaks
From: Boris Petkov @ 2016-01-26 8:26 UTC (permalink / raw)
To: Michael S. Tsirkin
Cc: Davidlohr Bueso, Davidlohr Bueso, Peter Zijlstra,
the arch/x86 maintainers, linux-kernel, virtualization,
H. Peter Anvin, Thomas Gleixner, Paul E. McKenney, Linus Torvalds,
Ingo Molnar
In-Reply-To: <20160126102022-mutt-send-email-mst@redhat.com>
"Michael S. Tsirkin" <mst@redhat.com> wrote:
>Sorry - in which tree are these applied?
They'll appear in tip at some point.
--
Sent from a small device: formatting sux and brevity is inevitable.
^ permalink raw reply
* Re: [PATCH v3 0/4] x86: faster mb()+documentation tweaks
From: Michael S. Tsirkin @ 2016-01-26 8:23 UTC (permalink / raw)
To: Borislav Petkov
Cc: Davidlohr Bueso, Davidlohr Bueso, Peter Zijlstra,
the arch/x86 maintainers, linux-kernel, virtualization,
H. Peter Anvin, Thomas Gleixner, Paul E. McKenney, Linus Torvalds,
Ingo Molnar
In-Reply-To: <20160114113934.GC19941@pd.tnic>
On Thu, Jan 14, 2016 at 12:39:34PM +0100, Borislav Petkov wrote:
> > Michael S. Tsirkin (4):
> > x86: add cc clobber for addl
> > x86: drop a comment left over from X86_OOSTORE
> > x86: tweak the comment about use of wmb for IO
>
> First three look ok to me regardless of what happens with 4. So applied.
Sorry - in which tree are these applied?
Thanks,
--
MST
^ permalink raw reply
* Re: [PATCH v2 0/3] x86: faster mb()+other barrier.h tweaks
From: Michael S. Tsirkin @ 2016-01-26 8:20 UTC (permalink / raw)
To: H. Peter Anvin
Cc: Davidlohr Bueso, Davidlohr Bueso, Peter Zijlstra,
the arch/x86 maintainers, linux-kernel, virtualization,
Thomas Gleixner, Paul E. McKenney, Linus Torvalds, Ingo Molnar
In-Reply-To: <56957D54.5000602@zytor.com>
On Tue, Jan 12, 2016 at 02:25:24PM -0800, H. Peter Anvin wrote:
> On 01/12/16 14:10, Michael S. Tsirkin wrote:
> > mb() typically uses mfence on modern x86, but a micro-benchmark shows that it's
> > 2 to 3 times slower than lock; addl $0,(%%e/rsp) that we use on older CPUs.
> >
> > So let's use the locked variant everywhere - helps keep the code simple as
> > well.
> >
> > While I was at it, I found some inconsistencies in comments in
> > arch/x86/include/asm/barrier.h
> >
> > I hope I'm not splitting this up too much - the reason is I wanted to isolate
> > the code changes (that people might want to test for performance) from comment
> > changes approved by Linus, from (so far unreviewed) comment change I came up
> > with myself.
> >
> > Lightly tested on my system.
> >
> > Michael S. Tsirkin (3):
> > x86: drop mfence in favor of lock+addl
> > x86: drop a comment left over from X86_OOSTORE
> > x86: tweak the comment about use of wmb for IO
> >
>
> I would like to get feedback from the hardware team about the
> implications of this change, first.
>
> -hpa
>
Hi hpa,
Any luck getting some feedback on this one?
Thanks,
--
MST
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-26 6:12 UTC (permalink / raw)
To: Will Deacon
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160125180234.GA26732@arm.com>
On Mon, Jan 25, 2016 at 06:02:34PM +0000, Will Deacon wrote:
> Hi Paul,
>
> On Fri, Jan 15, 2016 at 09:39:12AM -0800, Paul E. McKenney wrote:
> > On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
> > > On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
> > > > So smp_mb() provides transitivity, as do pairs of smp_store_release()
> > > > and smp_read_acquire(),
> > >
> > > But they provide different grades of transitivity, which is where all
> > > the confusion lays.
> > >
> > > smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
> > >
> > > Whereas the RCpc release+acquire is weakly so, only the two cpus
> > > involved in the handover will agree on the order.
> >
> > Good point!
> >
> > Using grace periods in place of smp_mb() also provides strong/global
> > transitivity, but also insanely high latencies. ;-)
> >
> > The patch below updates Documentation/memory-barriers.txt to define
> > local vs. global transitivity. The corresponding ppcmem litmus test
> > is included below as well.
> >
> > Should we start putting litmus tests for the various examples
> > somewhere, perhaps in a litmus-tests directory within each participating
> > architecture? I have a pile of powerpc-related litmus tests on my laptop,
> > but they probably aren't doing all that much good there.
>
> I too would like to have the litmus tests in the kernel so that we can
> refer to them from memory-barriers.txt. Ideally they wouldn't be targetted
> to a particular arch, however.
Agreed. Working on it...
> > PPC local-transitive
> > ""
> > {
> > 0:r1=1; 0:r2=u; 0:r3=v; 0:r4=x; 0:r5=y; 0:r6=z;
> > 1:r1=1; 1:r2=u; 1:r3=v; 1:r4=x; 1:r5=y; 1:r6=z;
> > 2:r1=1; 2:r2=u; 2:r3=v; 2:r4=x; 2:r5=y; 2:r6=z;
> > 3:r1=1; 3:r2=u; 3:r3=v; 3:r4=x; 3:r5=y; 3:r6=z;
> > }
> > P0 | P1 | P2 | P3 ;
> > lwz r9,0(r4) | lwz r9,0(r5) | lwz r9,0(r6) | stw r1,0(r3) ;
> > lwsync | lwsync | lwsync | sync ;
> > stw r1,0(r2) | lwz r8,0(r3) | stw r1,0(r7) | lwz r9,0(r2) ;
> > lwsync | lwz r7,0(r2) | | ;
> > stw r1,0(r5) | lwsync | | ;
> > | stw r1,0(r6) | | ;
> > exists
> > (* (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r8=0 /\ 3:r9=0) *)
> > (* (0:r9=1 /\ 1:r9=1 /\ 2:r9=1) *)
> > (* (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r7=0) *)
> > (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r7=0)
>
> i.e. we should rewrite this using READ_ONCE/WRITE_ONCE and smp_mb() etc.
Yep!
> > ------------------------------------------------------------------------
> >
> > commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
> > Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > Date: Fri Jan 15 09:30:42 2016 -0800
> >
> > documentation: Distinguish between local and global transitivity
> >
> > The introduction of smp_load_acquire() and smp_store_release() had
> > the side effect of introducing a weaker notion of transitivity:
> > The transitivity of full smp_mb() barriers is global, but that
> > of smp_store_release()/smp_load_acquire() chains is local. This
> > commit therefore introduces the notion of local transitivity and
> > gives an example.
> >
> > Reported-by: Peter Zijlstra <peterz@infradead.org>
> > Reported-by: Will Deacon <will.deacon@arm.com>
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> >
> > diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> > index c66ba46d8079..d8109ed99342 100644
> > --- a/Documentation/memory-barriers.txt
> > +++ b/Documentation/memory-barriers.txt
> > @@ -1318,8 +1318,82 @@ or a level of cache, CPU 2 might have early access to CPU 1's writes.
> > General barriers are therefore required to ensure that all CPUs agree
> > on the combined order of CPU 1's and CPU 2's accesses.
> >
> > -To reiterate, if your code requires transitivity, use general barriers
> > -throughout.
> > +General barriers provide "global transitivity", so that all CPUs will
> > +agree on the order of operations. In contrast, a chain of release-acquire
> > +pairs provides only "local transitivity", so that only those CPUs on
> > +the chain are guaranteed to agree on the combined order of the accesses.
>
> Thanks for having a go at this. I tried defining something axiomatically,
> but got stuck pretty quickly. In my scheme, I used "data-directed
> transitivity" instead of "local transitivity", since the latter seems to
> be a bit of a misnomer.
I figured that "local" meant local to the CPUs participating in the
release-acquire chain. As opposed to smp_mb() chains where the ordering
is "global" as in visible to all CPUs, whether on the chain or not.
Does that help?
> > +For example, switching to C code in deference to Herman Hollerith:
> > +
> > + int u, v, x, y, z;
> > +
> > + void cpu0(void)
> > + {
> > + r0 = smp_load_acquire(&x);
> > + WRITE_ONCE(u, 1);
> > + smp_store_release(&y, 1);
> > + }
> > +
> > + void cpu1(void)
> > + {
> > + r1 = smp_load_acquire(&y);
> > + r4 = READ_ONCE(v);
> > + r5 = READ_ONCE(u);
> > + smp_store_release(&z, 1);
> > + }
> > +
> > + void cpu2(void)
> > + {
> > + r2 = smp_load_acquire(&z);
> > + smp_store_release(&x, 1);
> > + }
> > +
> > + void cpu3(void)
> > + {
> > + WRITE_ONCE(v, 1);
> > + smp_mb();
> > + r3 = READ_ONCE(u);
> > + }
> > +
> > +Because cpu0(), cpu1(), and cpu2() participate in a local transitive
> > +chain of smp_store_release()/smp_load_acquire() pairs, the following
> > +outcome is prohibited:
> > +
> > + r0 == 1 && r1 == 1 && r2 == 1
> > +
> > +Furthermore, because of the release-acquire relationship between cpu0()
> > +and cpu1(), cpu1() must see cpu0()'s writes, so that the following
> > +outcome is prohibited:
> > +
> > + r1 == 1 && r5 == 0
> > +
> > +However, the transitivity of release-acquire is local to the participating
> > +CPUs and does not apply to cpu3(). Therefore, the following outcome
> > +is possible:
> > +
> > + r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0
>
> I think you should be completely explicit and include r5 == 1 here, too.
Good point -- I added this as an additional outcome:
r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0 && r5 == 1
> Also -- where would you add the smp_mb__after_release_acquire to fix
> (i.e. forbid) this? Immediately after cpu1()'s read of y?
That sounds plausible, but we would first have to agree on exactly
what smp_mb__after_release_acquire() did. ;-)
> > +Although cpu0(), cpu1(), and cpu2() will see their respective reads and
> > +writes in order, CPUs not involved in the release-acquire chain might
> > +well disagree on the order. This disagreement stems from the fact that
> > +the weak memory-barrier instructions used to implement smp_load_acquire()
> > +and smp_store_release() are not required to order prior stores against
> > +subsequent loads in all cases. This means that cpu3() can see cpu0()'s
> > +store to u as happening -after- cpu1()'s load from v, even though
> > +both cpu0() and cpu1() agree that these two operations occurred in the
> > +intended order.
> > +
> > +However, please keep in mind that smp_load_acquire() is not magic.
> > +In particular, it simply reads from its argument with ordering. It does
> > +-not- ensure that any particular value will be read. Therefore, the
> > +following outcome is possible:
> > +
> > + r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0
> > +
> > +Note that this outcome can happen even on a mythical sequentially
> > +consistent system where nothing is ever reordered.
>
> I'm not sure this last bit is strictly necessary. If somebody thinks that
> acquire/release involve some sort of implicit synchronisation, I think
> they may have bigger problems with memory-barriers.txt.
Agreed. But unless I add text like this occasionally, such people could
easily read through much of memory-barriers.txt and think that they did
in fact understand it. So I have to occasionally trip an assertion in
their brain. Or try to... :-/
Thanx, Paul
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-26 6:03 UTC (permalink / raw)
To: Will Deacon
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160125164242.GF22927@arm.com>
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
> On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
> > On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
> > > On Fri, Jan 15, 2016 at 09:46:12AM -0800, Paul E. McKenney wrote:
> > > > On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
> > >
> > > > > And the stuff we're confused about is how best to express the difference
> > > > > and guarantees of these two forms of transitivity and how exactly they
> > > > > interact.
> > > >
> > > > Hoping my memory-barrier.txt patch helps here...
> > >
> > > Yes, that seems a good start. But yesterday you raised the 'fun' point
> > > of two globally ordered sequences connected by a single local link.
> >
> > The conclusion that I am slowly coming to is that litmus tests should
> > not be thought of as linear chains, but rather as cycles. If you think
> > of it as a cycle, then it doesn't matter where the local link is, just
> > how many of them and how they are connected.
>
> Do you have some examples of this? I'm struggling to make it work in my
> mind, or are you talking specifically in the context of the kernel
> memory model?
Now that you mention it, maybe it would be best to keep the transitive
and non-transitive separate for the time being anyway. Just because it
might be possible to deal with does not necessarily mean that we should
be encouraging it. ;-)
> > But I will admit that there are some rather strange litmus tests that
> > challenge this cycle-centric view, for example, the one shown below.
> > It turns out that herd and ppcmem disagree on the outcome. (The Power
> > architects side with ppcmem.)
> >
> > > And I think I'm still confused on LWSYNC (in the smp_wmb case) when one
> > > of the stores looses a conflict, and if that scenario matters. If it
> > > does, we should inspect the same case for other barriers.
> >
> > Indeed. I am still working on how these should be described. My
> > current thought is to be quite conservative on what ordering is
> > actually respected, however, the current task is formalizing how
> > RCU plays with the rest of the memory model.
> >
> > Thanx, Paul
> >
> > ------------------------------------------------------------------------
> >
> > PPC Overlapping Group-B sets version 4
> > ""
> > (* When the Group-B sets from two different barriers involve instructions in
> > the same thread, within that thread one set must contain the other.
> >
> > P0 P1 P2
> > Rx=1 Wy=1 Wz=2
> > dep. lwsync lwsync
> > Ry=0 Wz=1 Wx=1
> > Rz=1
> >
> > assert(!(z=2))
> >
> > Forbidden by ppcmem, allowed by herd.
> > *)
> > {
> > 0:r1=x; 0:r2=y; 0:r3=z;
> > 1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
> > 2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
> > }
> > P0 | P1 | P2 ;
> > lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
> > xor r7,r6,r6 | lwsync | lwsync ;
> > lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
> > lwz r8,0(r3) | | ;
> >
> > exists
> > (z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
>
> That really hurts. Assuming that the "assert(!(z=2))" is actually there
> to constrain the coherence order of z to be {0->1->2}, then I think that
> this test is forbidden on arm using dmb instead of lwsync. That said, I
> also don't think the Rz=1 in P0 changes anything.
What about the smp_wmb() variant of dmb that orders only stores?
> The double negatives don't help here! (it is forbidden to guarantee that
> z is not always 2).
Yes, this is a weird one, and I don't know of any use of it.
Thanx, Paul
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-26 1:06 UTC (permalink / raw)
To: Will Deacon
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160125144133.GB22927@arm.com>
On Mon, Jan 25, 2016 at 02:41:34PM +0000, Will Deacon wrote:
> On Fri, Jan 15, 2016 at 11:28:45AM -0800, Paul E. McKenney wrote:
> > On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
> > > On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
> > > > See my earlier reply [1] (but also, your WRC Linux example looks more
> > > > like a variant on WWC and I couldn't really follow it).
> > >
> > > I will revisit my WRC Linux example. And yes, creating litmus tests
> > > that use non-fake dependencies is still a bit of an undertaking. :-/
> > > I am sure that it will seem more natural with time and experience...
> >
> > Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
> > last access from a store to a load to get WRC. Plus the levels of
> > indirection definitely didn't match up, did they?
>
> Nope, it was pretty baffling!
"It is a service that I provide." ;-)
> > struct foo {
> > struct foo *next;
> > };
> > struct foo a;
> > struct foo b;
> > struct foo c = { &a };
> > struct foo d = { &b };
> > struct foo x = { &c };
> > struct foo y = { &d };
> > struct foo *r1, *r2, *r3;
> >
> > void cpu0(void)
> > {
> > WRITE_ONCE(x.next, &y);
> > }
> >
> > void cpu1(void)
> > {
> > r1 = lockless_dereference(x.next);
> > WRITE_ONCE(r1->next, &x);
> > }
> >
> > void cpu2(void)
> > {
> > r2 = lockless_dereference(y.next);
> > r3 = READ_ONCE(r2->next);
> > }
> >
> > In this case, it is legal to end the run with:
> >
> > r1 == &y && r2 == &x && r3 == &c
> >
> > Please see below for a ppcmem litmus test.
> >
> > So, did I get it right this time? ;-)
>
> The code above looks correct to me (in that it matches WRC+addrs),
> but your litmus test:
>
> > PPC WRCnf+addrs
> > ""
> > {
> > 0:r2=x; 0:r3=y;
> > 1:r2=x; 1:r3=y;
> > 2:r2=x; 2:r3=y;
> > c=a; d=b; x=c; y=d;
> > }
> > P0 | P1 | P2 ;
> > stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
> > | stw r2,0(r3) | lwz r9,0(r8) ;
> > exists
> > (1:r8=y /\ 2:r8=x /\ 2:r9=c)
>
> Seems to be missing the address dependency on P1.
You are quite correct! How about the following?
As before, both herd and ppcmem say that the cycle is allowed, as
expected, given non-transitive ordering. To prohibit the cycle, P1
needs a suitable memory-barrier instruction.
Thanx, Paul
------------------------------------------------------------------------
PPC WRCnf+addrs
""
{
0:r2=x; 0:r3=y;
1:r2=x; 1:r3=y;
2:r2=x; 2:r3=y;
c=a; d=b; x=c; y=d;
}
P0 | P1 | P2 ;
stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
| stw r2,0(r8) | lwz r9,0(r8) ;
exists
(1:r8=y /\ 2:r8=x /\ 2:r9=c)
--
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Will Deacon @ 2016-01-25 18:02 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115173912.GU3818@linux.vnet.ibm.com>
Hi Paul,
On Fri, Jan 15, 2016 at 09:39:12AM -0800, Paul E. McKenney wrote:
> On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
> > On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
> > > So smp_mb() provides transitivity, as do pairs of smp_store_release()
> > > and smp_read_acquire(),
> >
> > But they provide different grades of transitivity, which is where all
> > the confusion lays.
> >
> > smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
> >
> > Whereas the RCpc release+acquire is weakly so, only the two cpus
> > involved in the handover will agree on the order.
>
> Good point!
>
> Using grace periods in place of smp_mb() also provides strong/global
> transitivity, but also insanely high latencies. ;-)
>
> The patch below updates Documentation/memory-barriers.txt to define
> local vs. global transitivity. The corresponding ppcmem litmus test
> is included below as well.
>
> Should we start putting litmus tests for the various examples
> somewhere, perhaps in a litmus-tests directory within each participating
> architecture? I have a pile of powerpc-related litmus tests on my laptop,
> but they probably aren't doing all that much good there.
I too would like to have the litmus tests in the kernel so that we can
refer to them from memory-barriers.txt. Ideally they wouldn't be targetted
to a particular arch, however.
> PPC local-transitive
> ""
> {
> 0:r1=1; 0:r2=u; 0:r3=v; 0:r4=x; 0:r5=y; 0:r6=z;
> 1:r1=1; 1:r2=u; 1:r3=v; 1:r4=x; 1:r5=y; 1:r6=z;
> 2:r1=1; 2:r2=u; 2:r3=v; 2:r4=x; 2:r5=y; 2:r6=z;
> 3:r1=1; 3:r2=u; 3:r3=v; 3:r4=x; 3:r5=y; 3:r6=z;
> }
> P0 | P1 | P2 | P3 ;
> lwz r9,0(r4) | lwz r9,0(r5) | lwz r9,0(r6) | stw r1,0(r3) ;
> lwsync | lwsync | lwsync | sync ;
> stw r1,0(r2) | lwz r8,0(r3) | stw r1,0(r7) | lwz r9,0(r2) ;
> lwsync | lwz r7,0(r2) | | ;
> stw r1,0(r5) | lwsync | | ;
> | stw r1,0(r6) | | ;
> exists
> (* (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r8=0 /\ 3:r9=0) *)
> (* (0:r9=1 /\ 1:r9=1 /\ 2:r9=1) *)
> (* (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r7=0) *)
> (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r7=0)
i.e. we should rewrite this using READ_ONCE/WRITE_ONCE and smp_mb() etc.
> ------------------------------------------------------------------------
>
> commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
> Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Date: Fri Jan 15 09:30:42 2016 -0800
>
> documentation: Distinguish between local and global transitivity
>
> The introduction of smp_load_acquire() and smp_store_release() had
> the side effect of introducing a weaker notion of transitivity:
> The transitivity of full smp_mb() barriers is global, but that
> of smp_store_release()/smp_load_acquire() chains is local. This
> commit therefore introduces the notion of local transitivity and
> gives an example.
>
> Reported-by: Peter Zijlstra <peterz@infradead.org>
> Reported-by: Will Deacon <will.deacon@arm.com>
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
>
> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> index c66ba46d8079..d8109ed99342 100644
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -1318,8 +1318,82 @@ or a level of cache, CPU 2 might have early access to CPU 1's writes.
> General barriers are therefore required to ensure that all CPUs agree
> on the combined order of CPU 1's and CPU 2's accesses.
>
> -To reiterate, if your code requires transitivity, use general barriers
> -throughout.
> +General barriers provide "global transitivity", so that all CPUs will
> +agree on the order of operations. In contrast, a chain of release-acquire
> +pairs provides only "local transitivity", so that only those CPUs on
> +the chain are guaranteed to agree on the combined order of the accesses.
Thanks for having a go at this. I tried defining something axiomatically,
but got stuck pretty quickly. In my scheme, I used "data-directed
transitivity" instead of "local transitivity", since the latter seems to
be a bit of a misnomer.
> +For example, switching to C code in deference to Herman Hollerith:
> +
> + int u, v, x, y, z;
> +
> + void cpu0(void)
> + {
> + r0 = smp_load_acquire(&x);
> + WRITE_ONCE(u, 1);
> + smp_store_release(&y, 1);
> + }
> +
> + void cpu1(void)
> + {
> + r1 = smp_load_acquire(&y);
> + r4 = READ_ONCE(v);
> + r5 = READ_ONCE(u);
> + smp_store_release(&z, 1);
> + }
> +
> + void cpu2(void)
> + {
> + r2 = smp_load_acquire(&z);
> + smp_store_release(&x, 1);
> + }
> +
> + void cpu3(void)
> + {
> + WRITE_ONCE(v, 1);
> + smp_mb();
> + r3 = READ_ONCE(u);
> + }
> +
> +Because cpu0(), cpu1(), and cpu2() participate in a local transitive
> +chain of smp_store_release()/smp_load_acquire() pairs, the following
> +outcome is prohibited:
> +
> + r0 == 1 && r1 == 1 && r2 == 1
> +
> +Furthermore, because of the release-acquire relationship between cpu0()
> +and cpu1(), cpu1() must see cpu0()'s writes, so that the following
> +outcome is prohibited:
> +
> + r1 == 1 && r5 == 0
> +
> +However, the transitivity of release-acquire is local to the participating
> +CPUs and does not apply to cpu3(). Therefore, the following outcome
> +is possible:
> +
> + r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0
I think you should be completely explicit and include r5 == 1 here, too.
Also -- where would you add the smp_mb__after_release_acquire to fix
(i.e. forbid) this? Immediately after cpu1()'s read of y?
> +Although cpu0(), cpu1(), and cpu2() will see their respective reads and
> +writes in order, CPUs not involved in the release-acquire chain might
> +well disagree on the order. This disagreement stems from the fact that
> +the weak memory-barrier instructions used to implement smp_load_acquire()
> +and smp_store_release() are not required to order prior stores against
> +subsequent loads in all cases. This means that cpu3() can see cpu0()'s
> +store to u as happening -after- cpu1()'s load from v, even though
> +both cpu0() and cpu1() agree that these two operations occurred in the
> +intended order.
> +
> +However, please keep in mind that smp_load_acquire() is not magic.
> +In particular, it simply reads from its argument with ordering. It does
> +-not- ensure that any particular value will be read. Therefore, the
> +following outcome is possible:
> +
> + r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0
> +
> +Note that this outcome can happen even on a mythical sequentially
> +consistent system where nothing is ever reordered.
I'm not sure this last bit is strictly necessary. If somebody thinks that
acquire/release involve some sort of implicit synchronisation, I think
they may have bigger problems with memory-barriers.txt.
Will
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Will Deacon @ 2016-01-25 16:42 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115215853.GC3818@linux.vnet.ibm.com>
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
> On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
> > On Fri, Jan 15, 2016 at 09:46:12AM -0800, Paul E. McKenney wrote:
> > > On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
> >
> > > > And the stuff we're confused about is how best to express the difference
> > > > and guarantees of these two forms of transitivity and how exactly they
> > > > interact.
> > >
> > > Hoping my memory-barrier.txt patch helps here...
> >
> > Yes, that seems a good start. But yesterday you raised the 'fun' point
> > of two globally ordered sequences connected by a single local link.
>
> The conclusion that I am slowly coming to is that litmus tests should
> not be thought of as linear chains, but rather as cycles. If you think
> of it as a cycle, then it doesn't matter where the local link is, just
> how many of them and how they are connected.
Do you have some examples of this? I'm struggling to make it work in my
mind, or are you talking specifically in the context of the kernel
memory model?
> But I will admit that there are some rather strange litmus tests that
> challenge this cycle-centric view, for example, the one shown below.
> It turns out that herd and ppcmem disagree on the outcome. (The Power
> architects side with ppcmem.)
>
> > And I think I'm still confused on LWSYNC (in the smp_wmb case) when one
> > of the stores looses a conflict, and if that scenario matters. If it
> > does, we should inspect the same case for other barriers.
>
> Indeed. I am still working on how these should be described. My
> current thought is to be quite conservative on what ordering is
> actually respected, however, the current task is formalizing how
> RCU plays with the rest of the memory model.
>
> Thanx, Paul
>
> ------------------------------------------------------------------------
>
> PPC Overlapping Group-B sets version 4
> ""
> (* When the Group-B sets from two different barriers involve instructions in
> the same thread, within that thread one set must contain the other.
>
> P0 P1 P2
> Rx=1 Wy=1 Wz=2
> dep. lwsync lwsync
> Ry=0 Wz=1 Wx=1
> Rz=1
>
> assert(!(z=2))
>
> Forbidden by ppcmem, allowed by herd.
> *)
> {
> 0:r1=x; 0:r2=y; 0:r3=z;
> 1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
> 2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
> }
> P0 | P1 | P2 ;
> lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
> xor r7,r6,r6 | lwsync | lwsync ;
> lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
> lwz r8,0(r3) | | ;
>
> exists
> (z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
That really hurts. Assuming that the "assert(!(z=2))" is actually there
to constrain the coherence order of z to be {0->1->2}, then I think that
this test is forbidden on arm using dmb instead of lwsync. That said, I
also don't think the Rz=1 in P0 changes anything.
The double negatives don't help here! (it is forbidden to guarantee that
z is not always 2).
Will
^ permalink raw reply
* [PATCH v5 2/2] virtio_balloon: Allow to resize and update the balloon stats in parallel
From: Petr Mladek @ 2016-01-25 16:38 UTC (permalink / raw)
To: Rusty Russell, Michael S. Tsirkin
Cc: Petr Mladek, Jiri Kosina, linux-kernel, virtualization, Tejun Heo,
Jeff Epler
In-Reply-To: <1453739886-29458-1-git-send-email-pmladek@suse.com>
The virtio balloon statistics are not updated when the balloon
is being resized. But it seems that both tasks could be done
in parallel.
stats_handle_request() updates the statistics in the balloon
structure and then communicates with the host.
update_balloon_stats() calls all_vm_events() that just reads
some per-CPU variables. The values might change during and
after the call but it is expected and happens even without
this patch.
update_balloon_stats() also calls si_meminfo(). It is a bit
more complex function. It too just reads some variables and
looks lock-less safe. In each case, it seems to be called
lock-less on several similar locations, e.g. from post_status()
in dm_thread_func(), or from vmballoon_send_get_target().
The communication with the host is done via a separate virtqueue,
see vb->stats_vq vs. vb->inflate_vq and vb->deflate_vq. Therefore
it could be used in parallel with fill_balloon() and leak_balloon().
This patch splits the existing work into two pieces. One is for
updating the balloon stats. The other is for resizing of the balloon.
It seems that they can be proceed in parallel without any
extra locking.
Signed-off-by: Petr Mladek <pmladek@suse.com>
---
drivers/virtio/virtio_balloon.c | 36 +++++++++++++++++++++---------------
1 file changed, 21 insertions(+), 15 deletions(-)
diff --git a/drivers/virtio/virtio_balloon.c b/drivers/virtio/virtio_balloon.c
index 2c9a92f1e525..9057cc768ca5 100644
--- a/drivers/virtio/virtio_balloon.c
+++ b/drivers/virtio/virtio_balloon.c
@@ -49,7 +49,8 @@ struct virtio_balloon {
struct virtqueue *inflate_vq, *deflate_vq, *stats_vq;
/* The balloon servicing is delegated to a freezable workqueue. */
- struct work_struct work;
+ struct work_struct update_balloon_stats_work;
+ struct work_struct update_balloon_size_work;
/* Prevent updating balloon when it is being canceled. */
spinlock_t stop_update_lock;
@@ -76,7 +77,6 @@ struct virtio_balloon {
u32 pfns[VIRTIO_BALLOON_ARRAY_PFNS_MAX];
/* Memory statistics */
- int need_stats_update;
struct virtio_balloon_stat stats[VIRTIO_BALLOON_S_NR];
/* To register callback in oom notifier call chain */
@@ -123,6 +123,7 @@ static void tell_host(struct virtio_balloon *vb, struct virtqueue *vq)
/* When host has read buffer, this completes via balloon_ack */
wait_event(vb->acked, virtqueue_get_buf(vq, &len));
+
}
static void set_page_pfns(u32 pfns[], struct page *page)
@@ -262,11 +263,9 @@ static void stats_request(struct virtqueue *vq)
{
struct virtio_balloon *vb = vq->vdev->priv;
- vb->need_stats_update = 1;
-
spin_lock(&vb->stop_update_lock);
if (!vb->stop_update)
- queue_work(system_freezable_wq, &vb->work);
+ queue_work(system_freezable_wq, &vb->update_balloon_stats_work);
spin_unlock(&vb->stop_update_lock);
}
@@ -276,7 +275,6 @@ static void stats_handle_request(struct virtio_balloon *vb)
struct scatterlist sg;
unsigned int len;
- vb->need_stats_update = 0;
update_balloon_stats(vb);
vq = vb->stats_vq;
@@ -294,7 +292,7 @@ static void virtballoon_changed(struct virtio_device *vdev)
spin_lock_irqsave(&vb->stop_update_lock, flags);
if (!vb->stop_update)
- queue_work(system_freezable_wq, &vb->work);
+ queue_work(system_freezable_wq, &vb->update_balloon_size_work);
spin_unlock_irqrestore(&vb->stop_update_lock, flags);
}
@@ -358,17 +356,24 @@ static int virtballoon_oom_notify(struct notifier_block *self,
return NOTIFY_OK;
}
-static void balloon(struct work_struct *work)
+static void update_balloon_stats_func(struct work_struct *work)
+{
+ struct virtio_balloon *vb;
+
+ vb = container_of(work, struct virtio_balloon,
+ update_balloon_stats_work);
+ stats_handle_request(vb);
+}
+
+static void update_balloon_size_func(struct work_struct *work)
{
struct virtio_balloon *vb;
s64 diff;
- vb = container_of(work, struct virtio_balloon, work);
+ vb = container_of(work, struct virtio_balloon,
+ update_balloon_size_work);
diff = towards_target(vb);
- if (vb->need_stats_update)
- stats_handle_request(vb);
-
if (diff > 0)
diff -= fill_balloon(vb, diff);
else if (diff < 0)
@@ -494,14 +499,14 @@ static int virtballoon_probe(struct virtio_device *vdev)
goto out;
}
- INIT_WORK(&vb->work, balloon);
+ INIT_WORK(&vb->update_balloon_stats_work, update_balloon_stats_func);
+ INIT_WORK(&vb->update_balloon_size_work, update_balloon_size_func);
spin_lock_init(&vb->stop_update_lock);
vb->stop_update = false;
vb->num_pages = 0;
mutex_init(&vb->balloon_lock);
init_waitqueue_head(&vb->acked);
vb->vdev = vdev;
- vb->need_stats_update = 0;
balloon_devinfo_init(&vb->vb_dev_info);
#ifdef CONFIG_BALLOON_COMPACTION
@@ -552,7 +557,8 @@ static void virtballoon_remove(struct virtio_device *vdev)
spin_lock_irq(&vb->stop_update_lock);
vb->stop_update = true;
spin_unlock_irq(&vb->stop_update_lock);
- cancel_work_sync(&vb->work);
+ cancel_work_sync(&vb->update_balloon_size_work);
+ cancel_work_sync(&vb->update_balloon_stats_work);
remove_common(vb);
kfree(vb);
--
1.8.5.6
^ permalink raw reply related
* [PATCH v5 1/2] virtio_balloon: Use a workqueue instead of "vballoon" kthread
From: Petr Mladek @ 2016-01-25 16:38 UTC (permalink / raw)
To: Rusty Russell, Michael S. Tsirkin
Cc: Petr Mladek, Jiri Kosina, linux-kernel, Petr Mladek,
virtualization, Tejun Heo, Jeff Epler
In-Reply-To: <1453739886-29458-1-git-send-email-pmladek@suse.com>
This patch moves the deferred work from the "vballoon" kthread into a
system freezable workqueue.
We do not need to maintain and run a dedicated kthread. Also the event
driven workqueues API makes the logic much easier. Especially, we do
not longer need an own wait queue, wait function, and freeze point.
The conversion is pretty straightforward. One cycle of the main loop
is put into a work. The work is queued instead of waking the kthread.
fill_balloon() and leak_balloon() have a limit for the amount of modified
pages. The work re-queues itself when necessary. For this, we make
fill_balloon() to return the number of really modified pages.
Note that leak_balloon() already did this.
virtballoon_restore() queues the work only when really needed.
The only complication is that we need to prevent queuing the work
when the balloon is being removed. It was easier before because the
kthread simply removed itself from the wait queue. We need an
extra boolean and spin lock now.
My initial idea was to use a dedicated workqueue. Michael S. Tsirkin
suggested using a system one. Tejun Heo confirmed that the system
workqueue has a pretty high concurrency level (256) by default.
Therefore we need not be afraid of too long blocking.
Signed-off-by: Petr Mladek <pmladek@suse.cz>
---
drivers/virtio/virtio_balloon.c | 108 +++++++++++++++++++---------------------
1 file changed, 51 insertions(+), 57 deletions(-)
diff --git a/drivers/virtio/virtio_balloon.c b/drivers/virtio/virtio_balloon.c
index 0c3691f46575..2c9a92f1e525 100644
--- a/drivers/virtio/virtio_balloon.c
+++ b/drivers/virtio/virtio_balloon.c
@@ -22,8 +22,7 @@
#include <linux/virtio.h>
#include <linux/virtio_balloon.h>
#include <linux/swap.h>
-#include <linux/kthread.h>
-#include <linux/freezer.h>
+#include <linux/workqueue.h>
#include <linux/delay.h>
#include <linux/slab.h>
#include <linux/module.h>
@@ -49,11 +48,12 @@ struct virtio_balloon {
struct virtio_device *vdev;
struct virtqueue *inflate_vq, *deflate_vq, *stats_vq;
- /* Where the ballooning thread waits for config to change. */
- wait_queue_head_t config_change;
+ /* The balloon servicing is delegated to a freezable workqueue. */
+ struct work_struct work;
- /* The thread servicing the balloon. */
- struct task_struct *thread;
+ /* Prevent updating balloon when it is being canceled. */
+ spinlock_t stop_update_lock;
+ bool stop_update;
/* Waiting for host to ack the pages we released. */
wait_queue_head_t acked;
@@ -135,9 +135,10 @@ static void set_page_pfns(u32 pfns[], struct page *page)
pfns[i] = page_to_balloon_pfn(page) + i;
}
-static void fill_balloon(struct virtio_balloon *vb, size_t num)
+static unsigned fill_balloon(struct virtio_balloon *vb, size_t num)
{
struct balloon_dev_info *vb_dev_info = &vb->vb_dev_info;
+ unsigned num_allocated_pages;
/* We can only do one array worth at a time. */
num = min(num, ARRAY_SIZE(vb->pfns));
@@ -162,10 +163,13 @@ static void fill_balloon(struct virtio_balloon *vb, size_t num)
adjust_managed_page_count(page, -1);
}
+ num_allocated_pages = vb->num_pfns;
/* Did we get any? */
if (vb->num_pfns != 0)
tell_host(vb, vb->inflate_vq);
mutex_unlock(&vb->balloon_lock);
+
+ return num_allocated_pages;
}
static void release_pages_balloon(struct virtio_balloon *vb)
@@ -251,14 +255,19 @@ static void update_balloon_stats(struct virtio_balloon *vb)
* with a single buffer. From that point forward, all conversations consist of
* a hypervisor request (a call to this function) which directs us to refill
* the virtqueue with a fresh stats buffer. Since stats collection can sleep,
- * we notify our kthread which does the actual work via stats_handle_request().
+ * we delegate the job to a freezable workqueue that will do the actual work via
+ * stats_handle_request().
*/
static void stats_request(struct virtqueue *vq)
{
struct virtio_balloon *vb = vq->vdev->priv;
vb->need_stats_update = 1;
- wake_up(&vb->config_change);
+
+ spin_lock(&vb->stop_update_lock);
+ if (!vb->stop_update)
+ queue_work(system_freezable_wq, &vb->work);
+ spin_unlock(&vb->stop_update_lock);
}
static void stats_handle_request(struct virtio_balloon *vb)
@@ -281,8 +290,12 @@ static void stats_handle_request(struct virtio_balloon *vb)
static void virtballoon_changed(struct virtio_device *vdev)
{
struct virtio_balloon *vb = vdev->priv;
+ unsigned long flags;
- wake_up(&vb->config_change);
+ spin_lock_irqsave(&vb->stop_update_lock, flags);
+ if (!vb->stop_update)
+ queue_work(system_freezable_wq, &vb->work);
+ spin_unlock_irqrestore(&vb->stop_update_lock, flags);
}
static inline s64 towards_target(struct virtio_balloon *vb)
@@ -345,43 +358,25 @@ static int virtballoon_oom_notify(struct notifier_block *self,
return NOTIFY_OK;
}
-static int balloon(void *_vballoon)
+static void balloon(struct work_struct *work)
{
- struct virtio_balloon *vb = _vballoon;
- DEFINE_WAIT_FUNC(wait, woken_wake_function);
-
- set_freezable();
- while (!kthread_should_stop()) {
- s64 diff;
-
- try_to_freeze();
-
- add_wait_queue(&vb->config_change, &wait);
- for (;;) {
- if ((diff = towards_target(vb)) != 0 ||
- vb->need_stats_update ||
- kthread_should_stop() ||
- freezing(current))
- break;
- wait_woken(&wait, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
- }
- remove_wait_queue(&vb->config_change, &wait);
+ struct virtio_balloon *vb;
+ s64 diff;
- if (vb->need_stats_update)
- stats_handle_request(vb);
- if (diff > 0)
- fill_balloon(vb, diff);
- else if (diff < 0)
- leak_balloon(vb, -diff);
- update_balloon_size(vb);
+ vb = container_of(work, struct virtio_balloon, work);
+ diff = towards_target(vb);
- /*
- * For large balloon changes, we could spend a lot of time
- * and always have work to do. Be nice if preempt disabled.
- */
- cond_resched();
- }
- return 0;
+ if (vb->need_stats_update)
+ stats_handle_request(vb);
+
+ if (diff > 0)
+ diff -= fill_balloon(vb, diff);
+ else if (diff < 0)
+ diff += leak_balloon(vb, -diff);
+ update_balloon_size(vb);
+
+ if (diff)
+ queue_work(system_freezable_wq, work);
}
static int init_vqs(struct virtio_balloon *vb)
@@ -499,9 +494,11 @@ static int virtballoon_probe(struct virtio_device *vdev)
goto out;
}
+ INIT_WORK(&vb->work, balloon);
+ spin_lock_init(&vb->stop_update_lock);
+ vb->stop_update = false;
vb->num_pages = 0;
mutex_init(&vb->balloon_lock);
- init_waitqueue_head(&vb->config_change);
init_waitqueue_head(&vb->acked);
vb->vdev = vdev;
vb->need_stats_update = 0;
@@ -523,16 +520,8 @@ static int virtballoon_probe(struct virtio_device *vdev)
virtio_device_ready(vdev);
- vb->thread = kthread_run(balloon, vb, "vballoon");
- if (IS_ERR(vb->thread)) {
- err = PTR_ERR(vb->thread);
- goto out_del_vqs;
- }
-
return 0;
-out_del_vqs:
- unregister_oom_notifier(&vb->nb);
out_oom_notify:
vdev->config->del_vqs(vdev);
out_free_vb:
@@ -559,7 +548,12 @@ static void virtballoon_remove(struct virtio_device *vdev)
struct virtio_balloon *vb = vdev->priv;
unregister_oom_notifier(&vb->nb);
- kthread_stop(vb->thread);
+
+ spin_lock_irq(&vb->stop_update_lock);
+ vb->stop_update = true;
+ spin_unlock_irq(&vb->stop_update_lock);
+ cancel_work_sync(&vb->work);
+
remove_common(vb);
kfree(vb);
}
@@ -570,10 +564,9 @@ static int virtballoon_freeze(struct virtio_device *vdev)
struct virtio_balloon *vb = vdev->priv;
/*
- * The kthread is already frozen by the PM core before this
+ * The workqueue is already frozen by the PM core before this
* function is called.
*/
-
remove_common(vb);
return 0;
}
@@ -589,7 +582,8 @@ static int virtballoon_restore(struct virtio_device *vdev)
virtio_device_ready(vdev);
- fill_balloon(vb, towards_target(vb));
+ if (towards_target(vb))
+ virtballoon_changed(vdev);
update_balloon_size(vb);
return 0;
}
--
1.8.5.6
^ permalink raw reply related
* [PATCH v5 0/2] virtio_balloon: Conversion to workqueue + parallel stats
From: Petr Mladek @ 2016-01-25 16:38 UTC (permalink / raw)
To: Rusty Russell, Michael S. Tsirkin
Cc: Petr Mladek, Jiri Kosina, linux-kernel, virtualization, Tejun Heo,
Jeff Epler
The previous version did not prevent updating the balloon when it was
being removed. There was an idea to update the stats in a separate work
and cancel it after the config reset. But this does not seem to work.
The code for updating the stats communicates with the host. IMHO, it
should not run after the reset (flushing buffers). Therefore I decided
to use a boolean value and a spin lock (inspired by virtio_scsi).
Michael S. Tsirkin suggested that it would have been nice to split the work
and updated the stats in parallel. I did a lot of investigation and it seemed
that we did not need any extra sychronization. Anyway, I rather made the split
in a separate patch. See the patch description for more details.
Changes against v4:
+ removed fix of the balloon restore code; it was false alarm;
freezer waken the kthread and it restored the balloon later
+ added a spin lock to prevent updating the balloon when being removed
+ split the work into two; it allows to update stats even
when the balloon is being resized
Changes against v3:
+ rebased on 4.4-rc3
+ call cancel_work_sync() when removing the balloon
+ do not queue the work from fill_balloon() and leak_balloon()
because they are called also independently from the workqueue,
e.g. remove_common(), virtballoon_oom_notify(). Re-queue
the work from the work function when necessary.
Changes against v2:
+ Use system_freezable_wq instead of an allocated one
and move INIT_WORK() higher in virtballoon_probe().
+ Fix typos in the commit message.
Changes against v1:
+ More elegant detection of the pending work in fill_balloon() and
leak_balloon(). It still needs to keep the original requested number
of pages but it does not add any extra boolean variable.
+ Remove WQ_MEM_RECLAIM workqueue parameter. If I get it correctly,
this is possible because the code manipulates memory but it is not
used in the memory reclaim path.
+ initialize the work item before allocation the workqueue
Just for record, the discussion about the previous version can be found
at http://thread.gmane.org/gmane.linux.kernel/2100306
Petr Mladek (2):
virtio_balloon: Use a workqueue instead of "vballoon" kthread
virtio_balloon: Allow to resize and update the balloon stats in
parallel
drivers/virtio/virtio_balloon.c | 122 ++++++++++++++++++++--------------------
1 file changed, 61 insertions(+), 61 deletions(-)
--
1.8.5.6
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Will Deacon @ 2016-01-25 14:41 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115192845.GA12510@linux.vnet.ibm.com>
On Fri, Jan 15, 2016 at 11:28:45AM -0800, Paul E. McKenney wrote:
> On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
> > On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
> > > See my earlier reply [1] (but also, your WRC Linux example looks more
> > > like a variant on WWC and I couldn't really follow it).
> >
> > I will revisit my WRC Linux example. And yes, creating litmus tests
> > that use non-fake dependencies is still a bit of an undertaking. :-/
> > I am sure that it will seem more natural with time and experience...
>
> Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
> last access from a store to a load to get WRC. Plus the levels of
> indirection definitely didn't match up, did they?
Nope, it was pretty baffling!
> struct foo {
> struct foo *next;
> };
> struct foo a;
> struct foo b;
> struct foo c = { &a };
> struct foo d = { &b };
> struct foo x = { &c };
> struct foo y = { &d };
> struct foo *r1, *r2, *r3;
>
> void cpu0(void)
> {
> WRITE_ONCE(x.next, &y);
> }
>
> void cpu1(void)
> {
> r1 = lockless_dereference(x.next);
> WRITE_ONCE(r1->next, &x);
> }
>
> void cpu2(void)
> {
> r2 = lockless_dereference(y.next);
> r3 = READ_ONCE(r2->next);
> }
>
> In this case, it is legal to end the run with:
>
> r1 == &y && r2 == &x && r3 == &c
>
> Please see below for a ppcmem litmus test.
>
> So, did I get it right this time? ;-)
The code above looks correct to me (in that it matches WRC+addrs),
but your litmus test:
> PPC WRCnf+addrs
> ""
> {
> 0:r2=x; 0:r3=y;
> 1:r2=x; 1:r3=y;
> 2:r2=x; 2:r3=y;
> c=a; d=b; x=c; y=d;
> }
> P0 | P1 | P2 ;
> stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
> | stw r2,0(r3) | lwz r9,0(r8) ;
> exists
> (1:r8=y /\ 2:r8=x /\ 2:r9=c)
Seems to be missing the address dependency on P1.
Will
^ permalink raw reply
* Re: [PATCH V2 0/3] basic busy polling support for vhost_net
From: Jason Wang @ 2016-01-25 8:41 UTC (permalink / raw)
To: Michael Rapoport
Cc: netdev, virtualization, linux-kernel, kvm, Michael S. Tsirkin
In-Reply-To: <OF39FCBD95.AC4D3DD2-ONC2257F45.002772D2-C2257F45.002BD839@il.ibm.com>
On 01/25/2016 03:58 PM, Michael Rapoport wrote:
> (restored 'CC, sorry for dropping it originally, Notes is still hard
> for me)
>
> > Jason Wang <jasowang@redhat.com> wrote on 01/25/2016 05:00:05 AM:
> > On 01/24/2016 05:00 PM, Mike Rapoport wrote:
> > > Hi Jason,
> > >
> > >> Jason Wang <jasowang <at> redhat.com> writes:
> > >>
> > >> Hi all:
> > >>
> > >> This series tries to add basic busy polling for vhost net. The
> idea is
> > >> simple: at the end of tx/rx processing, busy polling for new tx added
> > >> descriptor and rx receive socket for a while.
> > > There were several conciens Michael raised on the Razya's attempt
> to add
> > > polling to vhost-net ([1], [2]). Some of them seem relevant for these
> > > patches as well:
> > >
> > > - What happens in overcommit scenarios?
> >
> > We have an optimization here: busy polling will end if more than one
> > processes is runnable on local cpu. This was done by checking
> > single_task_running() in each iteration. So at the worst case, busy
> > polling should be as fast as or only a minor regression compared to
> > normal case. You can see this from the last test result.
> >
> > > - Have you checked the effect of polling on some macro benchmarks?
> >
> > I'm not sure I get the question. Cover letters shows some benchmark
> > result of netperf. What do you mean by "macro benchmarks"?
>
> Back then, when Razya posted her polling implementation, Michael had
> concern about the macro effect ([3]),
> so I was wondering if this concern is also valid for your implementation.
> Now, after I've reread your changes, I think it's not that relevant...
More benchmarks is good, but lots of kernel patches were accepted only
with simple netperf results. Anyway busy polling is disabled by default,
will try to do macro benchmark in the future if I had time.
>
>
> > >> The maximum number of time (in us) could be spent on busy polling was
> > >> specified ioctl.
> > > Although ioctl is definitely more appropriate interface to allow
> user to
> > > tune polling, it's still not clear for me how *end user* will
> interact with
> > > it and how easy it would be for him/her.
> >
> > There will be qemu part of the codes for end user. E.g. a vhost_poll_us
> > parameter for tap like:
> >
> > -netdev tap,id=hn0,vhost=on,vhost_pull_us=20
>
> Not strictly related, I'd like to give a try to polling + vhost thread
> sharing and polling + workqueues.
> Do you mind sharing the scripts you used to test the polling?
Sure, it was a subtest of autotest[1].
[1]
https://github.com/autotest/tp-qemu/blob/7cf589b490aff7511eccbf2e1336ecf8d9fa9cb9/generic/tests/netperf.py
>
>
> Thanks,
> Mike.
>
> > Thanks
> >
> > >
> > > [1] http://thread.gmane.org/gmane.linux.kernel/1765593
> > > [2] http://thread.gmane.org/gmane.comp.emulators.kvm.devel/131343
> > >
> > > --
> > > Sincerely yours,
> > > Mike.
> > >
>
> [3] https://www.mail-archive.com/kvm@vger.kernel.org/msg109703.html
^ permalink raw reply
* Re: [PATCH V2 0/3] basic busy polling support for vhost_net
From: Michael Rapoport @ 2016-01-25 7:58 UTC (permalink / raw)
To: Jason Wang; +Cc: netdev, virtualization, linux-kernel, kvm, Michael S. Tsirkin
In-Reply-To: <56A58FB5.8020101@redhat.com>
[-- Attachment #1.1: Type: text/plain, Size: 2411 bytes --]
(restored 'CC, sorry for dropping it originally, Notes is still hard for
me)
> Jason Wang <jasowang@redhat.com> wrote on 01/25/2016 05:00:05 AM:
> On 01/24/2016 05:00 PM, Mike Rapoport wrote:
> > Hi Jason,
> >
> >> Jason Wang <jasowang <at> redhat.com> writes:
> >>
> >> Hi all:
> >>
> >> This series tries to add basic busy polling for vhost net. The idea
is
> >> simple: at the end of tx/rx processing, busy polling for new tx added
> >> descriptor and rx receive socket for a while.
> > There were several conciens Michael raised on the Razya's attempt to
add
> > polling to vhost-net ([1], [2]). Some of them seem relevant for these
> > patches as well:
> >
> > - What happens in overcommit scenarios?
>
> We have an optimization here: busy polling will end if more than one
> processes is runnable on local cpu. This was done by checking
> single_task_running() in each iteration. So at the worst case, busy
> polling should be as fast as or only a minor regression compared to
> normal case. You can see this from the last test result.
>
> > - Have you checked the effect of polling on some macro benchmarks?
>
> I'm not sure I get the question. Cover letters shows some benchmark
> result of netperf. What do you mean by "macro benchmarks"?
Back then, when Razya posted her polling implementation, Michael had
concern about the macro effect ([3]),
so I was wondering if this concern is also valid for your implementation.
Now, after I've reread your changes, I think it's not that relevant...
> >> The maximum number of time (in us) could be spent on busy polling was
> >> specified ioctl.
> > Although ioctl is definitely more appropriate interface to allow user
to
> > tune polling, it's still not clear for me how *end user* will interact
with
> > it and how easy it would be for him/her.
>
> There will be qemu part of the codes for end user. E.g. a vhost_poll_us
> parameter for tap like:
>
> -netdev tap,id=hn0,vhost=on,vhost_pull_us=20
Not strictly related, I'd like to give a try to polling + vhost thread
sharing and polling + workqueues.
Do you mind sharing the scripts you used to test the polling?
Thanks,
Mike.
> Thanks
>
> >
> > [1] http://thread.gmane.org/gmane.linux.kernel/1765593
> > [2] http://thread.gmane.org/gmane.comp.emulators.kvm.devel/131343
> >
> > --
> > Sincerely yours,
> > Mike.
> >
[3] https://www.mail-archive.com/kvm@vger.kernel.org/msg109703.html
[-- Attachment #1.2: Type: text/html, Size: 3689 bytes --]
[-- Attachment #2: Type: text/plain, Size: 183 bytes --]
_______________________________________________
Virtualization mailing list
Virtualization@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
^ permalink raw reply
* Re: [PATCH] tools/virtio: add ringtest utilities
From: Cornelia Huck @ 2016-01-22 12:53 UTC (permalink / raw)
To: Michael S. Tsirkin; +Cc: linux-kernel, virtualization
In-Reply-To: <1453380639-10459-1-git-send-email-mst@redhat.com>
On Thu, 21 Jan 2016 14:52:32 +0200
"Michael S. Tsirkin" <mst@redhat.com> wrote:
> +#if defined(__x86_64__) || defined(__i386__)
> +#include "x86intrin.h"
> +
> +static inline void wait_cycles(unsigned long long cycles)
> +{
> + unsigned long long t;
> +
> + t = __rdtsc();
> + while (__rdtsc() - t < cycles) {}
> +}
> +
> +#define VMEXIT_CYCLES 500
> +#define VMENTRY_CYCLES 500
#elif defined(__s390x__)
static inline void wait_cycles(unsigned long long cycles)
{
asm volatile("0: brctg %0,0b" : : "d" (cycles));
}
/* tweak me */
#define VMEXIT_CYCLES 200
#define VMENTRY_CYCLES 200
Values are probably off...
> +
> +#else
> +static inline void wait_cycles(unsigned long long cycles)
> +{
> + _Exit(5);
> +}
> +#define VMEXIT_CYCLES 0
> +#define VMENTRY_CYCLES 0
> +#endif
> +/* Compiler barrier - similar to what Linux uses */
> +#define barrier() asm volatile("" ::: "memory")
> +
> +/* Is there a portable way to do this? */
> +#if defined(__x86_64__) || defined(__i386__)
> +#define cpu_relax() asm ("rep; nop" ::: "memory")
> +#else
> +#define cpu_relax() assert(0)
Fall back to barrier() instead?
> +#endif
> diff --git a/tools/virtio/ringtest/run-on-all.sh b/tools/virtio/ringtest/run-on-all.sh
> new file mode 100755
> index 0000000..52b0f71
> --- /dev/null
> +++ b/tools/virtio/ringtest/run-on-all.sh
> @@ -0,0 +1,24 @@
> +#!/bin/sh
> +
> +#use last CPU for host. Why not the first?
> +#many devices tend to use cpu0 by default so
> +#it tends to be busier
> +HOST_AFFINITY=$(cd /dev/cpu; ls|grep -v '[a-z]'|sort -n|tail -1)
> +
> +#run command on all cpus
> +for cpu in $(cd /dev/cpu; ls|grep -v '[a-z]'|sort -n);
How portable is /dev/cpu/? Maybe look in sysfs instead?
> +do
> + #Don't run guest and host on same CPU
> + #It actually works ok if using signalling
> + if
> + (echo "$@" | grep -e "--sleep" > /dev/null) || \
> + test $HOST_AFFINITY '!=' $cpu
> + then
> + echo "GUEST AFFINITY $cpu"
> + "$@" --host-affinity $HOST_AFFINITY --guest-affinity $cpu
> + fi
> +done
> +echo "NO GUEST AFFINITY"
> +"$@" --host-affinity $HOST_AFFINITY
> +echo "NO AFFINITY"
> +"$@"
It did not die on me for a basic (affinityless) run on s390. Let's see
if I find time to look at the actual ring code next week.
^ permalink raw reply
* Re: [PATCH V2 3/3] vhost_net: basic polling support
From: Jason Wang @ 2016-01-22 5:59 UTC (permalink / raw)
To: Michael S. Tsirkin; +Cc: netdev, linux-kernel, kvm, virtualization
In-Reply-To: <20160120143524.GA27168@redhat.com>
On 01/20/2016 10:35 PM, Michael S. Tsirkin wrote:
> On Tue, Dec 01, 2015 at 02:39:45PM +0800, Jason Wang wrote:
>> This patch tries to poll for new added tx buffer or socket receive
>> queue for a while at the end of tx/rx processing. The maximum time
>> spent on polling were specified through a new kind of vring ioctl.
>>
>> Signed-off-by: Jason Wang <jasowang@redhat.com>
>> ---
>> drivers/vhost/net.c | 72 ++++++++++++++++++++++++++++++++++++++++++----
>> drivers/vhost/vhost.c | 15 ++++++++++
>> drivers/vhost/vhost.h | 1 +
>> include/uapi/linux/vhost.h | 11 +++++++
>> 4 files changed, 94 insertions(+), 5 deletions(-)
>>
>> diff --git a/drivers/vhost/net.c b/drivers/vhost/net.c
>> index 9eda69e..ce6da77 100644
>> --- a/drivers/vhost/net.c
>> +++ b/drivers/vhost/net.c
>> @@ -287,6 +287,41 @@ static void vhost_zerocopy_callback(struct ubuf_info *ubuf, bool success)
>> rcu_read_unlock_bh();
>> }
>>
>> +static inline unsigned long busy_clock(void)
>> +{
>> + return local_clock() >> 10;
>> +}
>> +
>> +static bool vhost_can_busy_poll(struct vhost_dev *dev,
>> + unsigned long endtime)
>> +{
>> + return likely(!need_resched()) &&
>> + likely(!time_after(busy_clock(), endtime)) &&
>> + likely(!signal_pending(current)) &&
>> + !vhost_has_work(dev) &&
>> + single_task_running();
>> +}
>> +
>> +static int vhost_net_tx_get_vq_desc(struct vhost_net *net,
>> + struct vhost_virtqueue *vq,
>> + struct iovec iov[], unsigned int iov_size,
>> + unsigned int *out_num, unsigned int *in_num)
>> +{
>> + unsigned long uninitialized_var(endtime);
>> +
>> + if (vq->busyloop_timeout) {
>> + preempt_disable();
>> + endtime = busy_clock() + vq->busyloop_timeout;
>> + while (vhost_can_busy_poll(vq->dev, endtime) &&
>> + !vhost_vq_more_avail(vq->dev, vq))
>> + cpu_relax();
>> + preempt_enable();
>> + }
> Isn't there a way to call all this after vhost_get_vq_desc?
We can.
> First, this will reduce the good path overhead as you
> won't have to play with timers and preemption.
For good path, yes.
>
> Second, this will reduce the chance of a pagefault on avail ring read.
Yes.
>
>> +
>> + return vhost_get_vq_desc(vq, vq->iov, ARRAY_SIZE(vq->iov),
>> + out_num, in_num, NULL, NULL);
>> +}
>> +
>> /* Expects to be always run from workqueue - which acts as
>> * read-size critical section for our kind of RCU. */
>> static void handle_tx(struct vhost_net *net)
>> @@ -331,10 +366,9 @@ static void handle_tx(struct vhost_net *net)
>> % UIO_MAXIOV == nvq->done_idx))
>> break;
>>
>> - head = vhost_get_vq_desc(vq, vq->iov,
>> - ARRAY_SIZE(vq->iov),
>> - &out, &in,
>> - NULL, NULL);
>> + head = vhost_net_tx_get_vq_desc(net, vq, vq->iov,
>> + ARRAY_SIZE(vq->iov),
>> + &out, &in);
>> /* On error, stop handling until the next kick. */
>> if (unlikely(head < 0))
>> break;
>> @@ -435,6 +469,34 @@ static int peek_head_len(struct sock *sk)
>> return len;
>> }
>>
>> +static int vhost_net_peek_head_len(struct vhost_net *net, struct sock *sk)
> Need a hint that it's rx related in the name.
Ok.
>
>> +{
>> + struct vhost_net_virtqueue *nvq = &net->vqs[VHOST_NET_VQ_TX];
>> + struct vhost_virtqueue *vq = &nvq->vq;
>> + unsigned long uninitialized_var(endtime);
>> +
>> + if (vq->busyloop_timeout) {
>> + mutex_lock(&vq->mutex);
> This appears to be called under vq mutex in handle_rx.
> So how does this work then?
This is tx mutex, an optimization here: both rx socket and tx ring is
polled. So there's no need to tx notification anymore. This can save
lots of vmexits.
>
>
>> + vhost_disable_notify(&net->dev, vq);
> This appears to be called after disable notify
> in handle_rx - so why disable here again?
It disable the tx notification instead of rx.
>
>> +
>> + preempt_disable();
>> + endtime = busy_clock() + vq->busyloop_timeout;
>> +
>> + while (vhost_can_busy_poll(&net->dev, endtime) &&
>> + skb_queue_empty(&sk->sk_receive_queue) &&
>> + !vhost_vq_more_avail(&net->dev, vq))
>> + cpu_relax();
> This seems to mix in several items.
> RX queue is normally not empty. I don't think
> we need to poll for that.
> So IMHO we only need to poll for sk_receive_queue really.
Same as above, tx virt queue is being polled here.
>
>> +
>> + preempt_enable();
>> +
>> + if (vhost_enable_notify(&net->dev, vq))
>> + vhost_poll_queue(&vq->poll);
> But vhost_enable_notify returns true on queue not empty.
> So in fact this will requeue on good path -
> does not make sense to me.
And still the same, it enables tx notification and eliminate the window
if a new tx buffer is available.
>
>> + mutex_unlock(&vq->mutex);
>> + }
>> +
> Same comment as for get vq desc here: don't slow
> down the good path.
>
>> + return peek_head_len(sk);
ok.
>> +}
>> +
>> /* This is a multi-buffer version of vhost_get_desc, that works if
>> * vq has read descriptors only.
>> * @vq - the relevant virtqueue
>> @@ -553,7 +615,7 @@ static void handle_rx(struct vhost_net *net)
>> vq->log : NULL;
>> mergeable = vhost_has_feature(vq, VIRTIO_NET_F_MRG_RXBUF);
>>
>> - while ((sock_len = peek_head_len(sock->sk))) {
>> + while ((sock_len = vhost_net_peek_head_len(net, sock->sk))) {
>> sock_len += sock_hlen;
>> vhost_len = sock_len + vhost_hlen;
>> headcount = get_rx_bufs(vq, vq->heads, vhost_len,
>> diff --git a/drivers/vhost/vhost.c b/drivers/vhost/vhost.c
>> index 4f45a03..b8ca873 100644
>> --- a/drivers/vhost/vhost.c
>> +++ b/drivers/vhost/vhost.c
>> @@ -285,6 +285,7 @@ static void vhost_vq_reset(struct vhost_dev *dev,
>> vq->memory = NULL;
>> vq->is_le = virtio_legacy_is_little_endian();
>> vhost_vq_reset_user_be(vq);
>> + vq->busyloop_timeout = 0;
>> }
>>
>> static int vhost_worker(void *data)
>> @@ -747,6 +748,7 @@ long vhost_vring_ioctl(struct vhost_dev *d, int ioctl, void __user *argp)
>> struct vhost_vring_state s;
>> struct vhost_vring_file f;
>> struct vhost_vring_addr a;
>> + struct vhost_vring_busyloop_timeout t;
>> u32 idx;
>> long r;
>>
>> @@ -919,6 +921,19 @@ long vhost_vring_ioctl(struct vhost_dev *d, int ioctl, void __user *argp)
>> case VHOST_GET_VRING_ENDIAN:
>> r = vhost_get_vring_endian(vq, idx, argp);
>> break;
>> + case VHOST_SET_VRING_BUSYLOOP_TIMEOUT:
>> + if (copy_from_user(&t, argp, sizeof(t))) {
>> + r = -EFAULT;
>> + break;
>> + }
>> + vq->busyloop_timeout = t.timeout;
>> + break;
>> + case VHOST_GET_VRING_BUSYLOOP_TIMEOUT:
>> + t.index = idx;
>> + t.timeout = vq->busyloop_timeout;
>> + if (copy_to_user(argp, &t, sizeof(t)))
>> + r = -EFAULT;
>> + break;
>> default:
>> r = -ENOIOCTLCMD;
>> }
>> diff --git a/drivers/vhost/vhost.h b/drivers/vhost/vhost.h
>> index 2f3c57c..4b7d4fa 100644
>> --- a/drivers/vhost/vhost.h
>> +++ b/drivers/vhost/vhost.h
>> @@ -115,6 +115,7 @@ struct vhost_virtqueue {
>> /* Ring endianness requested by userspace for cross-endian support. */
>> bool user_be;
>> #endif
>> + u32 busyloop_timeout;
>> };
>>
>> struct vhost_dev {
>> diff --git a/include/uapi/linux/vhost.h b/include/uapi/linux/vhost.h
>> index ab373191..eaf6c33 100644
>> --- a/include/uapi/linux/vhost.h
>> +++ b/include/uapi/linux/vhost.h
>> @@ -27,6 +27,11 @@ struct vhost_vring_file {
>>
>> };
>>
>> +struct vhost_vring_busyloop_timeout {
>> + unsigned int index;
>> + unsigned int timeout;
>> +};
>> +
> So why not reuse vhost_vring_state then?
Good idea.
>
>
>
>> struct vhost_vring_addr {
>> unsigned int index;
>> /* Option flags. */
>> @@ -126,6 +131,12 @@ struct vhost_memory {
>> #define VHOST_SET_VRING_CALL _IOW(VHOST_VIRTIO, 0x21, struct vhost_vring_file)
>> /* Set eventfd to signal an error */
>> #define VHOST_SET_VRING_ERR _IOW(VHOST_VIRTIO, 0x22, struct vhost_vring_file)
>> +/* Set busy loop timeout */
> Units?
Will add this. (us).
>
>> +#define VHOST_SET_VRING_BUSYLOOP_TIMEOUT _IOW(VHOST_VIRTIO, 0x23, \
>> + struct vhost_vring_busyloop_timeout)
>> +/* Get busy loop timeout */
>> +#define VHOST_GET_VRING_BUSYLOOP_TIMEOUT _IOW(VHOST_VIRTIO, 0x24, \
>> + struct vhost_vring_busyloop_timeout)
>>
>> /* VHOST_NET specific defines */
>>
>> --
>> 2.5.0
> --
> To unsubscribe from this list: send the line "unsubscribe kvm" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
^ permalink raw reply
* Re: [PATCH V2 2/3] vhost: introduce vhost_vq_more_avail()
From: Jason Wang @ 2016-01-22 5:43 UTC (permalink / raw)
To: Michael S. Tsirkin; +Cc: netdev, linux-kernel, kvm, virtualization
In-Reply-To: <20160120160400-mutt-send-email-mst@redhat.com>
On 01/20/2016 10:09 PM, Michael S. Tsirkin wrote:
> On Tue, Dec 01, 2015 at 02:39:44PM +0800, Jason Wang wrote:
>> Signed-off-by: Jason Wang <jasowang@redhat.com>
> Wow new API with no comments anywhere, and no
> commit log to say what it's good for.
> Want to know what it does and whether
> it's correct? You have to read the next patch.
>
> So what is the point of splitting it out?
> It's confusing, and in fact it made you
> miss a bug.
Ok, will add comments to explain the function.
>
>> ---
>> drivers/vhost/vhost.c | 13 +++++++++++++
>> drivers/vhost/vhost.h | 1 +
>> 2 files changed, 14 insertions(+)
>>
>> diff --git a/drivers/vhost/vhost.c b/drivers/vhost/vhost.c
>> index 163b365..4f45a03 100644
>> --- a/drivers/vhost/vhost.c
>> +++ b/drivers/vhost/vhost.c
>> @@ -1633,6 +1633,19 @@ void vhost_add_used_and_signal_n(struct vhost_dev *dev,
>> }
>> EXPORT_SYMBOL_GPL(vhost_add_used_and_signal_n);
>>
>> +bool vhost_vq_more_avail(struct vhost_dev *dev, struct vhost_virtqueue *vq)
>> +{
>> + __virtio16 avail_idx;
>> + int r;
>> +
>> + r = __get_user(avail_idx, &vq->avail->idx);
>> + if (r)
>> + return false;
> So the result is that if the page is not present,
> you return false (empty ring) and the
> caller will busy wait with preempt disabled.
> Nasty.
>
> So it should return something that breaks
> the loop, and this means it should have
> a different name for the return code
> to make sense.
>
> Maybe reverse the polarity: vhost_vq_avail_empty?
> And add a comment saying we can't be sure ring
> is empty so return false.
Sounds good, will do this.
>
>> +
>> + return vhost16_to_cpu(vq, avail_idx) != vq->avail_idx;
>> +}
>> +EXPORT_SYMBOL_GPL(vhost_vq_more_avail);
>> +
>> /* OK, now we need to know about added descriptors. */
>> bool vhost_enable_notify(struct vhost_dev *dev, struct vhost_virtqueue *vq)
>> {
>> diff --git a/drivers/vhost/vhost.h b/drivers/vhost/vhost.h
>> index 43284ad..2f3c57c 100644
>> --- a/drivers/vhost/vhost.h
>> +++ b/drivers/vhost/vhost.h
>> @@ -159,6 +159,7 @@ void vhost_add_used_and_signal_n(struct vhost_dev *, struct vhost_virtqueue *,
>> struct vring_used_elem *heads, unsigned count);
>> void vhost_signal(struct vhost_dev *, struct vhost_virtqueue *);
>> void vhost_disable_notify(struct vhost_dev *, struct vhost_virtqueue *);
>> +bool vhost_vq_more_avail(struct vhost_dev *, struct vhost_virtqueue *);
>> bool vhost_enable_notify(struct vhost_dev *, struct vhost_virtqueue *);
>>
>> int vhost_log_write(struct vhost_virtqueue *vq, struct vhost_log *log,
>> --
>> 2.5.0
> --
> To unsubscribe from this list: send the line "unsubscribe kvm" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
^ permalink raw reply
* Re: virtio ring layout changes for optimal single-stream performance
From: Michael S. Tsirkin @ 2016-01-21 19:03 UTC (permalink / raw)
To: Cornelia Huck
Cc: virtio-dev, kvm, dev, linux-kernel, qemu-devel, Xie, Huawei,
virtio, virtualization
In-Reply-To: <20160121163836.1091943d.cornelia.huck@de.ibm.com>
On Thu, Jan 21, 2016 at 04:38:36PM +0100, Cornelia Huck wrote:
> On Thu, 21 Jan 2016 15:39:26 +0200
> "Michael S. Tsirkin" <mst@redhat.com> wrote:
>
> > Hi all!
> > I have been experimenting with alternative virtio ring layouts,
> > in order to speed up single stream performance.
> >
> > I have just posted a benchmark I wrote for the purpose, and a (partial)
> > alternative layout implementation. This achieves 20-40% reduction in
> > virtio overhead in the (default) polling mode.
> >
> > http://article.gmane.org/gmane.linux.kernel.virtualization/26889
> >
> > The layout is trying to be as simple as possible, to reduce
> > the number of cache lines bouncing between CPUs.
>
> Some kind of diagram or textual description would really help to review
> this.
>
> >
> > For benchmarking, the idea is to emulate virtio in user-space,
> > artificially adding overhead for e.g. signalling to match what happens
> > in case of a VM.
>
> Hm... is this overhead comparable enough between different platform so
> that you can get a halfway realistic scenario?
On x86 is seems pretty stable.
It's a question of setting VMEXIT_CYCLES and VMENTRY_CYCLES correctly.
> What about things like
> endianness conversions?
I didn't bother with them yet.
> >
> > I'd be very curious to get feedback on this, in particular, some people
> > discussed using vectored operations to format virtio ring - would it
> > conflict with this work?
> >
> > You are all welcome to post enhancements or more layout alternatives as
> > patches.
>
> Let me see if I can find time to experiment a bit.
^ permalink raw reply
* Re: virtio ring layout changes for optimal single-stream performance
From: Cornelia Huck @ 2016-01-21 15:38 UTC (permalink / raw)
To: Michael S. Tsirkin
Cc: virtio-dev, kvm, dev, linux-kernel, qemu-devel, Xie, Huawei,
virtio, virtualization
In-Reply-To: <20160121145418-mutt-send-email-mst@redhat.com>
On Thu, 21 Jan 2016 15:39:26 +0200
"Michael S. Tsirkin" <mst@redhat.com> wrote:
> Hi all!
> I have been experimenting with alternative virtio ring layouts,
> in order to speed up single stream performance.
>
> I have just posted a benchmark I wrote for the purpose, and a (partial)
> alternative layout implementation. This achieves 20-40% reduction in
> virtio overhead in the (default) polling mode.
>
> http://article.gmane.org/gmane.linux.kernel.virtualization/26889
>
> The layout is trying to be as simple as possible, to reduce
> the number of cache lines bouncing between CPUs.
Some kind of diagram or textual description would really help to review
this.
>
> For benchmarking, the idea is to emulate virtio in user-space,
> artificially adding overhead for e.g. signalling to match what happens
> in case of a VM.
Hm... is this overhead comparable enough between different platform so
that you can get a halfway realistic scenario? What about things like
endianness conversions?
>
> I'd be very curious to get feedback on this, in particular, some people
> discussed using vectored operations to format virtio ring - would it
> conflict with this work?
>
> You are all welcome to post enhancements or more layout alternatives as
> patches.
Let me see if I can find time to experiment a bit.
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox