[PATCH tty-next 0/4] tty: Fix ^C echo

[PATCH tty-next 0/4] tty: Fix ^C echo

[Peter Hurley]

Greg,

Sometimes when interrupting terminal output, the '^C' won't be echoed
until more output is echoed. This is fairly repeatable by interrupting
'cat large-file'.

The common reason for this is because the tty write buffer is full,
even though the write buffer _should_ have been flushed already.
Because of a known deadlock, the pty driver does not perform a
write buffer flush in its flush_buffer() method.

[Refer to the FIXME in pty_flush_buffer() from commit
d945cb9cce20ac7143c2de8d88b187f62db99bdc,
'pty: Rework the pty layer to use the normal buffering logic']

Patch 1 fixes a stale comment.
Patch 2 adds the necessary interfaces to avoid direct linkage
between the N_TTY line discipline and the pty driver.
Patch 3 avoids the deadlock while performing the write buffer flush.
Patch 4 fixes a less common condition introduced by the echo batch
processing added in 3.12.

Alan,

I cc'd you because of your recent involvement in other
tty patches/bug fixes and because it's your FIXME comment.
Feel free to ignore and/or let me know you would prefer not to
be bothered.

Regards,

Peter Hurley (4):
  tty: Fix stale tty_buffer_flush() comment
  tty: Add flush_nested() tty driver method and accessor
  tty: Fix pty flush
  n_tty: Flush echoes for signal chars

 drivers/tty/n_tty.c        |  8 +++--
 drivers/tty/pty.c          | 32 ++++++++++++++++++-
 drivers/tty/tty_buffer.c   | 79 ++++++++++++++++++++++++++++++++++++++++++++--
 drivers/tty/tty_ioctl.c    | 21 ++++++++++++
 include/linux/tty.h        |  1 +
 include/linux/tty_driver.h |  1 +
 include/linux/tty_flip.h   |  2 ++
 7 files changed, 137 insertions(+), 7 deletions(-)

-- 
1.8.1.2

[PATCH tty-next 1/4] tty: Fix stale tty_buffer_flush() comment

[Peter Hurley]

Commit d7a68be4f265be10e24be931c257af30ca55566b,
'tty: Only perform flip buffer flush from tty_buffer_flush()',
removed buffer flushing from flush_to_ldisc().

Fix function header comment which describes the former behavior.

Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---
 drivers/tty/tty_buffer.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/drivers/tty/tty_buffer.c b/drivers/tty/tty_buffer.c
index 6664f0d..2cea1ab 100644
--- a/drivers/tty/tty_buffer.c
+++ b/drivers/tty/tty_buffer.c
@@ -208,9 +208,7 @@ static void tty_buffer_free(struct tty_port *port, struct tty_buffer *b)
  *	tty_buffer_flush		-	flush full tty buffers
  *	@tty: tty to flush
  *
- *	flush all the buffers containing receive data. If the buffer is
- *	being processed by flush_to_ldisc then we defer the processing
- *	to that function
+ *	flush all the buffers containing receive data.
  *
  *	Locking: takes buffer lock to ensure single-threaded flip buffer
  *		 'consumer'
-- 
1.8.1.2

[PATCH tty-next 2/4] tty: Add flush_nested() tty driver method and accessor

[Peter Hurley]

To avoid a lock inversion deadlock, the pty driver must distinguish
when the flush_buffer() caller already holds its own tty_buffer buf->lock
(currently only in N_TTY's receive_buf() path when handling signals).

Extend tty_driver ops interface with the flush_nested() method.
Add the tty_driver_flush_nested() accessor which uses flush_nested()
(if the driver declares it); otherwise, uses tty_driver_flush_buffer().

Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---
 drivers/tty/n_tty.c        |  4 ++--
 drivers/tty/tty_ioctl.c    | 21 +++++++++++++++++++++
 include/linux/tty.h        |  1 +
 include/linux/tty_driver.h |  1 +
 4 files changed, 25 insertions(+), 2 deletions(-)

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index bd01d97..72a5c32 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -1191,7 +1191,7 @@ static void n_tty_receive_break(struct tty_struct *tty)
 			/* flushing needs exclusive termios_rwsem */
 			up_read(&tty->termios_rwsem);
 			n_tty_flush_buffer(tty);
-			tty_driver_flush_buffer(tty);
+			tty_driver_flush_nested(tty);
 			down_read(&tty->termios_rwsem);
 		}
 		return;
@@ -1271,7 +1271,7 @@ n_tty_receive_signal_char(struct tty_struct *tty, int signal, unsigned char c)
 		/* flushing needs exclusive termios_rwsem */
 		up_read(&tty->termios_rwsem);
 		n_tty_flush_buffer(tty);
-		tty_driver_flush_buffer(tty);
+		tty_driver_flush_nested(tty);
 		down_read(&tty->termios_rwsem);
 	}
 	if (I_IXON(tty))
