pipe: Convert ring to head/tail
Subsystems (4)
RFC PATCH 1/1 pipe: Convert ring to head/tail
Here's my first patch to the pipe ring, with an eye to piggybacking notifications on it. Other than whatever booting does, I haven't managed to explicitly test splice and iov_iter-to-pipe yet. Other than that, lmbench seems to show about a 1% improvement on pipe performance and my own just-shovel-data-through-for-X-amount-of-time test shows about .5% improvement. The difference in seeming improvements is possibly because my test is using 511-byte writes and lmbench is using 512-byte writes.
David
---
pipe: Use head and tail pointers for the ring, not cursor and length
Convert pipes to use head and tail pointers for the buffer ring rather than pointer and length as the latter requires two atomic ops to update (or a combined op) whereas the former only requires one.
(1) The head pointer is the point at which production occurs and points to the slot in which the next buffer will be placed. This is equivalent to pipe->curbuf + pipe->nrbufs.
The head pointer belongs to the write-side.
(2) The tail pointer is the point at which consumption occurs. It points to the next slot to be consumed. This is equivalent to pipe->curbuf.
The tail pointer belongs to the read-side.
(3) head and tail are allowed to run to UINT_MAX and wrap naturally. They are only masked off when the array is being accessed, e.g.:
pipe->bufs[head & mask]
This means that it is not necessary to have a dead slot in the ring as head == tail isn't ambiguous.
(4) The ring is empty if head == tail.
(5) The occupancy of the ring is head - tail.
(6) The amount of space in the ring is (tail + pipe->buffers) - head.
(7) The ring is full if head == (tail + pipe->buffers) or
head - tail == pipe->buffers.
Barriers are also inserted, wrapped in inline functions:
(1) unsigned int tail = pipe_get_tail_for_write(pipe);
Read the tail pointer from the write-side. This acts as a barrier to order the tail read before the data in the ring is overwritten. It also prevents the compiler from re-reading the pointer.
(2) unsigned int head = pipe_get_head_for_read(pipe);
Read the head pointer from the read-side. This acts as a barrier to order the head read before the data read. It also prevents the compiler from re-reading the pointer.
(3) pipe_post_read_barrier(pipe, unsigned int tail);
Update the tail pointer from the read-side. This acts as a barrier to order the pointer update after the data read. The consumed data slot must not be touched after this function.
(4) pipe_post_write_barrier(pipe, unsigned int head);
Update the head pointer from the write-side. This acts as a barrier to order the pointer update after the data write. The produced data slot should not normally be touched after this function[*].
[*] Unless pipe->mutex is held.
--- fs/fuse/dev.c | 23 ++- fs/pipe.c | 154 ++++++++++++++++---------- fs/splice.c | 161 +++++++++++++++++---------- include/linux/pipe_fs_i.h | 76 ++++++++++++- include/linux/uio.h | 4 lib/iov_iter.c | 268 ++++++++++++++++++++++++++-------------------- 6 files changed, 438 insertions(+), 248 deletions(-)
fs/fuse/dev.c +14 -9
@@ -1466,7 +1466,7 @@ static ssize_t fuse_dev_splice_read(struct file *in, loff_t *ppos,if (ret <0 ) goto out; -if (pipe->nrbufs + cs.nr_segs > pipe->buffers) { +if (pipe->head - pipe->tail + cs.nr_segs > pipe->buffers) { ret = -EIO ; goto out; }
@@ -2029,6 +2029,7 @@ static ssize_t fuse_dev_splice_write(struct pipe_inode_info *pipe, struct file *out, loff_t *ppos, size_t len, unsigned int flags) { + unsigned int head, tail, mask, count;unsigned nbuf;unsigned idx;struct pipe_buffer *bufs;
@@ -2043,8 +2044,12 @@ static ssize_t fuse_dev_splice_write(struct pipe_inode_info *pipe,pipe_lock (pipe); - bufs =kvmalloc_array (pipe->nrbufs,sizeof (struct pipe_buffer ), -GFP_KERNEL ); + head =pipe_get_head_for_read (pipe); + tail = pipe->tail; + mask = pipe->buffers -1 ; + count = head - tail; + + bufs =kvmalloc_array (count,sizeof (struct pipe_buffer ),GFP_KERNEL );if (!bufs) {pipe_unlock (pipe);return -ENOMEM ;
@@ -2052,8 +2057,8 @@ static ssize_t fuse_dev_splice_write(struct pipe_inode_info *pipe, nbuf =0 ; rem =0 ; -for (idx =0 ; idx < pipe->nrbufs && rem < len; idx++) - rem += pipe->bufs[(pipe->curbuf + idx) & (pipe->buffers -1 )].len; +for (idx = tail; idx < head && rem < len; idx++) + rem += pipe->bufs[idx & mask].len; ret = -EINVAL ;if (rem < len)
@@ -2065,15 +2070,15 @@ static ssize_t fuse_dev_splice_write(struct pipe_inode_info *pipe,struct pipe_buffer *obuf;BUG_ON (nbuf >= pipe->buffers); -BUG_ON (!pipe->nrbufs); - ibuf = &pipe->bufs[pipe->curbuf]; +BUG_ON (tail == head); + ibuf = &pipe->bufs[tail]; obuf = &bufs[nbuf];if (rem >= ibuf->len) { *obuf = *ibuf; ibuf->ops =NULL ; - pipe->curbuf = (pipe->curbuf +1 ) & (pipe->buffers -1 ); - pipe->nrbufs--; + tail++; +pipe_post_read_barrier (pipe, tail); }else {if (!pipe_buf_get (pipe, ibuf)) goto out_free;
fs/pipe.c +94 -60
286 lines not on this page · raw message
fs/splice.c +101 -60
414 lines not on this page · raw message
include/linux/pipe_fs_i.h +73 -3
95 lines not on this page · raw message
include/linux/uio.h +2 -2
@@ -45,8 +45,8 @@ struct iov_iter {union {unsigned long nr_segs;struct { -int idx; -int start_idx; +unsigned int head; +unsigned int start_head; }; }; };
lib/iov_iter.c +154 -114
547 lines not on this page · raw message
My just-shovel-data-through-for-X-amount-of-time test
/*
* Benchmark a pipe by seeing how many 511-byte writes can be stuffed through
* it in a certain amount of time. Compile with -lm.
*/
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <signal.h>
#include <math.h>
#include <sys/wait.h>
#include <sys/mman.h>
static char buf1[4096] __attribute__((aligned(4096))); static char buf2[4096] __attribute__((aligned(4096))); static unsigned long long *results;
static volatile int stop;
void sigalrm(int sig)
{
stop = 1;
}static __attribute__((noreturn))
void producer(int fd, int i)
{
unsigned long long l = 0;
ssize_t n;
signal(SIGALRM, sigalrm);
alarm(1);
while (!stop) {
n = write(fd, buf1, 511);
if (n == -1) {
perror("read");
exit(1);
}
l += n;
}
results[i] = l;
exit(0);
}static __attribute__((noreturn))
void consumer(int fd)
{
unsigned long long l = 0;
ssize_t n;
for (;;) {
n = read(fd, buf2, 4096);
if (n == 0)
break;
if (n == -1) {
perror("read");
exit(1);
}
l += n;
}
exit(0);
}unsigned long long stddev(const unsigned long long *vals, int nvals)
{
double sum = 0.0, mean, sd = 0.0;
int i;
for (i = 0; i < nvals; i++)
sum += vals[i];
mean = sum / nvals;
for (i = 0; i < nvals; i++)
sd += pow(vals[i] - mean, 2);
return sqrt(sd / 10);
}int main()
{
unsigned long long t = 0;
int ex = 0, i;
results = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANON, -1, 0);
if (results == MAP_FAILED) {
perror("mmap");
exit(1);
}
for (i = 0; i < 16 && ex == 0; i++) {
pid_t prod, con;
int pfd[2], wt;
if (pipe2(pfd, 0) < 0) {
perror("pipe");
exit(1);
}
con = fork();
switch (con) {
case -1:
perror("fork/c");
exit(1);
case 0:
close(pfd[1]);
consumer(pfd[0]);
default:
break;
}
prod = fork();
switch (prod) {
case -1:
perror("fork/p");
exit(1);
case 0:
close(pfd[0]);
producer(pfd[1], i);
default:
break;
}
close(pfd[0]);
close(pfd[1]);
for (;;) {
errno = 0;
wait(&wt);
if (errno == ECHILD)
break;
if (!WIFEXITED(wt) || WEXITSTATUS(wt) != 0)
ex = 1;
}
printf("WR[%02u]: %12llu\n", i, results[i]);
t += results[i];
}
printf("total : %12llu\n", t);
printf("avg : %12llu\n", t / i);
printf("stddev: %12llu\n", stddev(results, i));
exit(ex);
}Hi David, [+Peter]
I have a few drive-by comments on the ordering side of things. See below.
Quoted 67 lines · David Howells
Convert pipes to use head and tail pointers for the buffer ring rather than pointer and length as the latter requires two atomic ops to update (or a combined op) whereas the former only requires one.
(1) The head pointer is the point at which production occurs and points to the slot in which the next buffer will be placed. This is equivalent to
pipe->curbuf+pipe->nrbufs.The head pointer belongs to the write-side.
(2) The tail pointer is the point at which consumption occurs. It points to the next slot to be consumed. This is equivalent to
pipe->curbuf.The tail pointer belongs to the read-side.
(3) head and tail are allowed to run to
UINT_MAXand wrap naturally. They are only masked off when the array is being accessed, e.g.:pipe->bufs[head & mask]
This means that it is not necessary to have a dead slot in the ring as head == tail isn't ambiguous.
(4) The ring is empty if head == tail.
(5) The occupancy of the ring is head - tail.
(6) The amount of space in the ring is (tail +
pipe->buffers) - head.(7) The ring is full if head == (tail +
pipe->buffers) orhead - tail == pipe->buffers.Barriers are also inserted, wrapped in inline functions:
(1) unsigned int tail =
pipe_get_tail_for_write(pipe);Read the tail pointer from the write-side. This acts as a barrier to order the tail read before the data in the ring is overwritten. It also prevents the compiler from re-reading the pointer.
(2) unsigned int head =
pipe_get_head_for_read(pipe);Read the head pointer from the read-side. This acts as a barrier to order the head read before the data read. It also prevents the compiler from re-reading the pointer.
(3)
pipe_post_read_barrier(pipe, unsigned int tail);Update the tail pointer from the read-side. This acts as a barrier to order the pointer update after the data read. The consumed data slot must not be touched after this function.
(4)
pipe_post_write_barrier(pipe, unsigned int head);Update the head pointer from the write-side. This acts as a barrier to order the pointer update after the data write. The produced data slot should not normally be touched after this function[*].
[*] Unless
pipe->mutexis held.--- fs/fuse/dev.c | 23 ++- fs/pipe.c | 154 ++++++++++++++++---------- fs/splice.c | 161 +++++++++++++++++---------- include/linux/pipe_fs_i.h | 76 ++++++++++++- include/linux/uio.h | 4 lib/iov_iter.c | 268 ++++++++++++++++++++++++++-------------------- 6 files changed, 438 insertions(+), 248 deletions(-)
[...]
Quoted 19 lines
fs/pipe.c +2
-2@@ -43,10 +43,10 @@ unsigned long pipe_user_pages_hard;unsigned long pipe_user_pages_soft =PIPE_DEF_BUFFERS *INR_OPEN_CUR ;/* -* We use a start+len construction, which provides full use of the +* We use a start+len construction, which provides full use of the * allocated memory. * -- Florian Coosmann (FGC) -* +* * Reads with count = 0 should always return 0. * -- Julian Bradfield 1999-06-07. * @@ -285,10 +285,15 @@ pipe_read(struct kiocb *iocb, struct iov_iter *to) ret =0 ;
fs/pipe.c pipe_read(struct kiocb *iocb, struct iov_iter *to) · line 291
Quoted 10 lines
fs/pipe.c +4
-4__pipe_lock (pipe);for (;;) { -int bufs = pipe->nrbufs; -if (bufs) { -int curbuf = pipe->curbuf; -struct pipe_buffer *buf = pipe->bufs + curbuf; +/* Barrier: head belongs to the write side, so order reading +* the data after reading the head pointer. +*/ +unsigned int head =READ_ONCE (pipe->head);
Hmm, I don't understand this. Since READ_ONCE() doesn't imply a barrier, how are you enforcing the read-read ordering in the CPU?
fs/pipe.c struct pipe_buf_operations { · line 113
Quoted 11 lines
fs/pipe.c +7
-0@@ -104,6 +104,76 @@ struct pipe_buf_operations {bool (*get)(struct pipe_inode_info *,struct pipe_buffer *); }; +/** +* pipe_get_tail_for_write - Get pipe buffer tail pointer for write-side use +* @pipe: The pipe in question +* +* Get the tail pointer for use in the write-side code. This may need to +* insert a barrier against the reader to order reading the tail pointer +* against the reader reading the buffer.
What is the purpose of saying "This may need to insert a barrier"? Can this function be overridden or something?
Quoted 23 lines
fs/pipe.c +23
-0+*/ +static inline unsigned int pipe_get_tail_for_write (struct pipe_inode_info *pipe) +{ +return READ_ONCE (pipe->tail); +} + +/** +* pipe_post_read_barrier - Set pipe buffer tail pointer in the read-side +* @pipe: The pipe in question +* @tail: The new tail pointer +* +* Update the tail pointer in the read-side code. This inserts a barrier +* against the writer such that the data write is ordered before the tail +* pointer update. +*/ +static inline void pipe_post_read_barrier (struct pipe_inode_info *pipe, +unsigned int tail) +{ +smp_store_release (&pipe->tail, tail); +} + +/** +* pipe_get_head_for_read - Get pipe buffer head pointer for read-side use
fs/pipe.c struct pipe_buf_operations { · line 146
Quoted 10 lines
fs/pipe.c +10
-0+* @pipe: The pipe in question +* +* Get the head pointer for use in the read-side code. This inserts a barrier +* against the reader such that the head pointer is read before the data it +* points to. +*/ +static inline unsigned int pipe_get_head_for_read (struct pipe_inode_info *pipe) +{ +return READ_ONCE (pipe->head); +}
Saying that "This inserts a barrier" feels misleading, because READ_ONCE() doesn't do that.
Will
Quoted 7 lines · Will Deacon
fs/pipe.c pipe_read(struct kiocb *iocb, struct iov_iter *to) · line 291
Quoted 4 lines
fs/pipe.c +4
-0+/* Barrier: head belongs to the write side, so order reading +* the data after reading the head pointer. +*/ +unsigned int head =READ_ONCE (pipe->head);Hmm, I don't understand this. Since
READ_ONCE()doesn't imply a barrier, how are you enforcing the read-read ordering in the CPU?
It does imply a barrier: smp_read_barrier_depends(). I believe that's
Quoted 2 lines
What is the purpose of saying "This may need to insert a barrier"? Can this function be overridden or something?
I mean it's arch-dependent whether READ_ONCE() inserts a barrier or not.
Quoted 2 lines
Saying that "This inserts a barrier" feels misleading, because
READ_ONCE()doesn't do that.
Yes it does - on the Alpha:
[arch/alpha/include/asm/barrier.h]
#define read_barrier_depends() __asm__ __volatile__("mb": : :"memory")
[include/asm-generic/barrier.h]
#ifndef __smp_read_barrier_depends
#define __smp_read_barrier_depends() read_barrier_depends()
#endif
...
#ifndef smp_read_barrier_depends
#define smp_read_barrier_depends() __smp_read_barrier_depends()
#endif
[include/linux/compiler.h]
#define __READ_ONCE(x, check) \
({ \
union { typeof(x) __val; char __c[1]; } __u; \
if (check) \
__read_once_size(&(x), __u.__c, sizeof(x)); \
else \
__read_once_size_nocheck(&(x), __u.__c, sizeof(x)); \
smp_read_barrier_depends(); /* Enforce dependency ordering from x */ \
__u.__val; \
})#define READ_ONCE(x) __READ_ONCE(x, 1)
See:
commit 76ebbe78f7390aee075a7f3768af197ded1bdfbb
Author: Will Deacon <[email protected]>
Date: Tue Oct 24 11:22:47 2017 +0100
locking/barriers: Add implicit smp_read_barrier_depends() to READ_ONCE()
David
Hi David,
Quoted 11 lines · David Howells
Quoted 7 lines · Will Deacon
fs/pipe.c pipe_read(struct kiocb *iocb, struct iov_iter *to) · line 291
Quoted 4 lines
fs/pipe.c +4
-0+/* Barrier: head belongs to the write side, so order reading +* the data after reading the head pointer. +*/ +unsigned int head =READ_ONCE (pipe->head);Hmm, I don't understand this. Since
READ_ONCE()doesn't imply a barrier, how are you enforcing the read-read ordering in the CPU?It does imply a barrier:
smp_read_barrier_depends(). I believe that's
I fed your incomplete sentence to https://talktotransformer.com/ :
It does imply a barrier: smp_read_barrier_depends(). I believe that's correct. (I'm not a coder so I assume it just means it's a dependency. Maybe this works for other languages too.)
but I have a feeling that's not what you meant. I guess AI isn't quite ready to rule the world.
Quoted 4 lines
Quoted 2 lines
What is the purpose of saying "This may need to insert a barrier"? Can this function be overridden or something?
I mean it's arch-dependent whether
READ_ONCE()inserts a barrier or not.
Ok, but why would the caller care?
Quoted 28 lines
Quoted 2 lines
Saying that "This inserts a barrier" feels misleading, because
READ_ONCE()doesn't do that.Yes it does - on the Alpha:
[
arch/alpha/include/asm/barrier.h]
#defineread_barrier_depends()__asm____volatile__("mb": : :"memory")[
include/asm-generic/barrier.h]
#ifndef__smp_read_barrier_depends
#define__smp_read_barrier_depends()read_barrier_depends()
#endif
...
#ifndefsmp_read_barrier_depends
#definesmp_read_barrier_depends()__smp_read_barrier_depends()
#endif[
include/linux/compiler.h]
#define__READ_ONCE(x, check)\({ \ union { typeof(x) __val; char __c[1]; } __u; \ if (check) \ __read_once_size(&(x), __u.__c, sizeof(x)); \ else \ __read_once_size_nocheck(&(x), __u.__c, sizeof(x)); \ smp_read_barrier_depends(); /* Enforce dependency ordering from x */ \ __u.__val; \ })
Quoted 8 lines
#define
READ_ONCE(x)__READ_ONCE(x, 1)See:
commit
76ebbe78f7390aee075a7f3768af197ded1bdfbb
Author: Will Deacon <[email protected]>
Date: Tue Oct 24 11:22:47 2017 +0100
locking/barriers: Add implicitsmp_read_barrier_depends()toREAD_ONCE()
Ah, that guy. I tried emailing him but he didn't reply.
Seriously though, READ_ONCE() implies a barrier on Alpha, but its portable barrier semantics are only that it can be used to head an address dependency, a bit like rcu_dereference(). You shouldn't be relying on the stronger ordering provided by Alpha, and I doubt that you really are.
If I'm understanding your code correctly (big 'if'), then you have things like this in pipe_read():
unsigned int head = READ_ONCE(pipe->head);
unsigned int tail = pipe->tail;
unsigned int mask = pipe->buffers - 1;
if (tail != head) {
struct pipe_buffer *buf = &pipe->bufs[tail & mask];
[...]
written = copy_page_to_iter(buf->page, buf->offset, chars, to);where you want to make sure you don't read from 'buf->page' until after you've read the updated head index. Is that right? If so, then READ_ONCE() will not give you that guarantee on architectures such as Power and Arm, because the 'if (tail != head)' branch can be speculated and the buffer can be read before we've got around to looking at the head index.
So I reckon you need smp_load_acquire() in this case. pipe_write() might be ok with the control dependency because CPUs don't tend to make speculative writes visible, but I didn't check it carefully and the compiler can do crazy stuff in this area, so I'd be inclined to use smp_load_acquire() here too unless you really need the last ounce of performance.
Will
Do we need to correct barriering in circular-buffers.rst?
Quoted 22 lines · Will Deacon
If I'm understanding your code correctly (big 'if'), then you have things like this in
pipe_read():unsigned int head = READ_ONCE(pipe->head); unsigned int tail = pipe->tail; unsigned int mask = pipe->buffers - 1; if (tail != head) { struct pipe_buffer *buf = &pipe->bufs[tail & mask]; [...] written = copy_page_to_iter(buf->page, buf->offset, chars, to);where you want to make sure you don't read from '
buf->page' until after you've read the updated head index. Is that right? If so, thenREAD_ONCE()will not give you that guarantee on architectures such as Power and Arm, because the 'if (tail != head)' branch can be speculated and the buffer can be read before we've got around to looking at the head index.
Quoted 5 lines
So I reckon you need
smp_load_acquire()in this case.pipe_write()might be ok with the control dependency because CPUs don't tend to make speculative writes visible, but I didn't check it carefully and the compiler can do crazy stuff in this area, so I'd be inclined to usesmp_load_acquire()here too unless you really need the last ounce of performance.
Yeah, I probably do.
Documentation/core-api/circular-buffers.rst might be wrong, then, I think.
It mandates using smp_store_release() to update buffer->head in the producer and buffer->tail in the consumer - but these need pairing with memory barriers used when reading buffer->head and buffer->tail on the other side. Currently, for the producer we have:
spin_lock(&producer_lock);
unsigned long head = buffer->head;
/* The spin_unlock() and next spin_lock() provide needed ordering. */
unsigned long tail = READ_ONCE(buffer->tail);
if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
/* insert one item into the buffer */
struct item *item = buffer[head];
produce_item(item);
smp_store_release(buffer->head,
(head + 1) & (buffer->size - 1));
/* wake_up() will make sure that the head is committed before
* waking anyone up */
wake_up(consumer);
}
spin_unlock(&producer_lock);I think the ordering comment about spin_unlock and spin_lock is wrong. There's no requirement to have a spinlock on either side - and in any case, both sides could be inside their respective locked sections when accessing the buffer. The READ_ONCE() would theoretically provide the smp_read_barrier_depends() to pair with the smp_store_release() in the consumer. Maybe I should change this to:
spin_lock(&producer_lock);
/* Barrier paired with consumer-side store-release on tail */
unsigned long tail = smp_load_acquire(buffer->tail);
unsigned long head = buffer->head;
if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
/* insert one item into the buffer */
struct item *item = buffer[head];
produce_item(item);
smp_store_release(buffer->head,
(head + 1) & (buffer->size - 1));
/* wake_up() will make sure that the head is committed before
* waking anyone up */
wake_up(consumer);
}
spin_unlock(&producer_lock);The consumer is currently:
spin_lock(&consumer_lock);
/* Read index before reading contents at that index. */
unsigned long head = smp_load_acquire(buffer->head);
unsigned long tail = buffer->tail;
if (CIRC_CNT(head, tail, buffer->size) >= 1) {
/* extract one item from the buffer */
struct item *item = buffer[tail];
consume_item(item);
/* Finish reading descriptor before incrementing tail. */
smp_store_release(buffer->tail,
(tail + 1) & (buffer->size - 1));
}
spin_unlock(&consumer_lock);which I think is okay.
And yes, I note that this does use smp_load_acquire(buffer->head) in the consumer - which I should also be doing.
David
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 4 lines · David Howells
It mandates using
smp_store_release()to updatebuffer->headin the producer andbuffer->tailin the consumer - but these need pairing with memory barriers used when readingbuffer->headandbuffer->tailon the other side.
No, the rule with smp_store_release() should be that it's paired with "smp_load_acquire()". No other barriers needed.
If you do that
thread #1 thread #2
... add data to queue ..
smp_store_release(x)
smp_load_acquire(x) ... read data from queue ..
then you should need no other barriers.
But yes, store_release(x) should always pair with the load_acquire(x), and the guarantee is that if the load_acquire reads the value that the store_release stored, then all subsequent reads in thread #2 will see all preceding writes in thread #1.
That's the optimal locking for a simple queue with a reader and a writer and no other locking needed between the two.
HOWEVER.
I think this is all entirely pointless wrt the pipe buffer use. You don't have a simple queue. You have multiple writers, and you have multiple readers. As a result, you need real locking.
So don't do the barriers. If you do the barriers, you're almost certainly doing something buggy. You don't have the simple "consumer -> producer" thing. Or rather, you don't _only_ have that thing.
A reader "produces" a new tail as far as the writer is concerned (so the reader that has consumed an entry does a smp_store_release(tail) -> smp_load_acquire(tail) on the writer side when the writer looks for a new entry it can fill).
BUT! A writer also needs to make sure it's the *only* writer for that new entry, and similarly a reader that is about to consume an entry needs to make sure it's the only reader of that entry. So it is *not* that kind of simple hand-off situation at all.
End result: use a lock. Seriously. Anything else is going to be buggy, or going to be incredibly subtle.
Don't do those barriers. They are wrong. Barriers simply do not protect against two concurrent readers, or two concurrent writers. Barriers are useless.
Now, it's possible that barriers together with very clever atomics could do a lockless model, but then all the cleverness is going to be in the lockless part of the code, not the barriers. So even if we eventually do a lockless model, it's completely wrong to do the barriers first.
And no, lockless isn't as simple as "readers can do a atomic_add_return_relaxed() to consume an entry, and writers can do a atomic_cmpxchg() to produce one".
I think the only possible lockless model is that readers have some exclusion against other readers (so now you have only one reader at a time), and then you fundamentally know that a reader can update the tail pointer without worrying about any races (because a reader will never race against another reader, and a writer will only ever _read_ the tail pointer). So then - once you have reader-reader exclusion, the _tail_ update is simple:
smp_store_release(old_tail+1, &tail);
because while there are multiple writers, the reader doesn't care (the above, btw, assumes that head/tail themselves aren't doing the "& bufsize" thing, and that that is done at use time - that also makes it easy to see the difference between empty and full).
But this still requires that lock around all readers. And we have
that: the pipe mutex.
But writers have the same issue, and we don't want to use the pipe mutex for writer exclusion, since we want to allow atomic writers.
So writers do have to have a lock, or they need to do something clever with a reservation system that uses cmpxchg. Honestly, just do the lock.
The way this should be done:
1) do the head/tail conversion using the EXISTING locking. We have
the pipe_mutex, and it serializes everybody right now, and it makes any barriers or atomics pointless. Just covert to a sane and simple head/tail model.
NO BARRIERS!
*after* you've done this, do the next phase:
2) convert the writers to use an irq-safe spinlock, and either make
the readers look at it too, or do the above smp_store_release() for the final tail update (and the writers need to use a smp_load_acquire() to look at the tail, despite their lock).
NO BARRIERS (well, outside the tail thing above).
and *after* you've done #2, you can now do writes from atomic context.
At that point you are done. Consider youself happy, but also allow for the possibility that some day you'll see lock contention with lots of writers, and that *maybe* some day (unlikely) you'd want to look at doing
3) see if you can make the writers do some clever lockless reservation model.
But that #3 really should be considered a "we are pretty sure it's possible in theory, but it's questinably useful, and hopefully we'll never even need to consider it".
Linus
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 6 lines · Linus Torvalds
Quoted 3 lines
It mandates using
smp_store_release()to updatebuffer->headin the producer andbuffer->tailin the consumer - but these need pairing with memory barriers used when readingbuffer->headandbuffer->tailon the other side.No, the rule with
smp_store_release()should be that it's paired with "smp_load_acquire()".
Yes.
Quoted 1 line
No other barriers needed.
See below.
Quoted 7 lines
If you do that
thread #1 thread #2
... add data to queue ..
smp_store_release(x)
Quoted 7 lines
smp_load_acquire(x)
... read data from queue ..
...
But yes,store_release(x)should always pair with theload_acquire(x), and the guarantee is that if theload_acquirereads the value that thestore_releasestored, then all subsequent reads in thread #2 will see all preceding writes in thread #1.
I agree with this bit, but it's only half the picture.
Quoted 1 line
then you should need no other barriers.
But I don't agree with this. You're missing half the barriers. There should be *four* barriers. The document mandates only 3 barriers, and uses READ_ONCE() where the fourth should be, i.e.:
thread #1 thread #2
smp_load_acquire(head) ... read data from queue .. smp_store_release(tail)
READ_ONCE(tail)
... add data to queue ..
smp_store_release(head)
but I think that READ_ONCE() should instead be smp_load_acquire() so that the read of the data is ordered before it gets overwritten by the writer, ordering with respect to accesses on tail (it now implies smp_read_barrier_depends() which I think is sufficient).
Another way of looking at it is that smp_store_release(tail) needs pairing with something, so it should be:
thread #1 thread #2
smp_load_acquire(head) ... read data from queue .. smp_store_release(tail)
smp_load_acquire(tail)
... add data to queue ..
smp_store_release(head)
Take your example, reorder the threads and add the missing indices accesses:
thread #1 thread #2
smp_load_acquire(x) ... read data from queue .. tail++
read tail;
... add data to queue ..
smp_store_release(x)
Is there anything to stop the cpus doing out-of-order loads/stores such that the data read in thread 2 doesn't come after the update of tail? If that can happen, the data being written by thread 1 may be being read by thread 2 when in fact, it shouldn't see it yet, e.g.:
LOAD head
ACQUIRE_BARRIER
LOAD tail
LOAD head STORE tail++
LOAD tail
STORE data[head]
LOAD data[tail]
RELEASE_BARRIER
STORE head++
I would really like Paul and Will to check me on this.
-~-
Quoted 5 lines
HOWEVER.
I think this is all entirely pointless wrt the pipe buffer use. You don't have a simple queue. You have multiple writers, and you have multiple readers. As a result, you need real locking.
Yes, and I don't deny that. Between readers and readers you do; between writers and writers you do. But barriers are about the coupling between the active reader and the active writer - and even with locking, you *still* need the barriers, it's just that there are barriers implicit in the locking primitives - so they're there, just hidden.
Quoted 3 lines
So don't do the barriers. If you do the barriers, you're almost certainly doing something buggy. You don't have the simple "consumer -> producer" thing. Or rather, you don't _only_ have that thing.
I think what you're thinking of still has a problem. Could you give a simple 'trace' of what it is you're thinking of, particularly in the reader, so that I can see.
I think that the following points need to be considered:
(1) Accessing the ring requires *four* barriers, two read-side and two write-side.
(2) pipe_lock() and pipe_unlock() currently provide the barrier and the code
places them very wide so that they encompass the index access, the data
access and the index update, and order them with respect to pipe->mutex:
pipe_lock(); // barrier #1
... get curbuf and nbufs...
... write data ...
... nbufs++ ...
pipe_unlock(); // barrier #2
pipe_lock(); // barrier #3
... get curbuf and nbufs...
... read data ...
... curbuf++; nbufs--; ...
pipe_unlock(); // barrier #4
The barriers pair up #2->#3 and #4->#1. (3) Multiple readers are serialised against each other by pipe_lock(), and will continue to be so.
(4) Multiple userspace writers are serialised against each other by pipe_lock(), and will continue to be so.
(5) Readers and userspace writers are serialised against each other by pipe_lock(). This could be changed at some point in the future.
(6) pipe_lock() and pipe_unlock() cannot be used by post_notification() as it needs to be able to insert a message from softirq context or with a spinlock held.
(7) It might be possible to use pipe->wait's spinlock to guard access to the ring indices since we might be taking that lock anyway to poke the other side.
(8) We don't want to call copy_page_to/from_iter() with spinlock held.
As we discussed at Plumbers, we could use pipe->wait's spinlock in the from-userspace writer to do something like:
pipe_lock(); ... spin_lock_irq(&pipe->wait->lock); // barrier #1 ... get indices... ... advance index ... spin_unlock_irq(&pipe->wait->lock); ... write data ... pipe_unlock(); // barrier #2
ie. allocate the slot inside the spinlock, then write it whilst holding off the reader with the pipe lock. Yes, that would work as pipe_unlock() acts as the closing barrier. But this doesn't work for post_notification(). That would have to do:
spin_lock_irq(&pipe->wait->lock); // barrier #1 ... get indices... ... write data ... ... advance index ... spin_unlock_irq(&pipe->wait->lock); // barrier #2
which is fine, even if it occurs within the from-userspace writer as the latter is holding the pipe lock. However, consider the reader. If you're thinking of:
pipe_lock(); // barrier #3? ... ... get indices... ... read data ... spin_lock_irq(&pipe->wait->lock); ... advance index ... spin_unlock_irq(&pipe->wait->lock); // barrier #4 pipe_unlock();
that works against the from-userspace writer, but barrier #3 is in the wrong place against post_notification(). We could do this:
pipe_lock(); ... spin_lock_irq(&pipe->wait->lock); // barrier #3 ... get indices... ... read data ... ... advance index ... spin_unlock_irq(&pipe->wait->lock); // barrier #4 pipe_unlock();
which does indeed protect the reader against post_notification(), but it means that the data copy happens with the lock held. An alternative could be:
pipe_lock(); ... spin_lock_irq(&pipe->wait->lock); // barrier #3 ... get indices... spin_unlock_irq(&pipe->wait->lock); ... read data ... spin_lock_irq(&pipe->wait->lock); ... advance index ... spin_unlock_irq(&pipe->wait->lock); // barrier #4 pipe_unlock();
but that would take the spinlock twice.
There shouldn't need to be *any* common lock between the reader and the writer[*] - not even pipe_lock() or pipe->wait, both of which could be split.
[*] Apart from the minor fact that, currently, the writer can violate normal
ring-buffer semantics and go back and continue filling something it's already committed.
David
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 7 lines · David Howells
But I don't agree with this. You're missing half the barriers. There should be *four* barriers. The document mandates only 3 barriers, and uses
READ_ONCE()where the fourth should be, i.e.:thread #1 thread #2
Quoted 7 lines
smp_load_acquire(head)... read data from queue ..smp_store_release(tail)
READ_ONCE(tail)
... add data to queue ..
smp_store_release(head)
The document is right, but you shouldn't do this.
The reason that READ_ONCE() is possible - instead of a smp_load_acquire() - is that there's now an address dependency chain from the READ_ONCE to the subsequent writes of the data.
And while there isn't any barrier, a data or control dependency to a _write_ does end up ordering things (even on alpha - it's only the read->read dependencies that might be unordered on alpha).
But again, don't do this.
Also, you ignored the part where I told you to not do this because we already have locking.
I'm not goign to discuss this further. Locking works. Spinlocks are cheap. Lockless algorithms that need atomics aren't even cheaper than
spinlocks: they can in fact scale *worse*, because they don't have the nice queuing optimization that our spinlock have.
Lockless algorithms are great if they can avoid the contention on the lock and instead only work on distributed data and avoid contention entirely.
But in this case the lock would be right next to the data anyway, so even that case doesn't hold.
Linus
Re: Do we need to correct barriering in circular-buffers.rst?
In reply to David HowellsQuoted 6 lines · David Howells
But I don't agree with this. You're missing half the barriers. There should be *four* barriers. The document mandates only 3 barriers, and uses
READ_ONCE()where the fourth should be, i.e.:thread #1 thread #2
Quoted 8 lines
smp_load_acquire(head)... read data from queue ..smp_store_release(tail)
READ_ONCE(tail)
... add data to queue ..
smp_store_release(head)
Notably your READ_ONCE() pseudo code is lacking a conditional; kernel/events/ring_buffer.c writes it like so:
* kernel user
*
* if (LOAD ->data_tail) { LOAD ->data_head
* (A) smp_rmb() (C)
* STORE $data LOAD $data
* smp_wmb() (B) smp_mb() (D)
* STORE ->data_head STORE ->data_tail * }
*
* Where A pairs with D, and B pairs with C.
*
* In our case (A) is a control dependency that separates the load of
* the ->data_tail and the stores of $data. In case ->data_tail
* indicates there is no room in the buffer to store $data we do not. *
* D needs to be a full barrier since it separates the data READ
* from the tail WRITE.
*
* For B a WMB is sufficient since it separates two WRITEs, and for C
* an RMB is sufficient since it separates two READs.
Where 'kernel' is the producer and 'user' is the consumer. This was written before load-acquire and store-release came about (I _think_), and I've so far resisted updating B to store-release because smp_wmb() is actually cheaper than store-release on a number of architectures (notably ARM).
C ought to be a load-aquire, and D really should be a store-release, but I don't think the perf userspace has that (or uses C11).
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 27 lines · Peter Zijlstra
Quoted 6 lines · David Howells
But I don't agree with this. You're missing half the barriers. There should be *four* barriers. The document mandates only 3 barriers, and uses
READ_ONCE()where the fourth should be, i.e.:thread #1 thread #2
Quoted 8 lines
smp_load_acquire(head)... read data from queue ..smp_store_release(tail)
READ_ONCE(tail)
... add data to queue ..
smp_store_release(head)Notably your
READ_ONCE()pseudo code is lacking a conditional;kernel/events/ring_buffer.cwrites it like so:* kernel user
** if (LOAD ->data_tail) { LOAD ->data_head * (A) smp_rmb() (C) * STORE $data LOAD $data * smp_wmb() (B) smp_mb() (D) * STORE ->data_head STORE ->data_tail
Quoted 7 lines
* }
*
* Where A pairs with D, and B pairs with C.
*
* In our case (A) is a control dependency that separates the load of
* the ->data_tail and the stores of $data. In case ->data_tail
* indicates there is no room in the buffer to store $data we do not.
To elaborate on this, dependencies are tricky... ;-)
For the record, the LKMM doesn't currently model "order" derived from control dependencies to a _plain_ access (even if the plain access is a write): in particular, the following is racy (as far as the current LKMM is concerned):
C rb
{ }
P0(int *tail, int *data, int *head)
{
if (READ_ONCE(*tail)) {
*data = 1;
smp_wmb();
WRITE_ONCE(*head, 1);
}
}P1(int *tail, int *data, int *head)
{
int r0;
int r1;
r0 = READ_ONCE(*head);
smp_rmb();
r1 = *data;
smp_mb();
WRITE_ONCE(*tail, 1);
}Replacing the plain "*data = 1" with "WRITE_ONCE(*data, 1)" (or doing s/READ_ONCE(*tail)/smp_load_acquire(tail)) suffices to avoid the race. Maybe I'm short of imagination this morning... but I can't currently see how the compiler could "break" the above scenario.
I also didn't spend much time thinking about it. memory-barriers.txt has a section "CONTROL DEPENDENCIES" dedicated to "alerting developers using control dependencies for ordering". That's quite a long section (and probably still incomplete); the last paragraph summarizes: ;-)
(*) Compilers do not understand control dependencies. It is therefore
your job to ensure that they do not break your code.
Andrea
Quoted 15 lines
*
* D needs to be a full barrier since it separates the data READ
* from the tail WRITE.
*
* For B a WMB is sufficient since it separates two WRITEs, and for C
* an RMB is sufficient since it separates two READs.Where 'kernel' is the producer and 'user' is the consumer. This was written before load-acquire and store-release came about (I _think_), and I've so far resisted updating B to store-release because
smp_wmb()is actually cheaper than store-release on a number of architectures (notably ARM).C ought to be a load-aquire, and D really should be a store-release, but I don't think the perf userspace has that (or uses C11).
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 30 lines · Andrea Parri
For the record, the LKMM doesn't currently model "order" derived from control dependencies to a _plain_ access (even if the plain access is a write): in particular, the following is racy (as far as the current LKMM is concerned):
C rb
{ }
P0(int *tail, int *data, int *head){ if (READ_ONCE(*tail)) { *data = 1; smp_wmb(); WRITE_ONCE(*head, 1); } }
P1(int *tail, int *data, int *head){ int r0; int r1; r0 = READ_ONCE(*head); smp_rmb(); r1 = *data; smp_mb(); WRITE_ONCE(*tail, 1); }
Quoted 4 lines
Replacing the plain "*data = 1" with "
WRITE_ONCE(*data, 1)" (or doing s/READ_ONCE(*tail)/smp_load_acquire(tail)) suffices to avoid the race. Maybe I'm short of imagination this morning... but I can't currently see how the compiler could "break" the above scenario.
The compiler; if sufficiently smart; is 'allowed' to change P0 into something terrible like:
*data = 1;
if (*tail) {
smp_wmb();
*head = 1;
} else
*data = 0;(assuming it knows *data was 0 from a prior store or something)
Using WRITE_ONCE() defeats this because volatile indicates external visibility.
Quoted 4 lines
I also didn't spend much time thinking about it. memory-barriers.txt has a section "CONTROL DEPENDENCIES" dedicated to "alerting developers using control dependencies for ordering". That's quite a long section (and probably still incomplete); the last paragraph summarizes: ;-)
Barring LTO the above works for perf because of inter-translation-unit function calls, which imply a compiler barrier.
Now, when the compiler inlines, it looses that sync point (and thereby subtlely changes semantics from the non-inline variant). I suspect LTO does the same and can cause subtle breakage through this transformation.
Quoted 2 lines
(*) Compilers do not understand control dependencies. It is therefore
your job to ensure that they do not break your code.
It is one the list of things I want to talk about when I finally get relevant GCC and LLVM people in the same room ;-)
Ideally the compiler can be taught to recognise conditionals dependent on 'volatile' loads and disallow problematic transformations around them.
I've added Nick (clang) and Jose (GCC) on Cc, hopefully they can help find the right people for us.
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 48 lines · Peter Zijlstra
Quoted 30 lines · Andrea Parri
For the record, the LKMM doesn't currently model "order" derived from control dependencies to a _plain_ access (even if the plain access is a write): in particular, the following is racy (as far as the current LKMM is concerned):
C rb
{ }
P0(int *tail, int *data, int *head){ if (READ_ONCE(*tail)) { *data = 1; smp_wmb(); WRITE_ONCE(*head, 1); } }
P1(int *tail, int *data, int *head){ int r0; int r1; r0 = READ_ONCE(*head); smp_rmb(); r1 = *data; smp_mb(); WRITE_ONCE(*tail, 1); }Quoted 4 lines
Replacing the plain "*data = 1" with "
WRITE_ONCE(*data, 1)" (or doing s/READ_ONCE(*tail)/smp_load_acquire(tail)) suffices to avoid the race. Maybe I'm short of imagination this morning... but I can't currently see how the compiler could "break" the above scenario.The compiler; if sufficiently smart; is 'allowed' to change P0 into something terrible like:
*data = 1; if (*tail) { smp_wmb(); *head = 1; } else *data = 0;
Quoted 4 lines
(assuming it knows *data was 0 from a prior store or something)
Using
WRITE_ONCE()defeats this because volatile indicates external visibility.
The much simpler solution might be writing it like:
if (READ_ONCE(*tail) {
barrier();
*data = 1;
smp_wmb();
WRITE_ONCE(*head, 1);
}which I don't think the compiler is allowed to mess up.
Re: Do we need to correct barriering in circular-buffers.rst?
In reply to Peter ZijlstraQuoted 41 lines · Peter Zijlstra
Quoted 30 lines · Andrea Parri
For the record, the LKMM doesn't currently model "order" derived from control dependencies to a _plain_ access (even if the plain access is a write): in particular, the following is racy (as far as the current LKMM is concerned):
C rb
{ }
P0(int *tail, int *data, int *head){ if (READ_ONCE(*tail)) { *data = 1; smp_wmb(); WRITE_ONCE(*head, 1); } }
P1(int *tail, int *data, int *head){ int r0; int r1; r0 = READ_ONCE(*head); smp_rmb(); r1 = *data; smp_mb(); WRITE_ONCE(*tail, 1); }Quoted 4 lines
Replacing the plain "*data = 1" with "
WRITE_ONCE(*data, 1)" (or doing s/READ_ONCE(*tail)/smp_load_acquire(tail)) suffices to avoid the race. Maybe I'm short of imagination this morning... but I can't currently see how the compiler could "break" the above scenario.The compiler; if sufficiently smart; is 'allowed' to change P0 into something terrible like:
Quoted 6 lines
*data = 1;
if (*tail) {
smp_wmb();
*head = 1;
} else
*data = 0;I don't think so. This snippet has different side effects than P0. P0 never assigned *data to zero, this snippet does. P0 *may* assign *data to 1. This snippet will unconditionally assign to *data, conditionally 1 or 0. I think the REVERSE transform (from your snippet to P0) would actually be legal, but IANALL (I am not a language lawyer; haven't yet passed the BAR).
Quoted 3 lines
(assuming it knows *data was 0 from a prior store or something)
Oh, in that case I'm less sure (I still don't think so, but I would love to be proven wrong, preferably with a godbolt link). I think the best would be to share a godbolt.org link to a case that's clearly broken, or cite the relevant part of the ISO C standard (which itself leaves room for interpretation), otherwise the discussion is too hypothetical. Those two things are single-handedly the best way to communicate with compiler folks.
Quoted 3 lines
Using
WRITE_ONCE()defeats this because volatile indicates external visibility.
Could data be declared as a pointer to volatile qualified int?
Quoted 6 lines
Quoted 5 lines
I also didn't spend much time thinking about it. memory-barriers.txt has a section "CONTROL DEPENDENCIES" dedicated to "alerting developers using control dependencies for ordering". That's quite a long section (and probably still incomplete); the last paragraph summarizes: ;-)
Quoted 6 lines
Barring LTO the above works for perf because of inter-translation-unit function calls, which imply a compiler barrier.
Now, when the compiler inlines, it looses that sync point (and thereby subtlely changes semantics from the non-inline variant). I suspect LTO does the same and can cause subtle breakage through this transformation.
Do you have a bug report or godbolt link for the above? I trust that you're familiar enough with the issue to be able to quickly reproduce it? These descriptions of problems are difficult for me to picture in code or generated code, and when I try to read through memory-barriers.txt my eyes start to glaze over (then something else catches fire and I have to go put that out). Having a concise test case I think would better illustrate potential issues with LTO that we'd then be able to focus on trying to fix/support.
We definitely have heavy hitting language lawyers and our LTO folks are super sharp; I just don't have the necessary compiler experience just yet to be as helpful in these discussions as we need but I'm happy to bring them cases that don't work for the kernel and drive their resolution.
Quoted 13 lines
Quoted 3 lines
(*) Compilers do not understand control dependencies. It is therefore
your job to ensure that they do not break your code.It is one the list of things I want to talk about when I finally get relevant GCC and LLVM people in the same room ;-)
Ideally the compiler can be taught to recognise conditionals dependent on 'volatile' loads and disallow problematic transformations around them.
I've added Nick (clang) and Jose (GCC) on Cc, hopefully they can help find the right people for us.
Signature · 2 lines
Thanks, ~Nick Desaulniers
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 9 lines · Nick Desaulniers
Quoted 6 lines · Peter Zijlstra
Barring LTO the above works for perf because of inter-translation-unit function calls, which imply a compiler barrier.
Now, when the compiler inlines, it looses that sync point (and thereby subtlely changes semantics from the non-inline variant). I suspect LTO does the same and can cause subtle breakage through this transformation.
Quoted 9 lines
Do you have a bug report or godbolt link for the above? I trust that you're familiar enough with the issue to be able to quickly reproduce it? These descriptions of problems are difficult for me to picture in code or generated code, and when I try to read through memory-barriers.txt my eyes start to glaze over (then something else catches fire and I have to go put that out). Having a concise test case I think would better illustrate potential issues with LTO that we'd then be able to focus on trying to fix/support.
Further, if we identified a case were the existing invariants were broken under LTO, such a case could be added to CONFIG_DEBUG_LOCKING_API_SELFTESTS (or whatever the most appropriate kself test is).
Signature · 2 lines
Thanks, ~Nick Desaulniers
Re: Do we need to correct barriering in circular-buffers.rst?
In reply to Nick DesaulniersQuoted 9 lines · Nick Desaulniers
On Fri, Sep 27, 2019 at 5:49 AM Peter Zijlstra <[email protected]> wrote:
Oh, in that case I'm less sure (I still don't think so, but I would love to be proven wrong, preferably with a godbolt link). I think the best would be to share a godbolt.org link to a case that's clearly broken, or cite the relevant part of the ISO C standard (which itself leaves room for interpretation), otherwise the discussion is too hypothetical. Those two things are single-handedly the best way to communicate with compiler folks.
Ah, I'm not sure current compilers will get it wrong -- and I'm trying to be preemptive here. I'm looking for a guarantee that compilers will recognise and respect control depenencies.
The C language spec does not recognise the construct at _all_ and I'd be fine with it being behind some optional compiler knob.
So far we're mostly very careful when using it, recognising that compilers can screw us over because they have no clue.
Quoted 4 lines
Quoted 2 lines
Using
WRITE_ONCE()defeats this because volatile indicates external visibility.Could data be declared as a pointer to volatile qualified int?
It's not actually 'int' data, mostly its a void* and we use memcpy().
Quoted 2 lines
Quoted 2 lines
Barring LTO the above works for perf because of inter-translation-unit function calls, which imply a compiler barrier.
Having looked at it again, I think we're good and have sufficient barrier() in there to not rely on function calls being a sync point.
Quoted 13 lines
Quoted 3 lines
Now, when the compiler inlines, it looses that sync point (and thereby subtlely changes semantics from the non-inline variant). I suspect LTO does the same and can cause subtle breakage through this transformation.
Do you have a bug report or godbolt link for the above? I trust that you're familiar enough with the issue to be able to quickly reproduce it? These descriptions of problems are difficult for me to picture in code or generated code, and when I try to read through memory-barriers.txt my eyes start to glaze over (then something else catches fire and I have to go put that out). Having a concise test case I think would better illustrate potential issues with LTO that we'd then be able to focus on trying to fix/support.
Quoted 5 lines
We definitely have heavy hitting language lawyers and our LTO folks are super sharp; I just don't have the necessary compiler experience just yet to be as helpful in these discussions as we need but I'm happy to bring them cases that don't work for the kernel and drive their resolution.
Like said; I've not seen it go wrong -- but it is one of the things I'm always paranoid about with LTO.
Furthermore, if it were to go wrong, it'd be a very subtle data race and finding it would be super hard and painful. Which is again why I would love to get compiler folks on board to actually support control dependencies in some way.
Like I said before, something like: "disallowing store hoists over control flow depending on a volatile load" would be sufficient I think.
Yes this is outside of ISO/C, but it is something that is really important to us because, as said above, getting it wrong would be *SUPER* painful.
So basically I'm asking for a language extension I suppose; a new guarantee from the compiler's memory model that does not exist _at_all_ in the spec, one that we're actively using.
And I'm hoping that getting the compilers to (optionally) support this is easier than waiting another few decades until Paul McKenney has wrestled the C committee into sanity and only then (maybe) getting it. Look at the horrible mess vs data dependencies and consume ordering (another fun thing we're actively using lots that the compilers are still struggling with).
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 2 lines · Peter Zijlstra
Like I said before, something like: "disallowing store hoists over control flow depending on a volatile load" would be sufficient I think.
We need to add 'control flow depending on an inline-asm' to that. We also very much use that.
Re: Do we need to correct barriering in circular-buffers.rst?
Quoted 6 lines · Peter Zijlstra
Quoted 2 lines · Peter Zijlstra
Like I said before, something like: "disallowing store hoists over control flow depending on a volatile load" would be sufficient I think.
We need to add 'control flow depending on an inline-asm' to that. We also very much use that.
An example of that would be something like:
bool spin_try_lock(struct spinlock *lock)
{
u32 zero = 0;
if (atomic_try_cmpxchg_relaxed(&lock->val, &zero, 1)) {
smp_acquire__after_ctrl_dep(); /* aka smp_rmb() */
return true;
}
return false;
}(I think most our actual trylock functions use cmpxchg_acquire(), but the above would be a valid implementation -- and it is the simplest construct using smp_acquire__after_ctrl_dep() I could come up with in a hurry)