Skip to contentSkip to conversation

Broken terminal due to echo bufferring

PATCH Superseded Mikulas Patocka 3 participants 12 messages Dec 9, 2013 – Dec 13, 2013 TTY layer and serial drivers

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

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
Index: linux-3.12.4/drivers/tty/n_tty.c
===================================================================
@@ -783,21 +783,10 @@ static size_t __process_echoes(struct tt
 static 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);
 
Applied
#1 lore raw

PATCH 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

#2 lore raw
In reply to Mikulas Patocka
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 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.

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

#3 lore raw
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 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.

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

#4 lore raw
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 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.

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.

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 in process_echoes when 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_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.

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

#5 lore raw
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 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.

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 the flush_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 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.

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 in process_echoes when 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_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).

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_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_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.

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

#6 lore raw

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

#7 lore raw
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

#8 lore raw

PATCH 1/1 Broken terminal due to echo bufferring

In reply to Mikulas Patocka

Just 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

#9 lore raw
In reply to Mikulas Patocka
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 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.

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 the flush_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 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.

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 in process_echoes when 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_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).

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_ONCE if 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_ONCE is 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_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.

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_commit load from userspace that performing a load-acquire here and store-release in commit_echoes would 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_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.

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_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.

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

#10 lore raw
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 in process_echoes when 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_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).

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_ONCE if 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.

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_ONCE is 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_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.

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.

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_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.

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_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 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 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.

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

#11 lore raw
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 in process_echoes when 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_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).

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 serialization

Sure, 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_ONCE if 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.

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_ONCE is 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();
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_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.

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 5 lines

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?

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 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

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_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.

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_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.

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_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 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 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.

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

Quoted 2 lines

The kernel 3.11 doesn't have this bug (it doesn't check for L_ECHO in process_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