* Re: [PATCH linux-rcu] docs/litmus-tests: add BPF ringbuf MPSC litmus tests [not found] <20200528062408.547149-1-andriin@fb.com> @ 2020-05-28 22:54 ` Joel Fernandes 2020-05-29 5:50 ` Andrii Nakryiko 0 siblings, 1 reply; 4+ messages in thread From: Joel Fernandes @ 2020-05-28 22:54 UTC (permalink / raw) To: Andrii Nakryiko Cc: bpf, netdev, paulmck, stern, parri.andrea, will, peterz, boqun.feng, npiggin, dhowells, j.alglave, luc.maranget, akiyks, dlustig, linux-kernel, linux-arch, andrii.nakryiko, kernel-team Hello Andrii, This is quite exciting. Some comments below: On Wed, May 27, 2020 at 11:24:08PM -0700, Andrii Nakryiko wrote: [...] > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus > new file mode 100644 > index 000000000000..558f054fb0b4 > --- /dev/null > +++ b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus > @@ -0,0 +1,91 @@ > +C bpf-rb+1p1c+bounded > + > +(* > + * Result: Always > + * > + * This litmus test validates BPF ring buffer implementation under the > + * following assumptions: > + * - 1 producer; > + * - 1 consumer; > + * - ring buffer has capacity for only 1 record. > + * > + * Expectations: > + * - 1 record pushed into ring buffer; > + * - 0 or 1 element is consumed. > + * - no failures. > + *) > + > +{ > + atomic_t dropped; > +} > + > +P0(int *lenFail, int *len1, int *cx, int *px) > +{ > + int *rLenPtr; > + int rLen; > + int rPx; > + int rCx; > + int rFail; > + > + rFail = 0; > + > + rCx = smp_load_acquire(cx); > + rPx = smp_load_acquire(px); Is it possible for you to put some more comments around which ACQUIRE is paired with which RELEASE? And, in general more comments around the reason for a certain memory barrier and what pairs with what. In the kernel sources, the barriers needs a comment anyway. > + if (rCx < rPx) { > + if (rCx == 0) { > + rLenPtr = len1; > + } else { > + rLenPtr = lenFail; > + rFail = 1; > + } > + > + rLen = smp_load_acquire(rLenPtr); > + if (rLen == 0) { > + rFail = 1; > + } else if (rLen == 1) { > + rCx = rCx + 1; > + smp_store_release(cx, rCx); > + } > + } > +} > + > +P1(int *lenFail, int *len1, spinlock_t *rb_lock, int *px, int *cx, atomic_t *dropped) > +{ > + int rPx; > + int rCx; > + int rFail; > + int *rLenPtr; > + > + rFail = 0; > + > + rCx = smp_load_acquire(cx); > + spin_lock(rb_lock); > + > + rPx = *px; > + if (rPx - rCx >= 1) { > + atomic_inc(dropped); Why does 'dropped' need to be atomic if you are always incrementing under a lock? > + spin_unlock(rb_lock); > + } else { > + if (rPx == 0) { > + rLenPtr = len1; > + } else { > + rLenPtr = lenFail; > + rFail = 1; > + } > + > + *rLenPtr = -1; Clarify please the need to set the length intermittently to -1. Thanks. > + smp_store_release(px, rPx + 1); > + > + spin_unlock(rb_lock); > + > + smp_store_release(rLenPtr, 1); > + } > +} > + > +exists ( > + 0:rFail=0 /\ 1:rFail=0 > + /\ > + ( > + (dropped=0 /\ px=1 /\ len1=1 /\ (cx=0 \/ cx=1)) > + ) > +) > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+unbound.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+unbound.litmus > new file mode 100644 > index 000000000000..7ab5d0e6e49f > --- /dev/null > +++ b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+unbound.litmus I wish there was a way to pass args to litmus tests, then perhaps it would have been possible to condense some of these tests. :-) > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus > new file mode 100644 > index 000000000000..83f80328c92b > --- /dev/null > +++ b/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus [...] > +P0(int *lenFail, int *len1, int *cx, int *px) > +{ > + int *rLenPtr; > + int rLen; > + int rPx; > + int rCx; > + int rFail; > + > + rFail = 0; > + > + rCx = smp_load_acquire(cx); > + rPx = smp_load_acquire(px); > + if (rCx < rPx) { > + if (rCx == 0) { > + rLenPtr = len1; > + } else if (rCx == 1) { > + rLenPtr = len1; > + } else { > + rLenPtr = lenFail; > + rFail = 1; > + } > + > + rLen = smp_load_acquire(rLenPtr); > + if (rLen == 0) { > + rFail = 1; > + } else if (rLen == 1) { > + rCx = rCx + 1; > + smp_store_release(cx, rCx); > + } > + } > + > + rPx = smp_load_acquire(px); > + if (rCx < rPx) { > + if (rCx == 0) { > + rLenPtr = len1; > + } else if (rCx == 1) { > + rLenPtr = len1; > + } else { > + rLenPtr = lenFail; > + rFail = 1; > + } > + > + rLen = smp_load_acquire(rLenPtr); > + if (rLen == 0) { > + rFail = 1; > + } else if (rLen == 1) { > + rCx = rCx + 1; > + smp_store_release(cx, rCx); > + } > + } > +} > + > +P1(int *lenFail, int *len1, spinlock_t *rb_lock, int *px, int *cx, atomic_t *dropped) > +{ > + int rPx; > + int rCx; > + int rFail; > + int *rLenPtr; > + > + rFail = 0; > + rLenPtr = lenFail; > + > + rCx = smp_load_acquire(cx); > + spin_lock(rb_lock); > + > + rPx = *px; > + if (rPx - rCx >= 1) { > + atomic_inc(dropped); > + spin_unlock(rb_lock); > + } else { > + if (rPx == 0) { > + rLenPtr = len1; > + } else if (rPx == 1) { > + rLenPtr = len1; > + } else { > + rLenPtr = lenFail; > + rFail = 1; > + } > + > + *rLenPtr = -1; > + smp_store_release(px, rPx + 1); > + > + spin_unlock(rb_lock); > + > + smp_store_release(rLenPtr, 1); I ran a test replacing the last 2 statements above with the following and it still works: spin_unlock(rb_lock); WRITE_ONCE(*rLenPtr, 1); Wouldn't you expect the test to catch an issue? The spin_unlock is already a RELEASE barrier. Suggestion: It is hard to review the patch because it is huge, it would be good to split this up into 4 patches for each of the tests. But upto you :) thanks, - Joel [...] ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH linux-rcu] docs/litmus-tests: add BPF ringbuf MPSC litmus tests 2020-05-28 22:54 ` [PATCH linux-rcu] docs/litmus-tests: add BPF ringbuf MPSC litmus tests Joel Fernandes @ 2020-05-29 5:50 ` Andrii Nakryiko 2020-05-29 17:34 ` Joel Fernandes 0 siblings, 1 reply; 4+ messages in thread From: Andrii Nakryiko @ 2020-05-29 5:50 UTC (permalink / raw) To: Joel Fernandes Cc: Andrii Nakryiko, bpf, Networking, Paul E . McKenney, Alan Stern, parri.andrea, will, Peter Ziljstra, Boqun Feng, npiggin, dhowells, j.alglave, luc.maranget, Akira Yokosawa, dlustig, open list, linux-arch, Kernel Team On Thu, May 28, 2020 at 3:54 PM Joel Fernandes <joel@joelfernandes.org> wrote: > > Hello Andrii, > This is quite exciting. Some comments below: > > On Wed, May 27, 2020 at 11:24:08PM -0700, Andrii Nakryiko wrote: > [...] > > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus > > new file mode 100644 > > index 000000000000..558f054fb0b4 > > --- /dev/null > > +++ b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus > > @@ -0,0 +1,91 @@ > > +C bpf-rb+1p1c+bounded > > + > > +(* > > + * Result: Always > > + * > > + * This litmus test validates BPF ring buffer implementation under the > > + * following assumptions: > > + * - 1 producer; > > + * - 1 consumer; > > + * - ring buffer has capacity for only 1 record. > > + * > > + * Expectations: > > + * - 1 record pushed into ring buffer; > > + * - 0 or 1 element is consumed. > > + * - no failures. > > + *) > > + > > +{ > > + atomic_t dropped; > > +} > > + > > +P0(int *lenFail, int *len1, int *cx, int *px) > > +{ > > + int *rLenPtr; > > + int rLen; > > + int rPx; > > + int rCx; > > + int rFail; > > + > > + rFail = 0; > > + > > + rCx = smp_load_acquire(cx); > > + rPx = smp_load_acquire(px); > > Is it possible for you to put some more comments around which ACQUIRE is > paired with which RELEASE? And, in general more comments around the reason > for a certain memory barrier and what pairs with what. In the kernel sources, > the barriers needs a comment anyway. > > > + if (rCx < rPx) { > > + if (rCx == 0) { > > + rLenPtr = len1; > > + } else { > > + rLenPtr = lenFail; > > + rFail = 1; > > + } > > + > > + rLen = smp_load_acquire(rLenPtr); > > + if (rLen == 0) { > > + rFail = 1; > > + } else if (rLen == 1) { > > + rCx = rCx + 1; > > + smp_store_release(cx, rCx); > > + } > > + } > > +} > > + > > +P1(int *lenFail, int *len1, spinlock_t *rb_lock, int *px, int *cx, atomic_t *dropped) > > +{ > > + int rPx; > > + int rCx; > > + int rFail; > > + int *rLenPtr; > > + > > + rFail = 0; > > + > > + rCx = smp_load_acquire(cx); > > + spin_lock(rb_lock); > > + > > + rPx = *px; > > + if (rPx - rCx >= 1) { > > + atomic_inc(dropped); > > Why does 'dropped' need to be atomic if you are always incrementing under a > lock? It doesn't, strictly speaking, but making it atomic in litmus test was just more convenient, especially that I initially also had a lock-less variant of this algorithm. > > > + spin_unlock(rb_lock); > > + } else { > > + if (rPx == 0) { > > + rLenPtr = len1; > > + } else { > > + rLenPtr = lenFail; > > + rFail = 1; > > + } > > + > > + *rLenPtr = -1; > > Clarify please the need to set the length intermittently to -1. Thanks. This corresponds to setting a "busy bit" in kernel implementation. These litmus tests are supposed to be correlated with in-kernel implementation, I'm not sure I want to maintain extra 4 copies of comments here and in kernel code. Especially for 2-producer cases, there are 2 identical P1 and P2, which is unfortunate, but I haven't figured out how to have a re-usable pieces of code with litmus tests :) > > > + smp_store_release(px, rPx + 1); > > + > > + spin_unlock(rb_lock); > > + > > + smp_store_release(rLenPtr, 1); > > + } > > +} > > + > > +exists ( > > + 0:rFail=0 /\ 1:rFail=0 > > + /\ > > + ( > > + (dropped=0 /\ px=1 /\ len1=1 /\ (cx=0 \/ cx=1)) > > + ) > > +) > > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+unbound.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+unbound.litmus > > new file mode 100644 > > index 000000000000..7ab5d0e6e49f > > --- /dev/null > > +++ b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+unbound.litmus > > I wish there was a way to pass args to litmus tests, then perhaps it would > have been possible to condense some of these tests. :-) It wouldn't help much, actually, because litmus tests can't have arrays. See all those "if selectors" between len1 and len2, I had to do explicitly. > > > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus > > new file mode 100644 > > index 000000000000..83f80328c92b > > --- /dev/null > > +++ b/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus > [...] > > +P0(int *lenFail, int *len1, int *cx, int *px) > > +{ > > + int *rLenPtr; > > + int rLen; > > + int rPx; > > + int rCx; > > + int rFail; > > + > > + rFail = 0; > > + > > + rCx = smp_load_acquire(cx); > > + rPx = smp_load_acquire(px); > > + if (rCx < rPx) { > > + if (rCx == 0) { > > + rLenPtr = len1; > > + } else if (rCx == 1) { > > + rLenPtr = len1; > > + } else { > > + rLenPtr = lenFail; > > + rFail = 1; > > + } > > + > > + rLen = smp_load_acquire(rLenPtr); > > + if (rLen == 0) { > > + rFail = 1; > > + } else if (rLen == 1) { > > + rCx = rCx + 1; > > + smp_store_release(cx, rCx); > > + } > > + } > > + > > + rPx = smp_load_acquire(px); > > + if (rCx < rPx) { > > + if (rCx == 0) { > > + rLenPtr = len1; > > + } else if (rCx == 1) { > > + rLenPtr = len1; > > + } else { > > + rLenPtr = lenFail; > > + rFail = 1; > > + } > > + > > + rLen = smp_load_acquire(rLenPtr); > > + if (rLen == 0) { > > + rFail = 1; > > + } else if (rLen == 1) { > > + rCx = rCx + 1; > > + smp_store_release(cx, rCx); > > + } > > + } > > +} > > + > > +P1(int *lenFail, int *len1, spinlock_t *rb_lock, int *px, int *cx, atomic_t *dropped) > > +{ > > + int rPx; > > + int rCx; > > + int rFail; > > + int *rLenPtr; > > + > > + rFail = 0; > > + rLenPtr = lenFail; > > + > > + rCx = smp_load_acquire(cx); > > + spin_lock(rb_lock); > > + > > + rPx = *px; > > + if (rPx - rCx >= 1) { > > + atomic_inc(dropped); > > + spin_unlock(rb_lock); > > + } else { > > + if (rPx == 0) { > > + rLenPtr = len1; > > + } else if (rPx == 1) { > > + rLenPtr = len1; > > + } else { > > + rLenPtr = lenFail; > > + rFail = 1; > > + } > > + > > + *rLenPtr = -1; > > + smp_store_release(px, rPx + 1); > > + > > + spin_unlock(rb_lock); > > + > > + smp_store_release(rLenPtr, 1); > > I ran a test replacing the last 2 statements above with the following and it > still works: > > spin_unlock(rb_lock); > WRITE_ONCE(*rLenPtr, 1); > > Wouldn't you expect the test to catch an issue? The spin_unlock is already a > RELEASE barrier. Well, apparently it's not an issue and WRITE_ONCE would work as well :) My original version actually used WRITE_ONCE here. See [0] and discussion in [1] after which I removed all the WRITE_ONCE/READ_ONCE in favor of store_release/load_acquire for consistency. [0] https://patchwork.ozlabs.org/project/netdev/patch/20200513192532.4058934-3-andriin@fb.com/ [1] https://patchwork.ozlabs.org/project/netdev/patch/20200513192532.4058934-2-andriin@fb.com/ > > Suggestion: It is hard to review the patch because it is huge, it would be > good to split this up into 4 patches for each of the tests. But upto you :) Those 4 files are partial copies of each other, not sure splitting them actually would be easier. If anyone else thinks the same, though, I'll happily split. > > thanks, > > - Joel > > [...] > ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH linux-rcu] docs/litmus-tests: add BPF ringbuf MPSC litmus tests 2020-05-29 5:50 ` Andrii Nakryiko @ 2020-05-29 17:34 ` Joel Fernandes 2020-05-29 20:18 ` Andrii Nakryiko 0 siblings, 1 reply; 4+ messages in thread From: Joel Fernandes @ 2020-05-29 17:34 UTC (permalink / raw) To: Andrii Nakryiko Cc: Andrii Nakryiko, bpf, Networking, Paul E . McKenney, Alan Stern, parri.andrea, will, Peter Ziljstra, Boqun Feng, npiggin, dhowells, j.alglave, luc.maranget, Akira Yokosawa, dlustig, open list, linux-arch, Kernel Team Hi Andrii, On Thu, May 28, 2020 at 10:50:30PM -0700, Andrii Nakryiko wrote: > > [...] > > > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus > > > new file mode 100644 > > > index 000000000000..558f054fb0b4 > > > --- /dev/null > > > +++ b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus > > > @@ -0,0 +1,91 @@ > > > +C bpf-rb+1p1c+bounded > > > + > > > +(* > > > + * Result: Always > > > + * > > > + * This litmus test validates BPF ring buffer implementation under the > > > + * following assumptions: > > > + * - 1 producer; > > > + * - 1 consumer; > > > + * - ring buffer has capacity for only 1 record. > > > + * > > > + * Expectations: > > > + * - 1 record pushed into ring buffer; > > > + * - 0 or 1 element is consumed. > > > + * - no failures. > > > + *) > > > + > > > +{ > > > + atomic_t dropped; > > > +} > > > + > > > +P0(int *lenFail, int *len1, int *cx, int *px) > > > +{ > > > + int *rLenPtr; > > > + int rLen; > > > + int rPx; > > > + int rCx; > > > + int rFail; > > > + > > > + rFail = 0; > > > + > > > + rCx = smp_load_acquire(cx); > > > + rPx = smp_load_acquire(px); > > > > Is it possible for you to put some more comments around which ACQUIRE is > > paired with which RELEASE? And, in general more comments around the reason > > for a certain memory barrier and what pairs with what. In the kernel sources, > > the barriers needs a comment anyway. This was the comment earlier that was missed. > > > + if (rCx < rPx) { > > > + if (rCx == 0) { > > > + rLenPtr = len1; > > > + } else { > > > + rLenPtr = lenFail; > > > + rFail = 1; > > > + } > > > + > > > + rLen = smp_load_acquire(rLenPtr); > > > + if (rLen == 0) { > > > + rFail = 1; > > > + } else if (rLen == 1) { > > > + rCx = rCx + 1; > > > + smp_store_release(cx, rCx); > > > + } > > > + } > > > +} > > > + > > > +P1(int *lenFail, int *len1, spinlock_t *rb_lock, int *px, int *cx, atomic_t *dropped) > > > +{ > > > + int rPx; > > > + int rCx; > > > + int rFail; > > > + int *rLenPtr; > > > + > > > + rFail = 0; > > > + > > > + rCx = smp_load_acquire(cx); > > > + spin_lock(rb_lock); > > > + > > > + rPx = *px; > > > + if (rPx - rCx >= 1) { > > > + atomic_inc(dropped); > > > > Why does 'dropped' need to be atomic if you are always incrementing under a > > lock? > > It doesn't, strictly speaking, but making it atomic in litmus test was > just more convenient, especially that I initially also had a lock-less > variant of this algorithm. Ok, that's fine. > > > > > + spin_unlock(rb_lock); > > > + } else { > > > + if (rPx == 0) { > > > + rLenPtr = len1; > > > + } else { > > > + rLenPtr = lenFail; > > > + rFail = 1; > > > + } > > > + > > > + *rLenPtr = -1; > > > > Clarify please the need to set the length intermittently to -1. Thanks. > > This corresponds to setting a "busy bit" in kernel implementation. > These litmus tests are supposed to be correlated with in-kernel > implementation, I'm not sure I want to maintain extra 4 copies of > comments here and in kernel code. Especially for 2-producer cases, > there are 2 identical P1 and P2, which is unfortunate, but I haven't > figured out how to have a re-usable pieces of code with litmus tests > :) I disagree that comments related to memory ordering are optional. IMHO, the documentation should be clear from a memory ordering standpoint. After all, good Documentation/ always clarifies something / some concept to the reader right? :-) Please have mercy on me, I am just trying to learn *your* Documentation ;-) > > > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus [...] > > > +P1(int *lenFail, int *len1, spinlock_t *rb_lock, int *px, int *cx, atomic_t *dropped) > > > +{ > > > + int rPx; > > > + int rCx; > > > + int rFail; > > > + int *rLenPtr; > > > + > > > + rFail = 0; > > > + rLenPtr = lenFail; > > > + > > > + rCx = smp_load_acquire(cx); > > > + spin_lock(rb_lock); > > > + > > > + rPx = *px; > > > + if (rPx - rCx >= 1) { > > > + atomic_inc(dropped); > > > + spin_unlock(rb_lock); > > > + } else { > > > + if (rPx == 0) { > > > + rLenPtr = len1; > > > + } else if (rPx == 1) { > > > + rLenPtr = len1; > > > + } else { > > > + rLenPtr = lenFail; > > > + rFail = 1; > > > + } > > > + > > > + *rLenPtr = -1; > > > + smp_store_release(px, rPx + 1); > > > + > > > + spin_unlock(rb_lock); > > > + > > > + smp_store_release(rLenPtr, 1); > > > > I ran a test replacing the last 2 statements above with the following and it > > still works: > > > > spin_unlock(rb_lock); > > WRITE_ONCE(*rLenPtr, 1); > > > > Wouldn't you expect the test to catch an issue? The spin_unlock is already a > > RELEASE barrier. > > Well, apparently it's not an issue and WRITE_ONCE would work as well > :) My original version actually used WRITE_ONCE here. See [0] and > discussion in [1] after which I removed all the WRITE_ONCE/READ_ONCE > in favor of store_release/load_acquire for consistency. > > [0] https://patchwork.ozlabs.org/project/netdev/patch/20200513192532.4058934-3-andriin@fb.com/ > [1] https://patchwork.ozlabs.org/project/netdev/patch/20200513192532.4058934-2-andriin@fb.com/ Huh. So you are replacing the test to use WRITE_ONCE instead? Why did you favor the acquire/release memory barriers over the _ONCE annotations, if that was not really needed then? > > Suggestion: It is hard to review the patch because it is huge, it would be > > good to split this up into 4 patches for each of the tests. But upto you :) > > Those 4 files are partial copies of each other, not sure splitting > them actually would be easier. If anyone else thinks the same, though, > I'll happily split. I personally disagree. It would be much easier IMHO to review 4 different files since some of them are also quite dissimilar. I frequently keep jumping between diffs to find a different file and it makes the review that much harder. But anything the LKMM experts decide in this regard is acceptable to me :) thanks, - Joel ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH linux-rcu] docs/litmus-tests: add BPF ringbuf MPSC litmus tests 2020-05-29 17:34 ` Joel Fernandes @ 2020-05-29 20:18 ` Andrii Nakryiko 0 siblings, 0 replies; 4+ messages in thread From: Andrii Nakryiko @ 2020-05-29 20:18 UTC (permalink / raw) To: Joel Fernandes Cc: Andrii Nakryiko, bpf, Networking, Paul E . McKenney, Alan Stern, parri.andrea, will, Peter Ziljstra, Boqun Feng, npiggin, dhowells, j.alglave, luc.maranget, Akira Yokosawa, dlustig, open list, linux-arch, Kernel Team On Fri, May 29, 2020 at 10:34 AM Joel Fernandes <joel@joelfernandes.org> wrote: > > Hi Andrii, > > On Thu, May 28, 2020 at 10:50:30PM -0700, Andrii Nakryiko wrote: > > > [...] > > > > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus > > > > new file mode 100644 > > > > index 000000000000..558f054fb0b4 > > > > --- /dev/null > > > > +++ b/Documentation/litmus-tests/bpf-rb/bpf-rb+1p1c+bounded.litmus > > > > @@ -0,0 +1,91 @@ > > > > +C bpf-rb+1p1c+bounded > > > > + > > > > +(* > > > > + * Result: Always > > > > + * > > > > + * This litmus test validates BPF ring buffer implementation under the > > > > + * following assumptions: > > > > + * - 1 producer; > > > > + * - 1 consumer; > > > > + * - ring buffer has capacity for only 1 record. > > > > + * > > > > + * Expectations: > > > > + * - 1 record pushed into ring buffer; > > > > + * - 0 or 1 element is consumed. > > > > + * - no failures. > > > > + *) > > > > + > > > > +{ > > > > + atomic_t dropped; > > > > +} > > > > + > > > > +P0(int *lenFail, int *len1, int *cx, int *px) > > > > +{ > > > > + int *rLenPtr; > > > > + int rLen; > > > > + int rPx; > > > > + int rCx; > > > > + int rFail; > > > > + > > > > + rFail = 0; > > > > + > > > > + rCx = smp_load_acquire(cx); > > > > + rPx = smp_load_acquire(px); > > > > > > Is it possible for you to put some more comments around which ACQUIRE is > > > paired with which RELEASE? And, in general more comments around the reason > > > for a certain memory barrier and what pairs with what. In the kernel sources, > > > the barriers needs a comment anyway. > > This was the comment earlier that was missed. Right, I'll follow up extending kernel implementation comments, and will add some more to litmus tests. > > > > > + if (rCx < rPx) { > > > > + if (rCx == 0) { > > > > + rLenPtr = len1; > > > > + } else { > > > > + rLenPtr = lenFail; > > > > + rFail = 1; > > > > + } > > > > + > > > > + rLen = smp_load_acquire(rLenPtr); > > > > + if (rLen == 0) { > > > > + rFail = 1; > > > > + } else if (rLen == 1) { > > > > + rCx = rCx + 1; > > > > + smp_store_release(cx, rCx); > > > > + } > > > > + } > > > > +} > > > > + > > > > +P1(int *lenFail, int *len1, spinlock_t *rb_lock, int *px, int *cx, atomic_t *dropped) > > > > +{ > > > > + int rPx; > > > > + int rCx; > > > > + int rFail; > > > > + int *rLenPtr; > > > > + > > > > + rFail = 0; > > > > + > > > > + rCx = smp_load_acquire(cx); > > > > + spin_lock(rb_lock); > > > > + > > > > + rPx = *px; > > > > + if (rPx - rCx >= 1) { > > > > + atomic_inc(dropped); > > > > > > Why does 'dropped' need to be atomic if you are always incrementing under a > > > lock? > > > > It doesn't, strictly speaking, but making it atomic in litmus test was > > just more convenient, especially that I initially also had a lock-less > > variant of this algorithm. > > Ok, that's fine. > > > > > > > > + spin_unlock(rb_lock); > > > > + } else { > > > > + if (rPx == 0) { > > > > + rLenPtr = len1; > > > > + } else { > > > > + rLenPtr = lenFail; > > > > + rFail = 1; > > > > + } > > > > + > > > > + *rLenPtr = -1; > > > > > > Clarify please the need to set the length intermittently to -1. Thanks. > > > > This corresponds to setting a "busy bit" in kernel implementation. > > These litmus tests are supposed to be correlated with in-kernel > > implementation, I'm not sure I want to maintain extra 4 copies of > > comments here and in kernel code. Especially for 2-producer cases, > > there are 2 identical P1 and P2, which is unfortunate, but I haven't > > figured out how to have a re-usable pieces of code with litmus tests > > :) > > I disagree that comments related to memory ordering are optional. IMHO, the > documentation should be clear from a memory ordering standpoint. After all, > good Documentation/ always clarifies something / some concept to the reader > right? :-) Please have mercy on me, I am just trying to learn *your* > Documentation ;-) My point was that reading litmus test without also reading ringbuf implementation is pointless and is harder than necessary. I'll add few comments to litmus tests, but ultimately I view kernel implementation as the source of truth and litmus test as a simplified model of it. So having extensive comments in litmus test is just a maintenance burden and more chance to get confusing, out-of-sync documentation. > > > > > diff --git a/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus b/Documentation/litmus-tests/bpf-rb/bpf-rb+2p1c+bounded.litmus > [...] > > > > +P1(int *lenFail, int *len1, spinlock_t *rb_lock, int *px, int *cx, atomic_t *dropped) > > > > +{ > > > > + int rPx; > > > > + int rCx; > > > > + int rFail; > > > > + int *rLenPtr; > > > > + > > > > + rFail = 0; > > > > + rLenPtr = lenFail; > > > > + > > > > + rCx = smp_load_acquire(cx); > > > > + spin_lock(rb_lock); > > > > + > > > > + rPx = *px; > > > > + if (rPx - rCx >= 1) { > > > > + atomic_inc(dropped); > > > > + spin_unlock(rb_lock); > > > > + } else { > > > > + if (rPx == 0) { > > > > + rLenPtr = len1; > > > > + } else if (rPx == 1) { > > > > + rLenPtr = len1; > > > > + } else { > > > > + rLenPtr = lenFail; > > > > + rFail = 1; > > > > + } > > > > + > > > > + *rLenPtr = -1; > > > > + smp_store_release(px, rPx + 1); > > > > + > > > > + spin_unlock(rb_lock); > > > > + > > > > + smp_store_release(rLenPtr, 1); > > > > > > I ran a test replacing the last 2 statements above with the following and it > > > still works: > > > > > > spin_unlock(rb_lock); > > > WRITE_ONCE(*rLenPtr, 1); > > > > > > Wouldn't you expect the test to catch an issue? The spin_unlock is already a > > > RELEASE barrier. > > > > Well, apparently it's not an issue and WRITE_ONCE would work as well > > :) My original version actually used WRITE_ONCE here. See [0] and > > discussion in [1] after which I removed all the WRITE_ONCE/READ_ONCE > > in favor of store_release/load_acquire for consistency. > > > > [0] https://patchwork.ozlabs.org/project/netdev/patch/20200513192532.4058934-3-andriin@fb.com/ > > [1] https://patchwork.ozlabs.org/project/netdev/patch/20200513192532.4058934-2-andriin@fb.com/ > > Huh. So you are replacing the test to use WRITE_ONCE instead? Why did you > favor the acquire/release memory barriers over the _ONCE annotations, if that > was not really needed then? I replaced WRITE_ONCE with store_release. There was a request on initial version to keep it simple and use store_release/load_acquire pairings consistently and not mix up WRITE_ONCE and load_acquire, so that's what I did. As I mentioned elsewhere, this might not be the weakest possible set of orderings and we might improve that, but it seems to work well. > > > > Suggestion: It is hard to review the patch because it is huge, it would be > > > good to split this up into 4 patches for each of the tests. But upto you :) > > > > Those 4 files are partial copies of each other, not sure splitting > > them actually would be easier. If anyone else thinks the same, though, > > I'll happily split. > > I personally disagree. It would be much easier IMHO to review 4 different > files since some of them are also quite dissimilar. I frequently keep jumping > between diffs to find a different file and it makes the review that much > harder. But anything the LKMM experts decide in this regard is acceptable to me :) > > thanks, > > - Joel > ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2020-05-29 20:18 UTC | newest] Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <20200528062408.547149-1-andriin@fb.com> 2020-05-28 22:54 ` [PATCH linux-rcu] docs/litmus-tests: add BPF ringbuf MPSC litmus tests Joel Fernandes 2020-05-29 5:50 ` Andrii Nakryiko 2020-05-29 17:34 ` Joel Fernandes 2020-05-29 20:18 ` Andrii Nakryiko
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).