diff --git a/drivers/tty/tty_ioctl.c b/drivers/tty/tty_ioctl.c
index 6fd60fe..e64eb23 100644
--- a/drivers/tty/tty_ioctl.c
+++ b/drivers/tty/tty_ioctl.c
@@ -90,6 +90,27 @@ void tty_driver_flush_buffer(struct tty_struct *tty)
 EXPORT_SYMBOL(tty_driver_flush_buffer);
 
 /**
+ *	tty_driver_flush_nested	-	discard internal buffer
+ *	@tty: terminal
+ *
+ *	Line disciplines must call this flavor of tty_driver_flush_buffer()
+ *	if calling from their .receive_buf() method. The pty driver
+ *	in particular requires special handling to avoid a lock inversion
+ *	deadlock (see tty_buffer_flush_nested()).
+ *
+ *	A normal flush_buffer() is performed for drivers without this
+ *	extension.
+ */
+void tty_driver_flush_nested(struct tty_struct *tty)
+{
+	if (tty->ops->flush_nested)
+		tty->ops->flush_nested(tty);
+	else
+		tty_driver_flush_buffer(tty);
+}
+EXPORT_SYMBOL(tty_driver_flush_nested);
+
+/**
  *	tty_throttle		-	flow control
  *	@tty: terminal
  *
diff --git a/include/linux/tty.h b/include/linux/tty.h
index 9d234dc..de1f85f 100644
--- a/include/linux/tty.h
+++ b/include/linux/tty.h
@@ -414,6 +414,7 @@ extern int tty_put_char(struct tty_struct *tty, unsigned char c);
 extern int tty_chars_in_buffer(struct tty_struct *tty);
 extern int tty_write_room(struct tty_struct *tty);
 extern void tty_driver_flush_buffer(struct tty_struct *tty);
+extern void tty_driver_flush_nested(struct tty_struct *tty);
 extern void tty_throttle(struct tty_struct *tty);
 extern void tty_unthrottle(struct tty_struct *tty);
 extern int tty_throttle_safe(struct tty_struct *tty);
diff --git a/include/linux/tty_driver.h b/include/linux/tty_driver.h
index 756a609..4937e16 100644
--- a/include/linux/tty_driver.h
+++ b/include/linux/tty_driver.h
@@ -269,6 +269,7 @@ struct tty_operations {
 	void (*hangup)(struct tty_struct *tty);
 	int (*break_ctl)(struct tty_struct *tty, int state);
 	void (*flush_buffer)(struct tty_struct *tty);
+	void (*flush_nested)(struct tty_struct *tty);
 	void (*set_ldisc)(struct tty_struct *tty);
 	void (*wait_until_sent)(struct tty_struct *tty, int timeout);
 	void (*send_xchar)(struct tty_struct *tty, char ch);
-- 
1.8.1.2

[PATCH tty-next 3/4] tty: Fix pty flush

[Peter Hurley]

The pty driver writes output directly to the 'other' pty's flip
buffers; ie., the pty's write buffer is the other pty's flip buffer.
Flushing the write buffer for a pty was a FIXME because flushing the
other pty's flip buffer allows for a potential deadlock:

CPU 0                                        CPU 1
flush_to_ldisc
  mutex_lock(buf->lock)  <-----------+
  receive_buf                        |
    .                                |  flush_to_ldisc
    .                             +--|--> mutex_lock(buf->lock)
    tty_driver_flush_buffer       |  |    receive_buf
      pty_flush_buffer            |  |      .
        tty_buffer_flush          |  |      .
          mutex_lock(buf->lock) --+  |      tty_buffer_flush_buffer
                                     |        pty_flush_buffer
                                     |          tty_buffer_flush
                                     +--------    mutex_lock(buf->lock)

To resolve the lock inversion deadlock:
- Add a flush_nested() method to the pty driver (which is invoked by
  the line discipline when flushing the driver write buffer in the
  receive_buf() handling).
- Add tty_buffer_flush_nested(), which relies on the caller holding
  its own buf->lock and a shared mutex to so the state of the 'other'
  CPU can be inferred where a deadlock might otherwise have occurred.

Use the port->buf_mutex (which is otherwise unused by the pty driver)
of the lowest-address tty to ensure only a single mutex is used,
regardless of which pty is performing the flush.

Annotate the mutex lock as a nested lock class for lockdep: note the
buf->lock claimed here is the 'other' pty's buf->lock.

Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---
 drivers/tty/pty.c        | 32 ++++++++++++++++++++-
 drivers/tty/tty_buffer.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/tty_flip.h |  2 ++
 3 files changed, 108 insertions(+), 1 deletion(-)

diff --git a/drivers/tty/pty.c b/drivers/tty/pty.c
index 25c9bc7..54a2d6a 100644
--- a/drivers/tty/pty.c
+++ b/drivers/tty/pty.c
@@ -227,7 +227,33 @@ static void pty_flush_buffer(struct tty_struct *tty)
 
 	if (!to)
 		return;
-	/* tty_buffer_flush(to); FIXME */
+
+	tty_buffer_flush(to);
+
+	if (to->packet) {
+		spin_lock_irqsave(&tty->ctrl_lock, flags);
+		tty->ctrl_status |= TIOCPKT_FLUSHWRITE;
+		wake_up_interruptible(&to->read_wait);
+		spin_unlock_irqrestore(&tty->ctrl_lock, flags);
+	}
+}
+
+static void pty_flush_buffer_nested(struct tty_struct *tty)
+{
+	struct tty_struct *to = tty->link;
+	unsigned long flags;
+	struct mutex *mutex;
+
+	if (!to)
+		return;
+
+	/* Use a single mutex for the pty pair */
+	if (tty < to)
+		mutex = &tty->port->buf_mutex;
+	else
+		mutex = &to->port->buf_mutex;
+	tty_buffer_flush_nested(to, mutex);
+
 	if (to->packet) {
 		spin_lock_irqsave(&tty->ctrl_lock, flags);
 		tty->ctrl_status |= TIOCPKT_FLUSHWRITE;
@@ -451,6 +477,7 @@ static const struct tty_operations master_pty_ops_bsd = {
 	.write = pty_write,
 	.write_room = pty_write_room,
 	.flush_buffer = pty_flush_buffer,
+	.flush_nested = pty_flush_buffer_nested,
 	.chars_in_buffer = pty_chars_in_buffer,
 	.unthrottle = pty_unthrottle,
 	.set_termios = pty_set_termios,
@@ -467,6 +494,7 @@ static const struct tty_operations slave_pty_ops_bsd = {
 	.write = pty_write,
 	.write_room = pty_write_room,
 	.flush_buffer = pty_flush_buffer,
+	.flush_nested = pty_flush_buffer_nested,
 	.chars_in_buffer = pty_chars_in_buffer,
 	.unthrottle = pty_unthrottle,
 	.set_termios = pty_set_termios,
@@ -626,6 +654,7 @@ static const struct tty_operations ptm_unix98_ops = {
 	.write = pty_write,
 	.write_room = pty_write_room,
 	.flush_buffer = pty_flush_buffer,
+	.flush_nested = pty_flush_buffer_nested,
 	.chars_in_buffer = pty_chars_in_buffer,
 	.unthrottle = pty_unthrottle,
 	.set_termios = pty_set_termios,
@@ -644,6 +673,7 @@ static const struct tty_operations pty_unix98_ops = {
 	.write = pty_write,
 	.write_room = pty_write_room,
 	.flush_buffer = pty_flush_buffer,
+	.flush_nested = pty_flush_buffer_nested,
 	.chars_in_buffer = pty_chars_in_buffer,
 	.unthrottle = pty_unthrottle,
 	.set_termios = pty_set_termios,
diff --git a/drivers/tty/tty_buffer.c b/drivers/tty/tty_buffer.c
index 2cea1ab..4d0d2ef 100644
--- a/drivers/tty/tty_buffer.c
+++ b/drivers/tty/tty_buffer.c
@@ -233,6 +233,81 @@ void tty_buffer_flush(struct tty_struct *tty)
 }
 
 /**
+ *	tty_buffer_flush_nested		-	flush full tty buffers
+ *	@tty: tty to flush
+ *	@mutex: lock to distinguish 1st from subsequent caller
+ *
+ *	Special-purpose buffer flush for ptys receiving data (in ldisc's
+ *	receive_buf() path). Resolves lock inversion deadlock when both
+ *	paired ptys concurrently attempt flushing the write buffer (the
+ *	other's input tty_buffers).
+ *
+ *	Locking: Caller already holds its buf->lock (@tty is the 'other' pty)
+ *
+ *	Possible lock scenarios:
+ *	1) Caller successfully claims @mutex and @tty->port->buf->lock;
+ *	   no contention, flush buffer
+ *	2) Caller successfully claims @mutex but not @tty->port->buf->lock;
+ *	   wait for @tty->port->buf->lock;
+ *	   2a) @tty->port->buf->lock owner releases lock; caller claims lock
+ *	       and completes
+ *	   2b) while caller waits, @tty->port->buf->lock owner attempts buffer
+ *	       flush of caller's pty; @tty->port->buf->lock owner executes
+ *	       scenario 3 below, and releases lock; caller claims lock and
+ *	       completes.
+ *	3) Caller cannot successfully claim @mutex
+ *	   By inference, @tty->port->buf->lock owner is waiting for caller's
+ *	   buf->lock (since caller must hold its own buf->lock to call this
+ *	   this function); because the @tty->port->buf->lock owner is waiting,
+ *	   its buffers can be flushed without danger of concurrent changes.
+ *
+ *	The buffer flush in scenario 3 cannot free the current head buffer and
+ *	cannot alter its read index: processing the head buffer is in-progress
+ *	by the @tty->port->buf->lock owner (waiting in scenario 2b).
+ *
+ *	The release order of @mutex first and @tty->port->buf->lock next is
+ *	essential; if the release order is reversed, the 1st caller creates a
+ *	race window which could allow another thread to claim the
+ *	@tty->port->buf->lock and yet observe the locked @mutex and erroneously
+ *	concluded the 1st caller is stuck waiting.
+ */
+
+void tty_buffer_flush_nested(struct tty_struct *tty, struct mutex *mutex)
+{
+	struct tty_port *port = tty->port;
+	struct tty_bufhead *buf = &port->buf;
+	struct tty_buffer *next;
+
+	if (mutex_trylock(mutex)) {
+		atomic_inc(&buf->priority);
+		mutex_lock_nested(&buf->lock, 1);
+		while ((next = buf->head->next) != NULL) {
+			tty_buffer_free(port, buf->head);
+			buf->head = next;
+		}
+		buf->head->read = buf->head->commit;
+		atomic_dec(&buf->priority);
+		mutex_unlock(mutex);
+		mutex_unlock(&buf->lock);
+	} else {
+		/* Because the buf->lock owner is in-progress processing the
+		 * head buffer, free only the buffers after head. Also,
+		 * the tail buffer may be in concurrent use by a parallel
+		 * pty write, so don't free the last buffer; only truncate.
+		 */
+		next = buf->head->next;
+		while (next != NULL) {
+			struct tty_buffer *tmp = next->next;
+			if (tmp != NULL)
+				tty_buffer_free(port, next);
+			else
+				tmp->read = tmp->commit;
+			next = tmp;
+		}
+	}
+}
+
+/**
  *	tty_buffer_request_room		-	grow tty buffer if needed
  *	@tty: tty structure
  *	@size: size desired
diff --git a/include/linux/tty_flip.h b/include/linux/tty_flip.h
index c28dd52..803e67d 100644
--- a/include/linux/tty_flip.h
+++ b/include/linux/tty_flip.h
@@ -38,4 +38,6 @@ static inline int tty_insert_flip_string(struct tty_port *port,
 extern void tty_buffer_lock_exclusive(struct tty_port *port);
 extern void tty_buffer_unlock_exclusive(struct tty_port *port);
 
+extern void tty_buffer_flush_nested(struct tty_struct *tty, struct mutex *);
+
 #endif /* _LINUX_TTY_FLIP_H */
-- 
1.8.1.2

[PATCH tty-next 4/4] n_tty: Flush echoes for signal chars

[Peter Hurley]

Since echoes are batched and only flushed when completing the
current input processing, signal chars may appear in subsequent
output rather than trailing current output. Although the echo byte
code is immediately added to the echo buffer, the echo buffer
processing may be deferred. Also, because the signal is sent before
the echo buffer is processed, the tty state may change before the
echo buffer is flushed.

Preserve observed order; flush echoes before signalling.

Cc: <stable@vger.kernel.org> # 3.12.x
Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---
 drivers/tty/n_tty.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index 72a5c32..2c9dc7b 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -1278,7 +1278,9 @@ n_tty_receive_signal_char(struct tty_struct *tty, int signal, unsigned char c)
 		start_tty(tty);
 	if (L_ECHO(tty)) {
 		echo_char(c, tty);
-		commit_echoes(tty);
+		flush_echoes(tty);
+		if (tty->ops->flush_chars)
+			tty->ops->flush_chars(tty);
 	}
 	isig(signal, tty);
 	return;
-- 
1.8.1.2

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[One Thousand Gnomes]

> I cc'd you because of your recent involvement in other
> tty patches/bug fixes and because it's your FIXME comment.
> Feel free to ignore and/or let me know you would prefer not to
> be bothered.

It does seem horribly convoluted and likely to dig bigger long term holes
than the one its filling. The tty layer has suffered far too much from
"dodging one bullet by being clever and then getting shot at twice more"

Bigger question (and one I'm not going to try and untangle at quarter to
midnight). Is there any reason that the buffer locking has to be per tty
not a shared lock in some cases.

My thinking is that we never sit hogging the buffer lock for long periods
(even though someone has now made it a mutex which seems an odd
performance choice) and it is the deepest lock in the subsystem we take

So:

if the tty_buffer contained a mutex and a pointer to that mutex then for
the pty pairs you could set them to point to the same mutex but default
to separate mutexes.

At that point you swap all the locks on the mutex to simply lock through
the pointer, you don't need the nested hack and there are no special case
paths or uglies in the general code. The only special is that pty init
paths set the points to both point at the same mutex and no kittens die.

Alan

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[Peter Hurley]

On 12/02/2013 07:01 PM, One Thousand Gnomes wrote:
>> I cc'd you because of your recent involvement in other
>> tty patches/bug fixes and because it's your FIXME comment.
>> Feel free to ignore and/or let me know you would prefer not to
>> be bothered.
>
> It does seem horribly convoluted and likely to dig bigger long term holes
> than the one its filling. The tty layer has suffered far too much from
> "dodging one bullet by being clever and then getting shot at twice more"

Alan,

Thanks for the feedback.

I think any solution will be seriously constrained by the larger design
choice; the simplicity and performance of direct writes into a shared
buffer has trade-offs.

I chose what I felt was the simplest route; the code itself is
straightforward. Maybe I could move the locking documentation into the
changelog instead?

Setting aside the parallel flush interface complications (which in some
form is necessary even with a shared lock), there are a limited number
of solutions to concurrent pty buffer flushes:
1. Leave it broken.
2. As submitted.
3. Drop the buf->lock before flushing. This was the other solution I
    seriously considered, because a parallel flush interface would not
    be necessary then.
    The problem with this solution is that input processing would need
    to be aborted and restarted in case the current buffer data had been
    flushed in parallel while the buf->lock was unowned; this requires
    bubbling up return values from n_tty_receive_break() and
    n_tty_receive_signal_char(), plus the actual processed char count
    would need to propagate as well.
4. Do the flush in flush_to_ldisc(). This is variation on 3, because
    current input processing would still need to abort. This solution
    suffers in that the echo may still be deferred, since at the time
    of processing the signal, the other pty write buffer may still be
    full.
5. Probably a few others I haven't thought of.

 > Bigger question (and one I'm not going to try and untangle at quarter to
 > midnight). Is there any reason that the buffer locking has to be per tty
 > not a shared lock in some cases.

I'm not sure what kind of impact a partial half-duplex pty design would
really have.

> My thinking is that we never sit hogging the buffer lock for long periods
> (even though someone has now made it a mutex which seems an odd
> performance choice)

Uncontended mutex lock performance is on-par with uncontended spinlock;
both use a single bus-locked r/m/w instruction.

The buffer lock is mostly uncontended because it only excludes the
consumer-side; ie., only excludes flush_to_ldisc() from tty_buffer_flush().
The driver-side doesn't use buf->lock for access.

The use of a mutex for buf->lock allows the n_tty_receive_buf() path to
claim a read lock on termios changes with a r/w semaphore, termios_rwsem.

> and it is the deepest lock in the subsystem we take
>
> So:
>
> if the tty_buffer contained a mutex and a pointer to that mutex then for
> the pty pairs you could set them to point to the same mutex but default
> to separate mutexes.
>
> At that point you swap all the locks on the mutex to simply lock through
> the pointer, you don't need the nested hack and there are no special case
> paths or uglies in the general code.

To claim the buf->lock in any form from within the receive_buf() path
will require some construct that informs the pty driver's flush_buffer()
method that the buf->lock has already been claimed; otherwise,
double-claim deadlock.

These types of nested lock problems are common when different layers use
the same interface (the fb subsystem's use of the vt driver is another
example).

> The only special is that pty init
> paths set the points to both point at the same mutex and no kittens die.

I like the ptr-to-a-shadow-lock idiom, thanks for sharing.

Regards,
Peter Hurley

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[One Thousand Gnomes]

> These types of nested lock problems are common when different layers use
> the same interface (the fb subsystem's use of the vt driver is another
> example).

They are, and they end up nasty and eventually become impossible to fix.
Better to fix the underlying fundamental error as and when we can. The
current state of vt and fb and drm and handling accelerated scrolling of
a quota warning on drm on fb on vt is a testimony to what happens if you
don't go back and fix it properly now and then.

In this case I would argue there is a fundamental error. That is trying to
combine locking of the structures for buffers and locking the receive
path. It's a mistake and I don't see how you can properly clean up the
tty layer with that mix of high and low level lock in one. It's already
turned into a hackfest with buf->priority.

The old code wasn't the right answer either but did isolate the locks
better.


We've got three confused locks IMHO all stuck in as one

- integrity of the buffer queue
- lifetime of a buffer (don't free a buffer as someone else is
  processing it)
- serialization of flush_to_ldisc

(as an aside it was historically always required that a low_latency
caller correctly implemented its own serialization because you can't
really get that locking totally clean except in the driver either)


It's a bit of a drastic rethink of the idiom but the networking layer
basically does this, and has to solve exactly the same problem space


	while((buf = tty_buffer_dequeue(port)) != NULL) {
		if (receive_buf(tty, buf) < 0) {
			tty_buffer_requeue_head(port, buf);
			break;
		}
	}

tty_buffer_dequeue is trivial enough, tty_buffer_requeue_head is also
trivial because we are single threading flush_to_ldisc. Flushing just
requires ensuring we don't requeue the buffer so we have

	tty_buffer_requeue_head(port, buf)
	{
		lock(&port->buf.lock);
		if (port->buf.clock == buf->clock)
			requeue;
		else
			kfree
	}

	tty_buffer_flush(port)
	{
		port->buf.clock++;
		free buffers in queue
	}

Flush is trivial - increment clock, empty queue. The lifetime handling
will ensure the current buffer is either processed or returned but not
requeued.

Queuing data is also trivial - we just add to the buffer that is at the
end of the queue, or start a new buffer if empty. The requeue_head will
deal with the rest of it automagically

Downsides - slightly more locking, probably several things I've missed.

Upsides - tty buffer locking is clear and self contained, we invoke
flush_to_ldisc without holding what are really low level locks, queue
manipulation in flush_to_ldisc works just like anywhere else. The buffer
is owned by the tty which means the tty must free it, which means the tty
can 'borrow' a buffer for ldisc internal queueing without having to copy
all the bytes and we get the backpressure on the queue for free as the
network layer does.

It does mean touching every ldisc but as far as I can see with the
exception of n_tty the change in each case is (as usual) trivial.

As a PS: I think the termios is probably an RCU problem. The semaphore
seemed to make sense when I did it, but in hindsight I think I made the
wrong call.

Alan

Convert termios to RCU (was Re: [PATCH tty-next 0/4] tty: Fix ^C echo)

[Peter Hurley]

On 12/03/2013 09:20 AM, One Thousand Gnomes wrote:
> As a PS: I think the termios is probably an RCU problem. The semaphore
> seemed to make sense when I did it, but in hindsight I think I made the
> wrong call.

Alan,

Converting safe termios access to RCU is a really good idea.

Massive changeset though, if only because tty->termios would have to be
a struct termios __rcu *.

Regards,
Peter Hurley

Re: Convert termios to RCU (was Re: [PATCH tty-next 0/4] tty: Fix ^C echo)

[Peter Hurley]

On 12/03/2013 12:23 PM, Peter Hurley wrote:
> On 12/03/2013 09:20 AM, One Thousand Gnomes wrote:
>> As a PS: I think the termios is probably an RCU problem. The semaphore
>> seemed to make sense when I did it, but in hindsight I think I made the
>> wrong call.

Unfortunately, not without overhauling the console_lock().

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[Peter Hurley]

On 12/03/2013 09:20 AM, One Thousand Gnomes wrote:
>> These types of nested lock problems are common when different layers use
>> the same interface (the fb subsystem's use of the vt driver is another
>> example).
>
> They are, and they end up nasty and eventually become impossible to fix.
> Better to fix the underlying fundamental error as and when we can. The
> current state of vt and fb and drm and handling accelerated scrolling of
> a quota warning on drm on fb on vt is a testimony to what happens if you
> don't go back and fix it properly now and then.
>
> In this case I would argue there is a fundamental error. That is trying to
> combine locking of the structures for buffers and locking the receive
> path. It's a mistake and I don't see how you can properly clean up the
> tty layer with that mix of high and low level lock in one. It's already
> turned into a hackfest with buf->priority.
>
> The old code wasn't the right answer either but did isolate the locks
> better.
>
>
> We've got three confused locks IMHO all stuck in as one
>
> - integrity of the buffer queue
> - lifetime of a buffer (don't free a buffer as someone else is
>    processing it)
> - serialization of flush_to_ldisc

Not so much confused as simply merged. Input processing is inherently
single-threaded; it makes sense to rely on that at the highest level
possible.

On smp, locked instructions and cache-line contention on the tty_buffer
list ptrs and read_buf indices account for more than 90% of the time cost
in the read path for real hardware (and over 95% for ptys).

Firewire, which is capable of sustained throughput in excess of 40MB/sec,
struggles to get over 5MB/sec through the tty layer. [And drm output
is orders-of-magnitude slower than that, which is just sad...]

buf->priority isn't a hackfest; it's a zero-cost-in-read-path mechanism
for interrupting input processing, similar to the clock (or generation)
approach.

Although using locks is satisfyingly symmetrical, input processing vs.
buffer flush is an asymmetric problem.

> (as an aside it was historically always required that a low_latency
> caller correctly implemented its own serialization because you can't
> really get that locking totally clean except in the driver either)
>
>
> It's a bit of a drastic rethink of the idiom but the networking layer
> basically does this, and has to solve exactly the same problem space
>
>
> 	while((buf = tty_buffer_dequeue(port)) != NULL) {
> 		if (receive_buf(tty, buf) < 0) {
> 			tty_buffer_requeue_head(port, buf);
> 			break;
> 		}
> 	}
>
> tty_buffer_dequeue is trivial enough, tty_buffer_requeue_head is also
> trivial because we are single threading flush_to_ldisc. Flushing just
> requires ensuring we don't requeue the buffer so we have
>
> 	tty_buffer_requeue_head(port, buf)
> 	{
> 		lock(&port->buf.lock);
> 		if (port->buf.clock == buf->clock)
> 			requeue;
> 		else
> 			kfree
> 	}
>
> 	tty_buffer_flush(port)
> 	{
> 		port->buf.clock++;
> 		free buffers in queue
> 	}
>
> Flush is trivial - increment clock, empty queue. The lifetime handling
> will ensure the current buffer is either processed or returned but not
> requeued.
>
> Queuing data is also trivial - we just add to the buffer that is at the
> end of the queue, or start a new buffer if empty. The requeue_head will
> deal with the rest of it automagically
>
> Downsides - slightly more locking, probably several things I've missed.
>
> Upsides - tty buffer locking is clear and self contained, we invoke
> flush_to_ldisc without holding what are really low level locks, queue
> manipulation in flush_to_ldisc works just like anywhere else. The buffer
> is owned by the tty which means the tty must free it, which means the tty
> can 'borrow' a buffer for ldisc internal queueing without having to copy
> all the bytes and we get the backpressure on the queue for free as the
> network layer does.
>
> It does mean touching every ldisc but as far as I can see with the
> exception of n_tty the change in each case is (as usual) trivial.

While that would work, it's expensive extra locking in a path that 99.999%
of the time doesn't need it. I'd rather explore other solutions.

The clock/generation method seems like it might yield a lockless solution
for this problem, but maybe creates another one because the driver-side
would need to stamp the buffer (in essence, a flush could affect data
that has not yet been copied from the driver).

Still, it might be worth seeing if a solution lies in scheduling only
one flush_to_ldisc() per tty_buffer (per port) and letting it sleep
if receive_buf() can't accept more data [N_TTY would awaken the worker
instead of queueing it].

Regards,
Peter Hurley

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[One Thousand Gnomes]

> Not so much confused as simply merged. Input processing is inherently
> single-threaded; it makes sense to rely on that at the highest level
> possible.

I would disagree entirely. You want to minimise the areas affected by a
given lock. You also want to lock data not code. Correctness comes before
speed. You optimise it when its right, otherwise you end up in a nasty
mess when you discover you've optimised to assumptions that are flawed.

> On smp, locked instructions and cache-line contention on the tty_buffer
> list ptrs and read_buf indices account for more than 90% of the time cost
> in the read path for real hardware (and over 95% for ptys).

Yes I'm uncomfortably aware of that for modern SMP hardware, and also
that simply ripping out the buffering will screw the real low end people
(eg M68K and friends)

> Firewire, which is capable of sustained throughput in excess of 40MB/sec,
> struggles to get over 5MB/sec through the tty layer. [And drm output
> is orders-of-magnitude slower than that, which is just sad...]

And what protocols do you care about 5MB/second - n_tty - no ? For the
high speed protocols you are trying to fix a lost cause. By the time
we've gone piddling around with tty buffers and serialized tty queues
firing bytes through tasks and the like you already lost.

For drm I assume you mean the framebuffer console logic ? Last time I
benched that except for the Poulsbo it was bottlenecked on the GPU - not
that I can type at 5MB/second anyway. Not that fixing the performance of
the various bits wouldn't be a good thing too especially on the output
end.

> While that would work, it's expensive extra locking in a path that 99.999%
> of the time doesn't need it. I'd rather explore other solutions.

How about getting the high speed paths out of the whole tty buffer
layer ? Almost every line discipline can be a fastpath directly to the
network layer. If optimisation is the new obsession then we can cut the
crap entirely by optimising for networking not making it a slave of n_tty.

Starting at the beginning

we have locks on rx because
- we want serialized rx
- we have buffer lifetimes
- we have buffer queues
- we have loads of flow control parameters

Only n_tty needs the buffers (maybe some of irda but irda hasn't worked
for years afaik). IRQ receive paths are serialized (and as a bonus can be
pinned to a CPU). Flow control is n_tty stuff, everyone else simply fires
it at their network layer as fast as possible and net already does the
work.

Keep a single tty_buf in the tty for batching at any given time, and
private so no locks at all

Have a wrapper via
ld->receive(tty, buf)

which fires the tty_buf at the ldisc and allocates a new empty one

tty_queue_bytes(tty, buf, flags, len)

which adds to the buffer, and if full calls ld->queue and then carries on
the copying cycle

and

ld->receive_direct(tty, buf, flags, len)

which allows block mode devices to blast bytes directly at the queue (ie
all the USB 3G stuff, firewire, etc) without going via any additional
copies.

For almost all ldiscs

ld->receive would be

ld->receive_direct(tty, buf->buf, buf->flags, buf->len);
free buffer

For n_tty type stuff

ld->receive is basically much of tty_flip_buffer_push

ld->receive_direct allocates tty_buffers and copies into it

We may even be able to optimise some of the n_tty cases into the
fastpath afterwards (notably raw, no echo)

For anything receiving in blocks that puts us close to (but not quite at)
ethernet kinds of cleanness for network buffer delivery.

Worth me looking into ?

> The clock/generation method seems like it might yield a lockless solution
> for this problem, but maybe creates another one because the driver-side
> would need to stamp the buffer (in essence, a flush could affect data
> that has not yet been copied from the driver).

But it has arrived in the driver so might not matter. That requires a
little thought!

Alan

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[Greg Kroah-Hartman]

On Mon, Dec 02, 2013 at 04:12:01PM -0500, Peter Hurley wrote:
> Greg,
> 
> Sometimes when interrupting terminal output, the '^C' won't be echoed
> until more output is echoed. This is fairly repeatable by interrupting
> 'cat large-file'.
> 
> The common reason for this is because the tty write buffer is full,
> even though the write buffer _should_ have been flushed already.
> Because of a known deadlock, the pty driver does not perform a
> write buffer flush in its flush_buffer() method.
> 
> [Refer to the FIXME in pty_flush_buffer() from commit
> d945cb9cce20ac7143c2de8d88b187f62db99bdc,
> 'pty: Rework the pty layer to use the normal buffering logic']
> 
> Patch 1 fixes a stale comment.
> Patch 2 adds the necessary interfaces to avoid direct linkage
> between the N_TTY line discipline and the pty driver.
> Patch 3 avoids the deadlock while performing the write buffer flush.
> Patch 4 fixes a less common condition introduced by the echo batch
> processing added in 3.12.
> 
> Alan,
> 
> I cc'd you because of your recent involvement in other
> tty patches/bug fixes and because it's your FIXME comment.
> Feel free to ignore and/or let me know you would prefer not to
> be bothered.

Peter, this series doesn't fix the ^C echo problem that Karl recently
reported, so I'll hold off in applying it for now.

thanks,

greg k-h

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[Peter Hurley]

On 12/08/2013 08:12 PM, Greg Kroah-Hartman wrote:
> On Mon, Dec 02, 2013 at 04:12:01PM -0500, Peter Hurley wrote:
>> Greg,
>>
>> Sometimes when interrupting terminal output, the '^C' won't be echoed
>> until more output is echoed. This is fairly repeatable by interrupting
>> 'cat large-file'.
>>
>> The common reason for this is because the tty write buffer is full,
>> even though the write buffer _should_ have been flushed already.
>> Because of a known deadlock, the pty driver does not perform a
>> write buffer flush in its flush_buffer() method.
>>
>> [Refer to the FIXME in pty_flush_buffer() from commit
>> d945cb9cce20ac7143c2de8d88b187f62db99bdc,
>> 'pty: Rework the pty layer to use the normal buffering logic']
>>
>> Patch 1 fixes a stale comment.
>> Patch 2 adds the necessary interfaces to avoid direct linkage
>> between the N_TTY line discipline and the pty driver.
>> Patch 3 avoids the deadlock while performing the write buffer flush.
>> Patch 4 fixes a less common condition introduced by the echo batch
>> processing added in 3.12.
>>
>> Alan,
>>
>> I cc'd you because of your recent involvement in other
>> tty patches/bug fixes and because it's your FIXME comment.
>> Feel free to ignore and/or let me know you would prefer not to
>> be bothered.
>
> Peter, this series doesn't fix the ^C echo problem that Karl recently
> reported, so I'll hold off in applying it for now.

Yeah, please discard this. It does fix some problems but I don't really
like how it goes about fixing them. I've been exploring some ideas
based on my discussion with Alan but nothing fruitful yet.

Regards,
Peter Hurley

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[Peter Hurley]

On 12/04/2013 07:13 PM, One Thousand Gnomes wrote:
>> Not so much confused as simply merged. Input processing is inherently
>> single-threaded; it makes sense to rely on that at the highest level
>> possible.
>
> I would disagree entirely. You want to minimise the areas affected by a
> given lock. You also want to lock data not code. Correctness comes before
> speed. You optimise it when its right, otherwise you end up in a nasty
> mess when you discover you've optimised to assumptions that are flawed.

Sorry for the delayed reply, Alan; what little free time I had was spent
snuffing out regressions :/

Sure, I understand that ideally locks protect data, not operations.
But I think maybe you're missing my point. Almost every lock, even at
inception, is somewhat optimized; otherwise, every datum would have its
own lock. Eliminating overlapping locks is a common optimization in stable
code.

In this case, an already broken bit of code is just only still broken.
buf->lock is also fairly simple to break apart (although I don't want to
because of the performance hit) which is not characteristic of locks
which protect operations.


>> Firewire, which is capable of sustained throughput in excess of 40MB/sec,
>> struggles to get over 5MB/sec through the tty layer. [And drm output
>> is orders-of-magnitude slower than that, which is just sad...]
>
> And what protocols do you care about 5MB/second - n_tty - no ? For the
> high speed protocols you are trying to fix a lost cause. By the time
> we've gone piddling around with tty buffers and serialized tty queues
> firing bytes through tasks and the like you already lost.
>
> For drm I assume you mean the framebuffer console logic ? Last time I
> benched that except for the Poulsbo it was bottlenecked on the GPU - not
> that I can type at 5MB/second anyway. Not that fixing the performance of
> the various bits wouldn't be a good thing too especially on the output
> end.

For drm, I actually mean GEM object deletion, which is typically fenced
and thus appears to be GPU-bound. What's really needed there is deferred
deletion, like kfree_rcu(), with partial synchronization on allocation
failures only.

I mostly care about output speed; unfortunately, that's the input side
at the other end :)

>> While that would work, it's expensive extra locking in a path that 99.999%
>> of the time doesn't need it. I'd rather explore other solutions.
>
> How about getting the high speed paths out of the whole tty buffer
> layer ? Almost every line discipline can be a fastpath directly to the
> network layer. If optimisation is the new obsession then we can cut the
> crap entirely by optimising for networking not making it a slave of n_tty.
>
> Starting at the beginning
>
> we have locks on rx because
> - we want serialized rx
> - we have buffer lifetimes
> - we have buffer queues
> - we have loads of flow control parameters
>
> Only n_tty needs the buffers (maybe some of irda but irda hasn't worked
> for years afaik). IRQ receive paths are serialized (and as a bonus can be
> pinned to a CPU). Flow control is n_tty stuff, everyone else simply fires
> it at their network layer as fast as possible and net already does the
> work.
>
> Keep a single tty_buf in the tty for batching at any given time, and
> private so no locks at all
>
> Have a wrapper via
> ld->receive(tty, buf)
>
> which fires the tty_buf at the ldisc and allocates a new empty one
>
> tty_queue_bytes(tty, buf, flags, len)
>
> which adds to the buffer, and if full calls ld->queue and then carries on
> the copying cycle
>
> and
>
> ld->receive_direct(tty, buf, flags, len)
>
> which allows block mode devices to blast bytes directly at the queue (ie
> all the USB 3G stuff, firewire, etc) without going via any additional
> copies.
>
> For almost all ldiscs
>
> ld->receive would be
>
> ld->receive_direct(tty, buf->buf, buf->flags, buf->len);
> free buffer
>
> For n_tty type stuff
>
> ld->receive is basically much of tty_flip_buffer_push
>
> ld->receive_direct allocates tty_buffers and copies into it
>
> We may even be able to optimise some of the n_tty cases into the
> fastpath afterwards (notably raw, no echo)
>
> For anything receiving in blocks that puts us close to (but not quite at)
> ethernet kinds of cleanness for network buffer delivery.
>
> Worth me looking into ?

I have to give this a lot more thought.

The universality of n_tty is important, and costs real cycles on servers and
such. It's not just about typing speed.

>> The clock/generation method seems like it might yield a lockless solution
>> for this problem, but maybe creates another one because the driver-side
>> would need to stamp the buffer (in essence, a flush could affect data
>> that has not yet been copied from the driver).
>
> But it has arrived in the driver so might not matter. That requires a
> little thought!

This is my next experiment.

Regards,
Peter Hurley

Re: [PATCH tty-next 0/4] tty: Fix ^C echo

[One Thousand Gnomes]

> > Worth me looking into ?
> 
> I have to give this a lot more thought.
> 
> The universality of n_tty is important, and costs real cycles on servers and
> such. It's not just about typing speed.

For most systems its about ppp performance and nothing much else in real
use. I'm not arguing for this as an alternative to making n_tty better,
but that it's a far better way to deal with a lot of the other stuff.

If the GPU is allocating and freeing GEM objects a lot to do console then
it's probably doing it wrong. Several of the drivers don't accelerate
console (because of the locking issues) and others use the GPU to do
blits because they don't implement memory management based tricks like
double mapping the framebuffer and shifting offsets.

Some of the userspace is also not really optimised for modern 3D graphics
either - a text terminal is after all just a big texture that moves
offset and gets the content updated now and then.

For low speed devices its also generally broken because the framebuffer
layer is obsessed with printing *everything* and scrolling everything,
not blasting through the text data and reconstructing the framebuffer
level changes once per vblank. The result of doing an ugly hack on that
is quite extra-ordinary even on vesafb.

Alan