Broken terminal due to echo bufferring
PATCH 1/1 Broken terminal due to echo bufferring
Hi
I discovered that kernel 3.12 has broken terminal handling.
I created this program to show the problem:
#include <stdio.h>
#include <unistd.h>
int main(void)
{
int c;
while ((c = getchar()) != EOF) {
if (c == '\n') write(1, "prompt>", 7);
}
return 0;
}Each time the user presses enter, the program prints "prompt>". Normally, when you press enter, you should see:
prompt>
prompt>
prompt>
prompt>_
However, with kernel 3.12.4, you occasionally see
prompt>
prompt>
prompt>prompt>
_
This bug happens randomly, it is timing-dependent. I am using single-core 600MHz processor with preemptible kernel, the bug may or may not happen on other computers.
This bug is caused by Peter Hurley's echo buffering patches (cbfd0340ae1993378fd47179db949e050e16e697). The patches change n_tty.c so that it accumulates echoed characters and sends them out in a batch. Something like this happens:
* The user presses enter
* n_tty.c adds '\n' to the echo buffer using echo_char_raw
* n_tty.c adds '\n' to the input queue using put_tty_queue
* A process is switched
* Userspace reads '\n' from the terminal input queue
* Userspace writes the string "prompt>" to the terminal
* A process is switched back
* The echo buffer is flushed
* '\n' from the echo buffer is printed.
Echo bufferring is fundamentally wrong idea - you must make sure that you flush the echo buffer BEFORE you add a character to input queue and BEFORE you send any signal on behalf of that character. If you delay echo, you are breaking behavior of various programs because the program output will be interleaved with the echoed characters.
Here I'm sending a simple patch that disables echo buffering and restores correct behavior. I think you should remove the echo buffering code at all.
Mikulas
--- drivers/tty/n_tty.c | 15 ++------------- 1 file changed, 2 insertions(+), 13 deletions(-)
drivers/tty/n_tty.c +2 -13
@@ -783,21 +783,10 @@ static size_t __process_echoes(struct ttstatic void commit_echoes (struct tty_struct *tty) {struct n_tty_data *ldata = tty->disc_data; -size_t nr, old, echoed; -size_t head; - - head = ldata->echo_head; - old = ldata->echo_commit - ldata->echo_tail; - -/* Process committed echoes if the accumulated # of bytes -* is over the threshold (and try again each time another -* block is accumulated) */ - nr = head - ldata->echo_tail; -if (nr <ECHO_COMMIT_WATERMARK || (nr %ECHO_BLOCK > old %ECHO_BLOCK )) -return ; +size_t echoed;mutex_lock (&ldata->output_lock); - ldata->echo_commit = head; + ldata->echo_commit = ldata->echo_head; echoed =__process_echoes (tty);mutex_unlock (&ldata->output_lock);
Karl Dahlke
AppliedPATCH 1/1 Broken terminal due to echo bufferring
Quoted 3 lines
I discovered that kernel 3.12 has broken terminal handling. I created this program to show the problem:
...
This is very likely the same bug I reported, with subject:
Bug in tty cooked mode kernel 3.12.3
You don't have to write a program for it, just put bash into cooked mode. I demonstrated the bug by switching consoles and hitting return, assuming bash has been placed in cooked mode.
It's very repeatable this way, not so random.
Switch console,hit return, the prompt is on the same line as the previous prompt. It affects every cooked mode program, and of course your compiled program comes up in cooked mode.
It is cooked echo crlf that is the issue.
Programs in raw mode, like ash default in readline mode,
vi, emacs, etc,are ok.
So you don't see it right away.
See the thread with the aforementioned subject line.
I have applied two separate patches hoping to fix this problem, but it remains.
Karl Dahlke
Quoted 52 lines · Mikulas Patocka
Hi
I discovered that kernel 3.12 has broken terminal handling.
I created this program to show the problem:
#include <stdio.h>
#include <unistd.h>int main(void)
{ int c; while ((c = getchar()) != EOF) { if (c == '\n') write(1, "prompt>", 7); } return 0; }Each time the user presses enter, the program prints "prompt>". Normally, when you press enter, you should see:
prompt>
prompt>
prompt>
prompt>_However, with kernel 3.12.4, you occasionally see
prompt>
prompt>
prompt>prompt>
_This bug happens randomly, it is timing-dependent. I am using single-core 600MHz processor with preemptible kernel, the bug may or may not happen on other computers.
This bug is caused by Peter Hurley's echo buffering patches (
cbfd0340ae1993378fd47179db949e050e16e697). The patches changen_tty.cso that it accumulates echoed characters and sends them out in a batch. Something like this happens:* The user presses enter
*n_tty.cadds '\n' to the echo buffer usingecho_char_raw
*n_tty.cadds '\n' to the input queue usingput_tty_queue
* A process is switched
* Userspace reads '\n' from the terminal input queue
* Userspace writes the string "prompt>" to the terminal
* A process is switched back
* The echo buffer is flushed
* '\n' from the echo buffer is printed.
Quoted 5 lines
Echo bufferring is fundamentally wrong idea - you must make sure that you flush the echo buffer BEFORE you add a character to input queue and BEFORE you send any signal on behalf of that character. If you delay echo, you are breaking behavior of various programs because the program output will be interleaved with the echoed characters.
There is nothing fundamentally broken with buffering echoes; it's just that there is a bug wrt when to process the echoes (ie, when to force the output).
In the example you provided, the write() should cause the echoes to flush but doesn't because the commit marker hasn't been advanced.
The commit marker wasn't advanced _yet_ because there is a race window between the reader being woken as a result of the newline and the flush_echoes() which happens with every received input.
Either closing the race window or advancing the commit marker prior to write() output will fix the problem; right now, I'm looking at which is least painful.
Regards,
Peter Hurley
Quoted 69 lines · Peter Hurley
Quoted 52 lines · Mikulas Patocka
Hi
I discovered that kernel 3.12 has broken terminal handling.
I created this program to show the problem:
#include <stdio.h>
#include <unistd.h>int main(void)
{ int c; while ((c = getchar()) != EOF) { if (c == '\n') write(1, "prompt>", 7); } return 0; }Each time the user presses enter, the program prints "prompt>". Normally, when you press enter, you should see:
prompt>
prompt>
prompt>
prompt>_However, with kernel 3.12.4, you occasionally see
prompt>
prompt>
prompt>prompt>
_This bug happens randomly, it is timing-dependent. I am using single-core 600MHz processor with preemptible kernel, the bug may or may not happen on other computers.
This bug is caused by Peter Hurley's echo buffering patches (
cbfd0340ae1993378fd47179db949e050e16e697). The patches changen_tty.cso that it accumulates echoed characters and sends them out in a batch. Something like this happens:* The user presses enter
*n_tty.cadds '\n' to the echo buffer usingecho_char_raw
*n_tty.cadds '\n' to the input queue usingput_tty_queue
* A process is switched
* Userspace reads '\n' from the terminal input queue
* Userspace writes the string "prompt>" to the terminal
* A process is switched back
* The echo buffer is flushed
* '\n' from the echo buffer is printed.Quoted 5 lines
Echo bufferring is fundamentally wrong idea - you must make sure that you flush the echo buffer BEFORE you add a character to input queue and BEFORE you send any signal on behalf of that character. If you delay echo, you are breaking behavior of various programs because the program output will be interleaved with the echoed characters.
There is nothing fundamentally broken with buffering echoes; it's just that there is a bug wrt when to process the echoes (ie, when to force the output).
In the example you provided, the
write()should cause the echoes to flush but doesn't because the commit marker hasn't been advanced.The commit marker wasn't advanced _yet_ because there is a race window between the reader being woken as a result of the newline and the
flush_echoes()which happens with every received input.
Quoted 6 lines
Either closing the race window or advancing the commit marker prior to
write()output will fix the problem; right now, I'm looking at which is least painful.Regards,
Peter Hurley
I still think you should drop this.
The user types on the keyboard so slowly, that lock contention doesn't matter. Specialized programs that use terminal to transmit bulk data don't use cooked mode and echo. So I don't really see any use case where something depends on performance of echoed characters.
Those patches just complicate the code for no benefit.
When you read a variable that may be asynchronously modified, you need ACCESS_ONCE - for example you need this in process_echoes when accessing the variables outside the lock:
if (ACCESS_ONCE(ldata->echo_commit) == ACCESS_ONCE(ldata->echo_tail))
Anyway accessing variables that may change without locks or barriers is generally bad idea and it is hard to verify it. Terminal layer is not performance-sensitive part of the kernel, so it isn't justified to use such dirty tricks.
Another problem: what about this in process_echoes and flush_echoes? if (!L_ECHO(tty) || ldata->echo_commit == ldata->echo_tail)
return;
- so if the user turns off echo, echoes are not performed. But the buffer is not flushed. So when the user turns on echo again, previously buffered characters will be echoed. That is wrong.
Mikulas
Quoted 89 lines · Mikulas Patocka
Quoted 69 lines · Peter Hurley
Quoted 52 lines · Mikulas Patocka
Hi
I discovered that kernel 3.12 has broken terminal handling.
I created this program to show the problem:
#include <stdio.h>
#include <unistd.h>int main(void)
{ int c; while ((c = getchar()) != EOF) { if (c == '\n') write(1, "prompt>", 7); } return 0; }Each time the user presses enter, the program prints "prompt>". Normally, when you press enter, you should see:
prompt>
prompt>
prompt>
prompt>_However, with kernel 3.12.4, you occasionally see
prompt>
prompt>
prompt>prompt>
_This bug happens randomly, it is timing-dependent. I am using single-core 600MHz processor with preemptible kernel, the bug may or may not happen on other computers.
This bug is caused by Peter Hurley's echo buffering patches (
cbfd0340ae1993378fd47179db949e050e16e697). The patches changen_tty.cso that it accumulates echoed characters and sends them out in a batch. Something like this happens:* The user presses enter
*n_tty.cadds '\n' to the echo buffer usingecho_char_raw
*n_tty.cadds '\n' to the input queue usingput_tty_queue
* A process is switched
* Userspace reads '\n' from the terminal input queue
* Userspace writes the string "prompt>" to the terminal
* A process is switched back
* The echo buffer is flushed
* '\n' from the echo buffer is printed.Quoted 5 lines
Echo bufferring is fundamentally wrong idea - you must make sure that you flush the echo buffer BEFORE you add a character to input queue and BEFORE you send any signal on behalf of that character. If you delay echo, you are breaking behavior of various programs because the program output will be interleaved with the echoed characters.
There is nothing fundamentally broken with buffering echoes; it's just that there is a bug wrt when to process the echoes (ie, when to force the output).
In the example you provided, the
write()should cause the echoes to flush but doesn't because the commit marker hasn't been advanced.The commit marker wasn't advanced _yet_ because there is a race window between the reader being woken as a result of the newline and the
flush_echoes()which happens with every received input.Quoted 6 lines
Either closing the race window or advancing the commit marker prior to
write()output will fix the problem; right now, I'm looking at which is least painful.Regards,
Peter HurleyI still think you should drop this.
The user types on the keyboard so slowly, that lock contention doesn't matter. Specialized programs that use terminal to transmit bulk data don't use cooked mode and echo. So I don't really see any use case where something depends on performance of echoed characters.
Quoted 7 lines
Those patches just complicate the code for no benefit.
When you read a variable that may be asynchronously modified, you need
ACCESS_ONCE- for example you need this inprocess_echoeswhen accessing the variables outside the lock:
if (ACCESS_ONCE(ldata->echo_commit)==ACCESS_ONCE(ldata->echo_tail))
Not necessarily. Stale values in an SMP environment may not be a problem; in this case, a possibly stale echo_tail simply means that the output_lock will be obtained unnecessarily (which is cheaper every-so-often than contending over the echo_tail cache line every write, especially on x86 where there is no problem).
Similarly, so many fences had to be passed to get to the echo_commit load from userspace that performing a load-acquire here and store-release in commit_echoes would be ridiculously superfluous.
Quoted 6 lines
Anyway accessing variables that may change without locks or barriers is generally bad idea and it is hard to verify it. Terminal layer is not performance-sensitive part of the kernel, so it isn't justified to use such dirty tricks.
Quoted 6 lines
Another problem: what about this in
process_echoesandflush_echoes? if (!L_ECHO(tty) ||ldata->echo_commit==ldata->echo_tail)return;- so if the user turns off echo, echoes are not performed. But the buffer is not flushed. So when the user turns on echo again, previously buffered characters will be echoed. That is wrong.
The check for !L_ECHO pre-dates my patches; it might be wrong but userspace may have come to rely on this behavior. That said, feel free to submit a fix for that, if you think it's broken.
Regards,
Peter Hurley
Quoted 109 lines · Peter Hurley
Quoted 100 lines · Mikulas Patocka
Quoted 79 lines · Peter Hurley
Quoted 56 lines · Mikulas Patocka
Hi
I discovered that kernel 3.12 has broken terminal handling.
I created this program to show the problem:
#include <stdio.h>
#include <unistd.h>int main(void)
{ int c; while ((c = getchar()) != EOF) { if (c == '\n') write(1, "prompt>", 7); } return 0; }Each time the user presses enter, the program prints "prompt>". Normally,
when you press enter, you should see:prompt>
prompt>
prompt>
prompt>_However, with kernel 3.12.4, you occasionally see
prompt>
prompt>
prompt>prompt>
_This bug happens randomly, it is timing-dependent. I am using single-core
600MHz processor with preemptible kernel, the bug may or may not happen on
other computers.This bug is caused by Peter Hurley's echo buffering patches (
cbfd0340ae1993378fd47179db949e050e16e697). The patches changen_tty.cso
that it accumulates echoed characters and sends them out in a batch. Something like this happens:* The user presses enter
*n_tty.cadds '\n' to the echo buffer usingecho_char_raw
*n_tty.cadds '\n' to the input queue usingput_tty_queue
* A process is switched
* Userspace reads '\n' from the terminal input queue
* Userspace writes the string "prompt>" to the terminal
* A process is switched back
* The echo buffer is flushed
* '\n' from the echo buffer is printed.Quoted 8 lines
Echo bufferring is fundamentally wrong idea - you must make sure that you
flush the echo buffer BEFORE you add a character to input queue and BEFORE
you send any signal on behalf of that character. If you delay echo, you are breaking behavior of various programs because the program output will
be interleaved with the echoed characters.There is nothing fundamentally broken with buffering echoes; it's just that
there is a bug wrt when to process the echoes (ie, when to force the output).In the example you provided, the
write()should cause the echoes to flush but doesn't because the commit marker hasn't been advanced.The commit marker wasn't advanced _yet_ because there is a race window between
the reader being woken as a result of the newline and theflush_echoes()which happens with every received input.Quoted 7 lines
Either closing the race window or advancing the commit marker prior to
write()output will fix the problem; right now, I'm looking at which is least
painful.Regards,
Peter HurleyI still think you should drop this.
The user types on the keyboard so slowly, that lock contention doesn't matter. Specialized programs that use terminal to transmit bulk data don't use cooked mode and echo. So I don't really see any use case where something depends on performance of echoed characters.
Quoted 7 lines
Those patches just complicate the code for no benefit.
When you read a variable that may be asynchronously modified, you need
ACCESS_ONCE- for example you need this inprocess_echoeswhen accessing the variables outside the lock:
if (ACCESS_ONCE(ldata->echo_commit)==ACCESS_ONCE(ldata->echo_tail))
Quoted 6 lines
Not necessarily. Stale values in an SMP environment may not be a problem; in this case, a possibly stale
echo_tailsimply means that theoutput_lockwill be obtained unnecessarily (which is cheaper every-so-often than contending
over theecho_tailcache line every write, especially on x86 where there is no problem).
Note that a single lock doesn't imply memory barrier:
read(variable_1); spin_lock(lock); spin_unlock(lock); read(variable_2); may be reordered to spin_lock(lock); read(variable_2); read(variable_1); spin_unlock(lock);
Two lock do imply a memory barrier. Surely, you can argue that the system takes at least two locks between reading the input queue and writing to the output to compensate for the missing memory barrier. But depending on such guarantees is dirty.
What happens if I write the equivalent of the above program that reads '\n' and writes "prompt>" in the kernel space? Will there still be two locks between those operations? Will there be two locks always in the future?
Also note, that you need ACCESS_ONCE if the variable may change. The compiler may assume during optimizations that the variables that are read don't change.
The compiler may even generate something like this when you read variable "v":
movl v, %eax
cmpl v, %eax
jne nowhere
- of course it doesn't actually generate this code, but legally it could. ACCESS_ONCE is there to prevent this assumption.
I suggest that you change commit_echoes to always write the buffer and flush it with tty->ops->flush_chars(tty). And then, you can drop process_echoes from n_tty_write. And then, there will be no asynchronous access to the buffer pointers.
Quoted 17 lines
Similarly, so many fences had to be passed to get to the
echo_commitload from userspace that performing a load-acquire here and store-release incommit_echoeswould be ridiculously superfluous.Quoted 6 lines
Anyway accessing variables that may change without locks or barriers is generally bad idea and it is hard to verify it. Terminal layer is not performance-sensitive part of the kernel, so it isn't justified to use such dirty tricks.
Quoted 6 lines
Another problem: what about this in
process_echoesandflush_echoes? if (!L_ECHO(tty) ||ldata->echo_commit==ldata->echo_tail)return;- so if the user turns off echo, echoes are not performed. But the buffer is not flushed. So when the user turns on echo again, previously buffered characters will be echoed. That is wrong.
Quoted 3 lines
The check for !L_ECHO pre-dates my patches; it might be wrong but userspace may have come to rely on this behavior. That said, feel free to submit a fix for that, if you think it's broken.
We should just clear the buffer on !L_ECHO. Or maybe (once we get rid of the asynchronous buffer access) do not test here for L_ECHO at all - if L_ECHO isn't set, then nothing is appended to the buffer. Consequently we don't have to check for L_ECHO when we are flushing the buffer.
Quoted 2 lines
Regards,
Peter Hurley
Mikulas
PATCH 1/1 Broken terminal due to echo bufferring
| An involved discussion about race conditions and asynchronous events, | which is beyond me. | Please continue; I'm sure you will figure it out, | and perhaps educate me along the way. | But this thread began with the following program that revealed, | I believe, the same echo crlf bug that I pointed out.
Quoted 11 lines
#include <
stdio.h>
#include <unistd.h>int main(void)
{
int c;
while ((c =getchar()) != EOF) {
if (c == '\n')write(1, "prompt>", 7);
}
return 0;
}
Peter sent me a patch which fixed my bug, in its console switch form. And also seemed to fix the bug whenever I was in a cooked mode program. So I was happy.
For grins I compiled this program, to see if it also
ran properly.
It does, while it is running.
Prompt and newline come out in sequence, in order,
and everything looks right.
Hit control d, for EOF, as the program expects, and all is well.
But hit ^c for interrupt, and as Tilly says,
"All hell done broke loose now."
The tty spills out a bunch of accumulated text that it has displayed in the past. Don't know where it comes from, or why.
I ran the program several times, interrupt,
and the same thing happened each time, even the same stored output, as though it were a 4k block that was retained from somewhere.
Try it and see (with Peter's latest patches).
I may try some variants: this program running in raw mode, using read and write so we don't have half of it using stdio, other standard cooked mode programs that are ^c interruptable.
I guess the tty is an incredibly complicated beast.
Karl Dahlke
Quoted 28 lines · Karl Dahlke
| An involved discussion about race conditions and asynchronous events, | which is beyond me. | Please continue; I'm sure you will figure it out, | and perhaps educate me along the way. | But this thread began with the following program that revealed, | I believe, the same echo crlf bug that I pointed out.Quoted 11 lines
#include <
stdio.h>
#include <unistd.h>int main(void)
{
int c;
while ((c =getchar()) != EOF) {
if (c == '\n')write(1, "prompt>", 7);
}
return 0;
}Peter sent me a patch which fixed my bug, in its console switch form. And also seemed to fix the bug whenever I was in a cooked mode program. So I was happy.
For grins I compiled this program, to see if it also
ran properly.
It does, while it is running.
Prompt and newline come out in sequence, in order,
and everything looks right.
Hit control d, for EOF, as the program expects, and all is well.
Quoted 8 lines
But hit ^c for interrupt, and as Tilly says,
"All hell done broke loose now."
The tty spills out a bunch of accumulated text that it has displayed in the past. Don't know where it comes from, or why.
I ran the program several times, interrupt,
and the same thing happened each time, even the same stored output, as though it were a 4k block that was retained from somewhere.
Try it and see (with Peter's latest patches).
Hi Karl,
That's happening because you're also running the 'tty: Fix ^C echo' patch series which pre-dates this fix and is _not_ compatible with it.
I've already asked Greg to drop that series for other reasons (which he had planned on anyway).
Regards,
Peter Hurley
PATCH 1/1 Broken terminal due to echo bufferring
In reply to Mikulas PatockaJust a followup to my last post.
You don't need to compile the write("prompt>") program to see the bug. Just edit a modest text file with /bin/ed, which runs in cooked mode. As soon as the file comes up, hit ^c.
Lots of old stuff comes spewing out.
Eventually the tty is back and you can edit the file as usual, or quit.
Karl Dahlke
Quoted 131 lines · Mikulas Patocka
Quoted 109 lines · Peter Hurley
Quoted 100 lines · Mikulas Patocka
Quoted 79 lines · Peter Hurley
Quoted 56 lines · Mikulas Patocka
Hi
I discovered that kernel 3.12 has broken terminal handling.
I created this program to show the problem:
#include <stdio.h>
#include <unistd.h>int main(void)
{ int c; while ((c = getchar()) != EOF) { if (c == '\n') write(1, "prompt>", 7); } return 0; }Each time the user presses enter, the program prints "prompt>". Normally,
when you press enter, you should see:prompt>
prompt>
prompt>
prompt>_However, with kernel 3.12.4, you occasionally see
prompt>
prompt>
prompt>prompt>
_This bug happens randomly, it is timing-dependent. I am using single-core
600MHz processor with preemptible kernel, the bug may or may not happen on
other computers.This bug is caused by Peter Hurley's echo buffering patches (
cbfd0340ae1993378fd47179db949e050e16e697). The patches changen_tty.cso
that it accumulates echoed characters and sends them out in a batch. Something like this happens:* The user presses enter
*n_tty.cadds '\n' to the echo buffer usingecho_char_raw
*n_tty.cadds '\n' to the input queue usingput_tty_queue
* A process is switched
* Userspace reads '\n' from the terminal input queue
* Userspace writes the string "prompt>" to the terminal
* A process is switched back
* The echo buffer is flushed
* '\n' from the echo buffer is printed.Quoted 8 lines
Echo bufferring is fundamentally wrong idea - you must make sure that you
flush the echo buffer BEFORE you add a character to input queue and BEFORE
you send any signal on behalf of that character. If you delay echo, you are breaking behavior of various programs because the program output will
be interleaved with the echoed characters.There is nothing fundamentally broken with buffering echoes; it's just that
there is a bug wrt when to process the echoes (ie, when to force the output).In the example you provided, the
write()should cause the echoes to flush but doesn't because the commit marker hasn't been advanced.The commit marker wasn't advanced _yet_ because there is a race window between
the reader being woken as a result of the newline and theflush_echoes()which happens with every received input.Quoted 7 lines
Either closing the race window or advancing the commit marker prior to
write()output will fix the problem; right now, I'm looking at which is least
painful.Regards,
Peter HurleyI still think you should drop this.
The user types on the keyboard so slowly, that lock contention doesn't matter. Specialized programs that use terminal to transmit bulk data don't use cooked mode and echo. So I don't really see any use case where something depends on performance of echoed characters.
Quoted 7 lines
Those patches just complicate the code for no benefit.
When you read a variable that may be asynchronously modified, you need
ACCESS_ONCE- for example you need this inprocess_echoeswhen accessing the variables outside the lock:
if (ACCESS_ONCE(ldata->echo_commit)==ACCESS_ONCE(ldata->echo_tail))Quoted 6 lines
Not necessarily. Stale values in an SMP environment may not be a problem; in this case, a possibly stale
echo_tailsimply means that theoutput_lockwill be obtained unnecessarily (which is cheaper every-so-often than contending
over theecho_tailcache line every write, especially on x86 where there is no problem).Note that a single lock doesn't imply memory barrier:
read(variable_1); spin_lock(lock); spin_unlock(lock); read(variable_2); may be reordered to spin_lock(lock); read(variable_2); read(variable_1); spin_unlock(lock);
Quoted 4 lines
Two lock do imply a memory barrier. Surely, you can argue that the system takes at least two locks between reading the input queue and writing to the output to compensate for the missing memory barrier. But depending on such guarantees is dirty.
To escape from n_tty_read() alone requires passing through (at a minimum)
1. UNLOCK rwsem
2. LOCK wq
3. UNLOCK wq
4. UNLOCK read serialization
Quoted 4 lines
What happens if I write the equivalent of the above program that reads '\n' and writes "prompt>" in the kernel space? Will there still be two locks between those operations? Will there be two locks always in the future?
Out-of-tree breakage is common. Documentation/stable_api_nonsense.txt explains why.
Quoted 3 lines
Also note, that you need
ACCESS_ONCEif the variable may change. The compiler may assume during optimizations that the variables that are read don't change.
Lots of (many? most?) kernel variables change asynchronously and are still read without ACCESS_ONCE(); consider how waitqueue_active() works.
Quoted 7 lines
The compiler may even generate something like this when you read variable "v":
movl v, %eax
cmpl v, %eax
jne nowhere
- of course it doesn't actually generate this code, but legally it could.ACCESS_ONCEis there to prevent this assumption.
Not in this case. The compiler could not possibly prove the loads are unnecessary: n_tty_write() is a globally visible call target. (Besides, the load can't be optimized out because of the LOCK rwsem.)
Quoted 4 lines
I suggest that you change
commit_echoesto always write the buffer and flush it withtty->ops->flush_chars(tty). And then, you can dropprocess_echoesfromn_tty_write. And then, there will be no asynchronous access to the buffer pointers.
process_echoes() cannot be dropped from n_tty_write() because, even without block commits, the driver's output buffer may be full and unable to accept more input. That's why the echo buffer exists.
Quoted 17 lines
Quoted 17 lines
Similarly, so many fences had to be passed to get to the
echo_commitload from userspace that performing a load-acquire here and store-release incommit_echoeswould be ridiculously superfluous.Quoted 12 lines
Anyway accessing variables that may change without locks or barriers is generally bad idea and it is hard to verify it. Terminal layer is not performance-sensitive part of the kernel, so it isn't justified to use such dirty tricks.
Another problem: what about this in
process_echoesandflush_echoes? if (!L_ECHO(tty) ||ldata->echo_commit==ldata->echo_tail)return;- so if the user turns off echo, echoes are not performed. But the buffer is not flushed. So when the user turns on echo again, previously buffered characters will be echoed. That is wrong.
Quoted 8 lines
Quoted 3 lines
The check for !L_ECHO pre-dates my patches; it might be wrong but userspace may have come to rely on this behavior. That said, feel free to submit a fix for that, if you think it's broken.
We should just clear the buffer on !L_ECHO. Or maybe (once we get rid of the asynchronous buffer access) do not test here for
L_ECHOat all - ifL_ECHOisn't set, then nothing is appended to the buffer. Consequently we don't have to check forL_ECHOwhen we are flushing the buffer.
Discarding the echo buffer with L_ECHO -> !L_ECHO changes will almost certainly break something. I considered attempting to push the echo buffer when that change happens in n_tty_set_termios() but simply haven't gotten to it for testing; and that still wouldn't get rid of the need to check if echoes need to be pushed when !L_ECHO.
Regards,
Peter Hurley
Quoted 49 lines · Peter Hurley
Quoted 43 lines · Mikulas Patocka
Quoted 20 lines · Peter Hurley
Quoted 11 lines · Mikulas Patocka
I still think you should drop this.
The user types on the keyboard so slowly, that lock contention doesn't matter. Specialized programs that use terminal to transmit bulk data don't
use cooked mode and echo. So I don't really see any use case where something depends on performance of echoed characters.Quoted 7 lines
Those patches just complicate the code for no benefit.
When you read a variable that may be asynchronously modified, you need
ACCESS_ONCE- for example you need this inprocess_echoeswhen accessing the variables outside the lock:
if (ACCESS_ONCE(ldata->echo_commit)==ACCESS_ONCE(ldata->echo_tail))Quoted 7 lines
Not necessarily. Stale values in an SMP environment may not be a problem; in this case, a possibly stale
echo_tailsimply means that theoutput_lockwill be obtained unnecessarily (which is cheaper every-so-often than contending
over theecho_tailcache line every write, especially on x86 where there is
no problem).Note that a single lock doesn't imply memory barrier:
read(variable_1); spin_lock(lock); spin_unlock(lock); read(variable_2); may be reordered to spin_lock(lock); read(variable_2); read(variable_1); spin_unlock(lock);Quoted 4 lines
Two lock do imply a memory barrier. Surely, you can argue that the system takes at least two locks between reading the input queue and writing to the output to compensate for the missing memory barrier. But depending on such guarantees is dirty.
Quoted 5 lines
To escape from
n_tty_read()alone requires passing through (at a minimum)
1. UNLOCK rwsem
2. LOCK wq
3. UNLOCK wq
4. UNLOCK read serialization
Sure, but you should just add the barriers if they are needed, don't rely on others doing barriers for you. Besides, there is another rw-semaphore implementation that doesn't have any barrier guarantees (include/linux/percpu-rwsem.h).
Quoted 6 lines
Quoted 3 lines
Also note, that you need
ACCESS_ONCEif the variable may change. The compiler may assume during optimizations that the variables that are read don't change.Lots of (many? most?) kernel variables change asynchronously and are still read without
ACCESS_ONCE(); consider howwaitqueue_active()works.
So they should be read with ACCESS_ONCE().
Quoted 11 lines
Quoted 7 lines
The compiler may even generate something like this when you read variable "v":
movl v, %eax
cmpl v, %eax
jne nowhere
- of course it doesn't actually generate this code, but legally it could.ACCESS_ONCEis there to prevent this assumption.Not in this case. The compiler could not possibly prove the loads are unnecessary:
n_tty_write()is a globally visible call target. (Besides, the load can't be optimized out because of the LOCK rwsem.)
The compiler may assume that the variables that it is reading don't change. Usually it doesn't use this assumption (that why omitting ACCESS_ONCE in most cases doesn't result in any observable wrongdoing), but nonetheless, the compiler may use this assumption.
For example, if the compiler proves that action1() and action2() don't change the variable, it may transform this piece of code:
if (variable) {
action1();
action2();
action3();
} else {
action2();
}
into this piece of code:
if (variable)
action1();
action2();
if (variable)
action3();- obviously, if the variable changes asynchronously, it results in unintended bahavior.
Quoted 8 lines
Quoted 4 lines
I suggest that you change
commit_echoesto always write the buffer and flush it withtty->ops->flush_chars(tty). And then, you can dropprocess_echoesfromn_tty_write. And then, there will be no asynchronous access to the buffer pointers.
process_echoes()cannot be dropped fromn_tty_write()because, even without block commits, the driver's output buffer may be full and unable to accept more input. That's why the echo buffer exists.
Let me ask you this question:
Does the function __process_echoes (in 3.12) or process_echoes (in 3.11) guarantee that the echo buffer is emptied and all characters in the buffer are sent to the terminal?
- if it has this guarantee, then you don't need to call that function in n_tty_write. It is just enough to call it before adding the character to the input queue.
- if it doesn't have this guarantee, then then the code is already buggy:
suppose for example this race condition:
1. the user presses enter
2. '\n' is added to the echo buffer
3. the echo buffer is not flushed because tty_write_room returns zero
4. the program reads '\n' from the input buffer
5. the program writes the string "prompt>" to the terminal
6. n_tty_write calls process_echoes, it still doesn't echo anything because tty_write_room returns zero
7. the terminal driver makes some progress and makes some room in its buffer so that tty_write_room no longer returns zero
8. n_tty_write writes the string "prompt>" while '\n' is still sitting in the echo buffer
Another problem - if __process_echoes doesn't flush the echo buffer, who does flush it afterwards? You need to spawn a workqueue that waits on tty->write_wait and flushes the echo buffer when the terminal drivers makes some room.
Quoted 20 lines
Quoted 15 lines
Quoted 9 lines
Quoted 8 lines
Another problem: what about this in
process_echoesandflush_echoes? if (!L_ECHO(tty) ||ldata->echo_commit==ldata->echo_tail)return;- so if the user turns off echo, echoes are not performed. But the buffer
is not flushed. So when the user turns on echo again, previously buffered
characters will be echoed. That is wrong.Quoted 5 lines
The check for !L_ECHO pre-dates my patches; it might be wrong but userspace
may have come to rely on this behavior. That said, feel free to submit a fix
for that, if you think it's broken.Quoted 4 lines
We should just clear the buffer on !L_ECHO. Or maybe (once we get rid of the asynchronous buffer access) do not test here for
L_ECHOat all - ifL_ECHOisn't set, then nothing is appended to the buffer. Consequently we don't have to check forL_ECHOwhen we are flushing the buffer.
Quoted 5 lines
Discarding the echo buffer with
L_ECHO-> !L_ECHO changes will almost certainly break something. I considered attempting to push the echo buffer when that change happens inn_tty_set_termios()but simply haven't gotten to it for testing; and that still wouldn't get rid of the need to check if echoes need to be pushed when !L_ECHO.
If there is !L_ECHO, than no characters are added to the echo buffer. Then, you test L_ECHO again, when flushing the echo buffer.
So I think there's a race condition:
1. L_ECHO is on
2. the user types some characters, they are added to the echo buffer
3. the program turns L_ECHO off
4. process_echoes and flush_echoes see that L_ECHO is off, so they don't flush the buffer - but the buffer still contains the characters
5. some time passes
6. the program turns L_ECHO on
7. the characters typed in step 2. are still in the buffer and they are echoed now - this is WRONG - the characters typed in step 2. should be either echoed immediatelly or not echoed at all
The kernel 3.11 doesn't have this bug (it doesn't check for L_ECHO in process_echoes).
Quoted 2 lines
Regards,
Peter Hurley
Mikulas
Quoted 53 lines · Mikulas Patocka
Quoted 49 lines · Peter Hurley
Quoted 47 lines · Mikulas Patocka
Quoted 20 lines · Peter Hurley
Quoted 11 lines · Mikulas Patocka
I still think you should drop this.
The user types on the keyboard so slowly, that lock contention doesn't matter. Specialized programs that use terminal to transmit bulk data don't
use cooked mode and echo. So I don't really see any use case where something depends on performance of echoed characters.Quoted 7 lines
Those patches just complicate the code for no benefit.
When you read a variable that may be asynchronously modified, you need
ACCESS_ONCE- for example you need this inprocess_echoeswhen accessing the variables outside the lock:
if (ACCESS_ONCE(ldata->echo_commit)==ACCESS_ONCE(ldata->echo_tail))Quoted 7 lines
Not necessarily. Stale values in an SMP environment may not be a problem; in this case, a possibly stale
echo_tailsimply means that theoutput_lockwill be obtained unnecessarily (which is cheaper every-so-often than contending
over theecho_tailcache line every write, especially on x86 where there is
no problem).Note that a single lock doesn't imply memory barrier:
read(variable_1); spin_lock(lock); spin_unlock(lock); read(variable_2); may be reordered to spin_lock(lock); read(variable_2); read(variable_1); spin_unlock(lock);Two lock do imply a memory barrier. Surely, you can argue that the system takes at least two locks between reading the input queue and writing to the output to compensate for the missing memory barrier. But depending on such guarantees is dirty.
Quoted 8 lines
Quoted 5 lines
To escape from
n_tty_read()alone requires passing through (at a minimum)
1. UNLOCK rwsem
2. LOCK wq
3. UNLOCK wq
4. UNLOCK read serializationSure, but you should just add the barriers if they are needed, don't rely on others doing barriers for you.
Sorry, but I'm not add extra memory barriers when adequate barriers already exist, as designed and explained.
Quoted 3 lines
Besides, there is another rw-semaphore implementation that doesn't have any barrier guarantees (
include/linux/percpu-rwsem.h).
Which is why percpu-rwsem is not a drop-in replacement for regular rwsem.
Quoted 8 lines
Quoted 6 lines
Quoted 3 lines
Also note, that you need
ACCESS_ONCEif the variable may change. The compiler may assume during optimizations that the variables that are read don't change.Lots of (many? most?) kernel variables change asynchronously and are still read without
ACCESS_ONCE(); consider howwaitqueue_active()works.So they should be read with
ACCESS_ONCE().
You'll also want to 'fix' most of the existing locks, like rwsem which peeks at the lock count outside any barriers (or any of the other highly- contended paths in other locks as well).
Quoted 33 lines
Quoted 11 lines
Quoted 7 lines
The compiler may even generate something like this when you read variable "v":
movl v, %eax
cmpl v, %eax
jne nowhere
- of course it doesn't actually generate this code, but legally it could.ACCESS_ONCEis there to prevent this assumption.Not in this case. The compiler could not possibly prove the loads are unnecessary:
n_tty_write()is a globally visible call target. (Besides, the load can't be optimized out because of the LOCK rwsem.)The compiler may assume that the variables that it is reading don't change. Usually it doesn't use this assumption (that why omitting
ACCESS_ONCEin most cases doesn't result in any observable wrongdoing), but nonetheless, the compiler may use this assumption.For example, if the compiler proves that
action1()andaction2()don't change the variable, it may transform this piece of code:if (variable) { action1(); action2(); action3(); } else { action2(); } into this piece of code: if (variable) action1(); action2(); if (variable) action3();
Quoted 2 lines
- obviously, if the variable changes asynchronously, it results in unintended bahavior.
Sure, but that's not the situation you brought up; you're suggesting that the compiler will optimize out either/both loads of the echo buffer indices that happen immediately following the LOCK rwsem (or assuming the LOCK rwsem is removed, the beginning of a exported function).
The only way that happens is if the compiler and/or the LOCK barrier is broken; so again, nothing here to fix.
Quoted 9 lines
Quoted 8 lines
Quoted 4 lines
I suggest that you change
commit_echoesto always write the buffer and flush it withtty->ops->flush_chars(tty). And then, you can dropprocess_echoesfromn_tty_write. And then, there will be no asynchronous access to the buffer pointers.
process_echoes()cannot be dropped fromn_tty_write()because, even without block commits, the driver's output buffer may be full and unable to accept more input. That's why the echo buffer exists.
Quoted 5 lines
Let me ask you this question:
Does the function
__process_echoes(in 3.12) orprocess_echoes(in 3.11) guarantee that the echo buffer is emptied and all characters in the buffer are sent to the terminal?
No. __process_echoes does not (and cannot) guarantee that the echo buffer can be completely pushed (and would eliminate the need for a 4K echo buffer if it could).
Quoted 4 lines
- if it has this guarantee, then you don't need to call that function in
n_tty_write. It is just enough to call it before adding the character to the input queue.
Quoted 13 lines
- if it doesn't have this guarantee, then then the code is already buggy:
suppose for example this race condition:
1. the user presses enter
2. '\n' is added to the echo buffer
3. the echo buffer is not flushed becausetty_write_roomreturns zero
4. the program reads '\n' from the input buffer
5. the program writes the string "prompt>" to the terminal
6.n_tty_writecallsprocess_echoes, it still doesn't echo anything becausetty_write_roomreturns zero
7. the terminal driver makes some progress and makes some room in its buffer so thattty_write_roomno longer returns zero
8.n_tty_writewrites the string "prompt>" while '\n' is still sitting in the echo buffer
Yep, known bug.
If you suggest the trivial fix is to always prefer echoes over outgoing output, then that's just as buggy; one end will be able to starve the other and will only ever see it's own writes.
An output 'clock' would be one way to fix this. Need a project? :)
Quoted 4 lines
Another problem - if
__process_echoesdoesn't flush the echo buffer, who does flush it afterwards? You need to spawn a workqueue that waits ontty->write_waitand flushes the echo buffer when the terminal drivers makes some room.
Yep, again known bug, for the same reason, although more complicated:
how to handle signal-driven i/o.
Quoted 41 lines
Quoted 20 lines
Quoted 15 lines
Quoted 9 lines
Quoted 8 lines
Another problem: what about this in
process_echoesandflush_echoes? if (!L_ECHO(tty) ||ldata->echo_commit==ldata->echo_tail)return;- so if the user turns off echo, echoes are not performed. But the buffer
is not flushed. So when the user turns on echo again, previously buffered
characters will be echoed. That is wrong.Quoted 5 lines
The check for !L_ECHO pre-dates my patches; it might be wrong but userspace
may have come to rely on this behavior. That said, feel free to submit a fix
for that, if you think it's broken.Quoted 4 lines
We should just clear the buffer on !L_ECHO. Or maybe (once we get rid of the asynchronous buffer access) do not test here for
L_ECHOat all - ifL_ECHOisn't set, then nothing is appended to the buffer. Consequently we don't have to check forL_ECHOwhen we are flushing the buffer.Quoted 5 lines
Discarding the echo buffer with
L_ECHO-> !L_ECHO changes will almost certainly break something. I considered attempting to push the echo buffer when that change happens inn_tty_set_termios()but simply haven't gotten to it for testing; and that still wouldn't get rid of the need to check if echoes need to be pushed when !L_ECHO.If there is !L_ECHO, than no characters are added to the echo buffer. Then, you test
L_ECHOagain, when flushing the echo buffer.So I think there's a race condition:
1.L_ECHOis on
2. the user types some characters, they are added to the echo buffer
3. the program turnsL_ECHOoff
4.process_echoesandflush_echoessee thatL_ECHOis off, so they don't flush the buffer - but the buffer still contains the characters
5. some time passes
6. the program turnsL_ECHOon
7. the characters typed in step 2. are still in the buffer and they are echoed now - this is WRONG - the characters typed in step 2. should be either echoed immediatelly or not echoed at all
Quoted 2 lines
The kernel 3.11 doesn't have this bug (it doesn't check for
L_ECHOinprocess_echoes).
Yeah, you're right that 3.11- doesn't check for !L_ECHO in the n_tty_write() path; I'll send a patch to fix that (I must have been looking at the wrong tree/branch when I wrote that earlier, sorry).
Regards,
Peter Hurley