[PATCH v2] n_tty: Fix unordered accesses to lockless read buffer

[PATCH v2] n_tty: Fix unordered accesses to lockless read buffer

[Peter Hurley]

Add commit_head buffer index, which the producer-side publishes
after input processing in non-canon mode. This ensures the consumer-side
observes correctly-ordered writes in non-canonical mode (ie., the buffer
data is written before the buffer index is advanced). Fix consumer-side
uses of read_cnt() to use commit_head instead.

Add required memory barriers to the tail index to guarantee
the consumer-side has completed the loads before the producer-side
begins writing new data. Open-code the producer-side receive_room()
into the i/o loop.

Based on work by Christian Riesch <christian.riesch@omicron.at>

Cc: Christian Riesch <christian.riesch@omicron.at>
Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---

Changes from v1:
*  Remove read_tail accesses completely from n_tty_receive_buf_real_raw().
   The computation for copy size does not require the read_cnt() since
   count is already <= available buffer space.
*  commit_head is only published in non-canonical mode. The index is
   synced if the mode is changed in n_tty_set_termios. This becomes
   relevant for a follow-on fix that must back up the read_head in
   canon mode.
*  receive_room() in the producer-side i/o loop is open-coded to
   enable smp_load_acquire() of read_tail. (see updated commit log)
*  ACCESS_ONCE()s removed according to my own review of v1. I can
   expand on the analysis of each of those if someone would like.
*  Stuck with the read_head accesses from exclusive access functions
   like n_tty_set_termios() and n_tty_ioctl() (instead of the v1 usage
   of commit_head)

 drivers/tty/n_tty.c | 74 +++++++++++++++++++++++++++++++----------------------
 1 file changed, 43 insertions(+), 31 deletions(-)

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index 4ddfa60..ccc68a5 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -90,6 +90,7 @@
 struct n_tty_data {
 	/* producer-published */
 	size_t read_head;
+	size_t commit_head;
 	size_t canon_head;
 	size_t echo_head;
 	size_t echo_commit;
@@ -164,15 +165,16 @@ static inline int tty_put_user(struct tty_struct *tty, unsigned char x,
 static int receive_room(struct tty_struct *tty)
 {
 	struct n_tty_data *ldata = tty->disc_data;
+	size_t count = ldata->commit_head - ldata->read_tail;
 	int left;
 
 	if (I_PARMRK(tty)) {
-		/* Multiply read_cnt by 3, since each byte might take up to
+		/* Multiply count by 3, since each byte might take up to
 		 * three times as many spaces when PARMRK is set (depending on
 		 * its flags, e.g. parity error). */
-		left = N_TTY_BUF_SIZE - read_cnt(ldata) * 3 - 1;
+		left = N_TTY_BUF_SIZE - count * 3 - 1;
 	} else
-		left = N_TTY_BUF_SIZE - read_cnt(ldata) - 1;
+		left = N_TTY_BUF_SIZE - count - 1;
 
 	/*
 	 * If we are doing input canonicalization, and there are no
@@ -224,7 +226,7 @@ static ssize_t chars_in_buffer(struct tty_struct *tty)
 	ssize_t n = 0;
 
 	if (!ldata->icanon)
-		n = read_cnt(ldata);
+		n = ldata->commit_head - ldata->read_tail;
 	else
 		n = ldata->canon_head - ldata->read_tail;
 	return n;
@@ -313,10 +315,6 @@ static void n_tty_check_unthrottle(struct tty_struct *tty)
  *
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
- *		modifies read_head
- *
- *	read_head is only considered 'published' if canonical mode is
- *	not active.
  */
 
 static inline void put_tty_queue(unsigned char c, struct n_tty_data *ldata)
@@ -340,6 +338,7 @@ static void reset_buffer_flags(struct n_tty_data *ldata)
 {
 	ldata->read_head = ldata->canon_head = ldata->read_tail = 0;
 	ldata->echo_head = ldata->echo_tail = ldata->echo_commit = 0;
+	ldata->commit_head = 0;
 	ldata->echo_mark = 0;
 	ldata->line_start = 0;
 
@@ -987,10 +986,6 @@ static inline void finish_erasing(struct n_tty_data *ldata)
  *
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
- *		modifies read_head
- *
- *	Modifying the read_head is not considered a publish in this context
- *	because canonical mode is active -- only canon_head publishes
  */
 
 static void eraser(unsigned char c, struct tty_struct *tty)
@@ -1139,7 +1134,6 @@ static void isig(int sig, struct tty_struct *tty)
  *
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
- *		publishes read_head via put_tty_queue()
  *
  *	Note: may get exclusive termios_rwsem if flushing input buffer
  */
@@ -1209,7 +1203,6 @@ static void n_tty_receive_overrun(struct tty_struct *tty)
  *
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
- *		publishes read_head via put_tty_queue()
  */
 static void n_tty_receive_parity_error(struct tty_struct *tty, unsigned char c)
 {
@@ -1263,7 +1256,6 @@ n_tty_receive_signal_char(struct tty_struct *tty, int signal, unsigned char c)
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
  *		publishes canon_head if canonical mode is active
- *		otherwise, publishes read_head via put_tty_queue()
  *
  *	Returns 1 if LNEXT was received, else returns 0
  */
@@ -1376,7 +1368,7 @@ n_tty_receive_char_special(struct tty_struct *tty, unsigned char c)
 handle_newline:
 			set_bit(ldata->read_head & (N_TTY_BUF_SIZE - 1), ldata->read_flags);
 			put_tty_queue(c, ldata);
-			ldata->canon_head = ldata->read_head;
+			smp_store_release(&ldata->canon_head, ldata->read_head);
 			kill_fasync(&tty->fasync, SIGIO, POLL_IN);
 			if (waitqueue_active(&tty->read_wait))
 				wake_up_interruptible_poll(&tty->read_wait, POLLIN);
@@ -1526,7 +1518,7 @@ n_tty_receive_char_lnext(struct tty_struct *tty, unsigned char c, char flag)
  *
  *	n_tty_receive_buf()/producer path:
  *		claims non-exclusive termios_rwsem
- *		publishes read_head and canon_head
+ *		publishes commit_head or canon_head
  */
 
 static void
@@ -1537,16 +1529,14 @@ n_tty_receive_buf_real_raw(struct tty_struct *tty, const unsigned char *cp,
 	size_t n, head;
 
 	head = ldata->read_head & (N_TTY_BUF_SIZE - 1);
-	n = N_TTY_BUF_SIZE - max(read_cnt(ldata), head);
-	n = min_t(size_t, count, n);
+	n = min_t(size_t, count, N_TTY_BUF_SIZE - head);
 	memcpy(read_buf_addr(ldata, head), cp, n);
 	ldata->read_head += n;
 	cp += n;
 	count -= n;
 
 	head = ldata->read_head & (N_TTY_BUF_SIZE - 1);
-	n = N_TTY_BUF_SIZE - max(read_cnt(ldata), head);
-	n = min_t(size_t, count, n);
+	n = min_t(size_t, count, N_TTY_BUF_SIZE - head);
 	memcpy(read_buf_addr(ldata, head), cp, n);
 	ldata->read_head += n;
 }
@@ -1676,8 +1666,13 @@ static void __receive_buf(struct tty_struct *tty, const unsigned char *cp,
 			tty->ops->flush_chars(tty);
 	}
 
-	if ((!ldata->icanon && (read_cnt(ldata) >= ldata->minimum_to_wake)) ||
-		L_EXTPROC(tty)) {
+	if (ldata->icanon && !L_EXTPROC(tty))
+		return;
+
+	/* publish read_head to consumer */
+	smp_store_release(&ldata->commit_head, ldata->read_head);
+
+	if ((read_cnt(ldata) >= ldata->minimum_to_wake) || L_EXTPROC(tty)) {
 		kill_fasync(&tty->fasync, SIGIO, POLL_IN);
 		if (waitqueue_active(&tty->read_wait))
 			wake_up_interruptible_poll(&tty->read_wait, POLLIN);
@@ -1694,7 +1689,22 @@ n_tty_receive_buf_common(struct tty_struct *tty, const unsigned char *cp,
 	down_read(&tty->termios_rwsem);
 
 	while (1) {
-		room = receive_room(tty);
+		/*
+		 * paired with store in *_copy_from_read_buf() -- guarantees
+		 * the consumer has loaded the data in read_buf up to the new
+		 * read_tail (so this producer will not overwrite unread data)
+		 */
+		size_t tail = smp_load_acquire(&ldata->read_tail);
+		size_t head = ldata->read_head;
+
+		if (I_PARMRK(tty))
+			room = N_TTY_BUF_SIZE - (head - tail) * 3 - 1;
+		else
+			room = N_TTY_BUF_SIZE - (head - tail) - 1;
+
+		if (room <= 0)
+			room = ldata->icanon && ldata->canon_head == tail;
+
 		n = min(count, room);
 		if (!n) {
 			if (flow && !room)
@@ -1764,6 +1774,7 @@ static void n_tty_set_termios(struct tty_struct *tty, struct ktermios *old)
 			ldata->canon_head = ldata->read_head;
 			ldata->push = 1;
 		}
+		ldata->commit_head = ldata->read_head;
 		ldata->erasing = 0;
 		ldata->lnext = 0;
 	}
@@ -1905,7 +1916,7 @@ static inline int input_available_p(struct tty_struct *tty, int poll)
 	if (ldata->icanon && !L_EXTPROC(tty))
 		return ldata->canon_head != ldata->read_tail;
 	else
-		return read_cnt(ldata) >= amt;
+		return ldata->commit_head - ldata->read_tail >= amt;
 }
 
 /**
@@ -1937,10 +1948,11 @@ static int copy_from_read_buf(struct tty_struct *tty,
 	int retval;
 	size_t n;
 	bool is_eof;
+	size_t head = smp_load_acquire(&ldata->commit_head);
 	size_t tail = ldata->read_tail & (N_TTY_BUF_SIZE - 1);
 
 	retval = 0;
-	n = min(read_cnt(ldata), N_TTY_BUF_SIZE - tail);
+	n = min(head - ldata->read_tail, N_TTY_BUF_SIZE - tail);
 	n = min(*nr, n);
 	if (n) {
 		retval = copy_to_user(*b, read_buf_addr(ldata, tail), n);
@@ -1948,9 +1960,10 @@ static int copy_from_read_buf(struct tty_struct *tty,
 		is_eof = n == 1 && read_buf(ldata, tail) == EOF_CHAR(tty);
 		tty_audit_add_data(tty, read_buf_addr(ldata, tail), n,
 				ldata->icanon);
-		ldata->read_tail += n;
+		smp_store_release(&ldata->read_tail, ldata->read_tail + n);
 		/* Turn single EOF into zero-length read */
-		if (L_EXTPROC(tty) && ldata->icanon && is_eof && !read_cnt(ldata))
+		if (L_EXTPROC(tty) && ldata->icanon && is_eof &&
+		    (head == ldata->read_tail))
 			n = 0;
 		*b += n;
 		*nr -= n;
@@ -1993,7 +2006,7 @@ static int canon_copy_from_read_buf(struct tty_struct *tty,
 	bool eof_push = 0;
 
 	/* N.B. avoid overrun if nr == 0 */
-	n = min(*nr, read_cnt(ldata));
+	n = min(*nr, smp_load_acquire(&ldata->canon_head) - ldata->read_tail);
 	if (!n)
 		return 0;
 
@@ -2043,8 +2056,7 @@ static int canon_copy_from_read_buf(struct tty_struct *tty,
 
 	if (found)
 		clear_bit(eol, ldata->read_flags);
-	smp_mb__after_atomic();
-	ldata->read_tail += c;
+	smp_store_release(&ldata->read_tail, ldata->read_tail + c);
 
 	if (found) {
 		if (!ldata->push)
-- 
2.2.1

Re: [PATCH v2] n_tty: Fix unordered accesses to lockless read buffer

[Peter Hurley]

On 01/12/2015 08:47 PM, Peter Hurley wrote:
> Add commit_head buffer index, which the producer-side publishes
> after input processing in non-canon mode. This ensures the consumer-side
> observes correctly-ordered writes in non-canonical mode (ie., the buffer
> data is written before the buffer index is advanced). Fix consumer-side
> uses of read_cnt() to use commit_head instead.
> 
> Add required memory barriers to the tail index to guarantee
> the consumer-side has completed the loads before the producer-side
> begins writing new data. Open-code the producer-side receive_room()
> into the i/o loop.

Hi Greg,

Please don't apply this. I've been testing a v3 series that I should be
able to get to you today.

Regards,
Peter Hurley

[PATCH v3 0/6] N_TTY input path fixes

[Peter Hurley]

Greg,

Here's the unordered access fix blown up to a series :(

The first patch removes receive_room() from the non-producer code
paths; this avoids the complication of read_head access from the
consumer-side. Exclusive-use paths (where the termios_rwsem is write-locked,
such as n_tty_set_termios(), n_tty_ioctl() and n_tty_flush_buffer()) can
access any of the buffer indexes without racing, since both the input
worker and reader are excluded by the write lock.

The second patch fixes a failure to make forward progress if an
unterminated line longer than 3967 chars is received in canonical mode; the
tty will mistakenly be throttled and thus potentially never receive the
line termination.

The third patch simplifies the throttle threshold calculation, _and_
removes the last-but-one receive_room() call site.

The fourth patch fixes the unordered read buffer accesses with weakly-
ordered arches.

The fifth patch fixes the space calculation issue noted by Christian;
while this is low priority, the subsequent patch requires it.

The sixth patch fixes input handling when a line termination has
not been received and the read buffer is full.

I'll send a separate email for which stables these can be directly applied;
then I'll get to work on backporting these fixes to the other longterm
stable trees.

Regards,

Peter Hurley (6):
  n_tty: Eliminate receive_room() from consumer/exclusive paths
  n_tty: Fix throttle for canon lines > 3967 chars
  n_tty: Simplify throttle threshold calculation
  n_tty: Fix unordered accesses to lockless read buffer
  n_tty: Fix PARMRK over-throttling
  n_tty: Fix read buffer overwrite when no newline

 drivers/tty/n_tty.c | 209 ++++++++++++++++++++++++++++++----------------------
 1 file changed, 119 insertions(+), 90 deletions(-)

-- 
2.2.2

[PATCH v3 1/6] n_tty: Eliminate receive_room() from consumer/exclusive paths

[Peter Hurley]

The input worker never reschedules itself; it only processes input until
either there is no more input or the read buffer is full. So the reader
is responsible for restarting the input worker only if the read buffer
was previously full (no_room == 1) _and_ space is now available to process
more input because the reader has consumed data from the read buffer.

However, computing the actual space available is not required to determine
if the reader has consumed data from the read buffer. This condition is
evaluated in 5 situations, each of which the space avail is already known:
1. n_tty_flush_buffer() - the read buffer is empty; kick the worker
2. n_tty_set_termios() - no data has been consumed; do not kick the worker
       (although it may have kicked the reader so data _will be_ consumed)
3. n_tty_check_unthrottle - avail space > 3968; kick the worker
4. n_tty_read, before leaving - only kick the worker if the reader has
       moved the tail. This prevents unnecessarily kicking the worker
       when timeout-style reading is used.
5. n_tty_read, before sleeping - although it is possible for the read
       buffer to be full and input_available_p() to be false, this can
       only happen when the input worker is racing the reader, in which
       case the reader will have been woken and won't sleep.

Rename n_tty_set_room() to n_tty_kick_worker() to reflect what the
function actually does.

Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---
 drivers/tty/n_tty.c | 23 ++++++++++++-----------
 1 file changed, 12 insertions(+), 11 deletions(-)

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index 4ddfa60..b60b043 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -187,10 +187,10 @@ static int receive_room(struct tty_struct *tty)
 }
 
 /**
- *	n_tty_set_room	-	receive space
+ *	n_tty_kick_worker - start input worker (if required)
  *	@tty: terminal
  *
- *	Re-schedules the flip buffer work if space just became available.
+ *	Re-schedules the flip buffer work if it may have stopped
  *
  *	Caller holds exclusive termios_rwsem
  *	   or
@@ -198,12 +198,12 @@ static int receive_room(struct tty_struct *tty)
  *		holds non-exclusive termios_rwsem
  */
 
-static void n_tty_set_room(struct tty_struct *tty)
+static void n_tty_kick_worker(struct tty_struct *tty)
 {
 	struct n_tty_data *ldata = tty->disc_data;
 
-	/* Did this open up the receive buffer? We may need to flip */
-	if (unlikely(ldata->no_room) && receive_room(tty)) {
+	/* Did the input worker stop? Restart it */
+	if (unlikely(ldata->no_room)) {
 		ldata->no_room = 0;
 
 		WARN_RATELIMIT(tty->port->itty == NULL,
@@ -274,7 +274,7 @@ static void n_tty_check_unthrottle(struct tty_struct *tty)
 			return;
 		if (!tty->count)
 			return;
-		n_tty_set_room(tty);
+		n_tty_kick_worker(tty);
 		n_tty_write_wakeup(tty->link);
 		if (waitqueue_active(&tty->link->write_wait))
 			wake_up_interruptible_poll(&tty->link->write_wait, POLLOUT);
@@ -296,7 +296,7 @@ static void n_tty_check_unthrottle(struct tty_struct *tty)
 			break;
 		if (!tty->count)
 			break;
-		n_tty_set_room(tty);
+		n_tty_kick_worker(tty);
 		unthrottled = tty_unthrottle_safe(tty);
 		if (!unthrottled)
 			break;
@@ -379,7 +379,7 @@ static void n_tty_flush_buffer(struct tty_struct *tty)
 {
 	down_write(&tty->termios_rwsem);
 	reset_buffer_flags(tty->disc_data);
-	n_tty_set_room(tty);
+	n_tty_kick_worker(tty);
 
 	if (tty->link)
 		n_tty_packet_mode_flush(tty);
@@ -1817,7 +1817,6 @@ static void n_tty_set_termios(struct tty_struct *tty, struct ktermios *old)
 		else
 			ldata->real_raw = 0;
 	}
-	n_tty_set_room(tty);
 	/*
 	 * Fix tty hang when I_IXON(tty) is cleared, but the tty
 	 * been stopped by STOP_CHAR(tty) before it.
@@ -2130,6 +2129,7 @@ static ssize_t n_tty_read(struct tty_struct *tty, struct file *file,
 	ssize_t retval = 0;
 	long timeout;
 	int packet;
+	size_t tail;
 
 	c = job_control(tty, file);
 	if (c < 0)
@@ -2166,6 +2166,7 @@ static ssize_t n_tty_read(struct tty_struct *tty, struct file *file,
 	}
 
 	packet = tty->packet;
+	tail = ldata->read_tail;
 
 	add_wait_queue(&tty->read_wait, &wait);
 	while (nr) {
@@ -2208,7 +2209,6 @@ static ssize_t n_tty_read(struct tty_struct *tty, struct file *file,
 				retval = -ERESTARTSYS;
 				break;
 			}
-			n_tty_set_room(tty);
 			up_read(&tty->termios_rwsem);
 
 			timeout = wait_woken(&wait, TASK_INTERRUPTIBLE,
@@ -2253,7 +2253,8 @@ static ssize_t n_tty_read(struct tty_struct *tty, struct file *file,
 		if (time)
 			timeout = time;
 	}
-	n_tty_set_room(tty);
+	if (tail != ldata->read_tail)
+		n_tty_kick_worker(tty);
 	up_read(&tty->termios_rwsem);
 
 	remove_wait_queue(&tty->read_wait, &wait);
-- 
2.2.2

[PATCH v3 2/6] n_tty: Fix throttle for canon lines > 3967 chars

[Peter Hurley]

The tty driver will be mistakenly throttled if a line termination
has not been received, and the line exceeds 3967 chars. Thus, it is
possible for the driver to stop sending when it has not yet sent
the newline. This does not apply to the pty driver.

Don't throttle until at least one line termination has been
received.

Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---
 drivers/tty/n_tty.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index b60b043..d4b14c3 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -247,6 +247,8 @@ static void n_tty_write_wakeup(struct tty_struct *tty)
 
 static void n_tty_check_throttle(struct tty_struct *tty)
 {
+	struct n_tty_data *ldata = tty->disc_data;
+
 	if (tty->driver->type == TTY_DRIVER_TYPE_PTY)
 		return;
 	/*
@@ -254,6 +256,9 @@ static void n_tty_check_throttle(struct tty_struct *tty)
 	 * mode.  We don't want to throttle the driver if we're in
 	 * canonical mode and don't have a newline yet!
 	 */
+	if (ldata->icanon && ldata->canon_head == ldata->read_tail)
+		return;
+
 	while (1) {
 		int throttled;
 		tty_set_flow_change(tty, TTY_THROTTLE_SAFE);
-- 
2.2.2

[PATCH v3 3/6] n_tty: Simplify throttle threshold calculation

[Peter Hurley]

The adjustments performed by receive_room() are to ensure a line
termination can always be written to the read buffer. However,
these adjustments are irrelevant to the throttle threshold (because
the threshold < buffer limit).

Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---
 drivers/tty/n_tty.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index d4b14c3..7efabc4 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -262,7 +262,7 @@ static void n_tty_check_throttle(struct tty_struct *tty)
 	while (1) {
 		int throttled;
 		tty_set_flow_change(tty, TTY_THROTTLE_SAFE);
-		if (receive_room(tty) >= TTY_THRESHOLD_THROTTLE)
+		if (N_TTY_BUF_SIZE - read_cnt(ldata) >= TTY_THRESHOLD_THROTTLE)
 			break;
 		throttled = tty_throttle_safe(tty);
 		if (!throttled)
-- 
2.2.2

[PATCH v3 4/6] n_tty: Fix unordered accesses to lockless read buffer

[Peter Hurley]

Add commit_head buffer index, which the producer-side publishes
after input processing in non-canon mode. This ensures the consumer-side
observes correctly-ordered writes in non-canonical mode (ie., the buffer
data is written before the buffer index is advanced). Fix consumer-side
uses of read_cnt() to use commit_head instead.

Add required memory barriers to the tail index to guarantee
the consumer-side has completed the loads before the producer-side
begins writing new data. Open-code the producer-side receive_room()
into the i/o loop.

Remove no-longer-referenced receive_room().

Based on work by Christian Riesch <christian.riesch@omicron.at>

Cc: Christian Riesch <christian.riesch@omicron.at>
Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---

Changes from v2:
*  Depends on "n_tty: Eliminate receive_room() from consumer/exclusive paths"
   and "n_tty: Simplify throttle threshold calculation". This eliminates
   receive_room() completely, which avoids the complication of accessing
   the 'opposed' buffer index from this shared code path (or unnecessarily
   duplicating it).
*  Moves the relevant comments from receive_room() to the producer i/o loop
   in n_tty_receive_buf_common()

Changes from v1:
*  Remove read_tail accesses completely from n_tty_receive_buf_real_raw().
   The computation for copy size does not require the read_cnt() since
   count is already <= available buffer space.
*  commit_head is only published in non-canonical mode. The index is
   synced if the mode is changed in n_tty_set_termios. This becomes
   relevant for a follow-on fix that must back up the read_head in
   canon mode.
*  receive_room() in the producer-side i/o loop is open-coded to
   enable smp_load_acquire() of read_tail. (see updated commit log)
*  ACCESS_ONCE()s removed according to my own review of v1. I can
   expand on the analysis of each of those if someone would like.
*  Stuck with the read_head accesses from exclusive access functions
   like n_tty_set_termios() and n_tty_ioctl() (instead of the v1 usage
   of commit_head)

 drivers/tty/n_tty.c | 101 +++++++++++++++++++++++++---------------------------
 1 file changed, 48 insertions(+), 53 deletions(-)

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index 7efabc4..f63b25b 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -90,6 +90,7 @@
 struct n_tty_data {
 	/* producer-published */
 	size_t read_head;
+	size_t commit_head;
 	size_t canon_head;
 	size_t echo_head;
 	size_t echo_commit;
@@ -161,31 +162,6 @@ static inline int tty_put_user(struct tty_struct *tty, unsigned char x,
 	return put_user(x, ptr);
 }
 
-static int receive_room(struct tty_struct *tty)
-{
-	struct n_tty_data *ldata = tty->disc_data;
-	int left;
-
-	if (I_PARMRK(tty)) {
-		/* Multiply read_cnt by 3, since each byte might take up to
-		 * three times as many spaces when PARMRK is set (depending on
-		 * its flags, e.g. parity error). */
-		left = N_TTY_BUF_SIZE - read_cnt(ldata) * 3 - 1;
-	} else
-		left = N_TTY_BUF_SIZE - read_cnt(ldata) - 1;
-
-	/*
-	 * If we are doing input canonicalization, and there are no
-	 * pending newlines, let characters through without limit, so
-	 * that erase characters will be handled.  Other excess
-	 * characters will be beeped.
-	 */
-	if (left <= 0)
-		left = ldata->icanon && ldata->canon_head == ldata->read_tail;
-
-	return left;
-}
-
 /**
  *	n_tty_kick_worker - start input worker (if required)
  *	@tty: terminal
@@ -224,7 +200,7 @@ static ssize_t chars_in_buffer(struct tty_struct *tty)
 	ssize_t n = 0;
 
 	if (!ldata->icanon)
-		n = read_cnt(ldata);
+		n = ldata->commit_head - ldata->read_tail;
 	else
 		n = ldata->canon_head - ldata->read_tail;
 	return n;
@@ -318,10 +294,6 @@ static void n_tty_check_unthrottle(struct tty_struct *tty)
  *
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
- *		modifies read_head
- *
- *	read_head is only considered 'published' if canonical mode is
- *	not active.
  */
 
 static inline void put_tty_queue(unsigned char c, struct n_tty_data *ldata)
@@ -345,6 +317,7 @@ static void reset_buffer_flags(struct n_tty_data *ldata)
 {
 	ldata->read_head = ldata->canon_head = ldata->read_tail = 0;
 	ldata->echo_head = ldata->echo_tail = ldata->echo_commit = 0;
+	ldata->commit_head = 0;
 	ldata->echo_mark = 0;
 	ldata->line_start = 0;
 
@@ -992,10 +965,6 @@ static inline void finish_erasing(struct n_tty_data *ldata)
  *
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
- *		modifies read_head
- *
- *	Modifying the read_head is not considered a publish in this context
- *	because canonical mode is active -- only canon_head publishes
  */
 
 static void eraser(unsigned char c, struct tty_struct *tty)
@@ -1144,7 +1113,6 @@ static void isig(int sig, struct tty_struct *tty)
  *
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
- *		publishes read_head via put_tty_queue()
  *
  *	Note: may get exclusive termios_rwsem if flushing input buffer
  */
@@ -1214,7 +1182,6 @@ static void n_tty_receive_overrun(struct tty_struct *tty)
  *
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
- *		publishes read_head via put_tty_queue()
  */
 static void n_tty_receive_parity_error(struct tty_struct *tty, unsigned char c)
 {
@@ -1268,7 +1235,6 @@ n_tty_receive_signal_char(struct tty_struct *tty, int signal, unsigned char c)
  *	n_tty_receive_buf()/producer path:
  *		caller holds non-exclusive termios_rwsem
  *		publishes canon_head if canonical mode is active
- *		otherwise, publishes read_head via put_tty_queue()
  *
  *	Returns 1 if LNEXT was received, else returns 0
  */
@@ -1381,7 +1347,7 @@ n_tty_receive_char_special(struct tty_struct *tty, unsigned char c)
 handle_newline:
 			set_bit(ldata->read_head & (N_TTY_BUF_SIZE - 1), ldata->read_flags);
 			put_tty_queue(c, ldata);
-			ldata->canon_head = ldata->read_head;
+			smp_store_release(&ldata->canon_head, ldata->read_head);
 			kill_fasync(&tty->fasync, SIGIO, POLL_IN);
 			if (waitqueue_active(&tty->read_wait))
 				wake_up_interruptible_poll(&tty->read_wait, POLLIN);
@@ -1531,7 +1497,7 @@ n_tty_receive_char_lnext(struct tty_struct *tty, unsigned char c, char flag)
  *
  *	n_tty_receive_buf()/producer path:
  *		claims non-exclusive termios_rwsem
- *		publishes read_head and canon_head
+ *		publishes commit_head or canon_head
  */
 
 static void
@@ -1542,16 +1508,14 @@ n_tty_receive_buf_real_raw(struct tty_struct *tty, const unsigned char *cp,
 	size_t n, head;
 
 	head = ldata->read_head & (N_TTY_BUF_SIZE - 1);
-	n = N_TTY_BUF_SIZE - max(read_cnt(ldata), head);
-	n = min_t(size_t, count, n);
+	n = min_t(size_t, count, N_TTY_BUF_SIZE - head);
 	memcpy(read_buf_addr(ldata, head), cp, n);
 	ldata->read_head += n;
 	cp += n;
 	count -= n;
 
 	head = ldata->read_head & (N_TTY_BUF_SIZE - 1);
-	n = N_TTY_BUF_SIZE - max(read_cnt(ldata), head);
-	n = min_t(size_t, count, n);
+	n = min_t(size_t, count, N_TTY_BUF_SIZE - head);
 	memcpy(read_buf_addr(ldata, head), cp, n);
 	ldata->read_head += n;
 }
@@ -1681,8 +1645,13 @@ static void __receive_buf(struct tty_struct *tty, const unsigned char *cp,
 			tty->ops->flush_chars(tty);
 	}
 
-	if ((!ldata->icanon && (read_cnt(ldata) >= ldata->minimum_to_wake)) ||
-		L_EXTPROC(tty)) {
+	if (ldata->icanon && !L_EXTPROC(tty))
+		return;
+
+	/* publish read_head to consumer */
+	smp_store_release(&ldata->commit_head, ldata->read_head);
+
+	if ((read_cnt(ldata) >= ldata->minimum_to_wake) || L_EXTPROC(tty)) {
 		kill_fasync(&tty->fasync, SIGIO, POLL_IN);
 		if (waitqueue_active(&tty->read_wait))
 			wake_up_interruptible_poll(&tty->read_wait, POLLIN);
@@ -1699,7 +1668,31 @@ n_tty_receive_buf_common(struct tty_struct *tty, const unsigned char *cp,
 	down_read(&tty->termios_rwsem);
 
 	while (1) {
-		room = receive_room(tty);
+		/*
+		 * When PARMRK is set, multiply read_cnt by 3, since each byte
+		 * might take up to three times as many spaces (depending on
+		 * its flags, e.g. parity error). [This calculation is wrong.]
+		 *
+		 * If we are doing input canonicalization, and there are no
+		 * pending newlines, let characters through without limit, so
+		 * that erase characters will be handled.  Other excess
+		 * characters will be beeped.
+		 *
+		 * paired with store in *_copy_from_read_buf() -- guarantees
+		 * the consumer has loaded the data in read_buf up to the new
+		 * read_tail (so this producer will not overwrite unread data)
+		 */
+		size_t tail = smp_load_acquire(&ldata->read_tail);
+		size_t head = ldata->read_head;
+
+		if (I_PARMRK(tty))
+			room = N_TTY_BUF_SIZE - (head - tail) * 3 - 1;
+		else
+			room = N_TTY_BUF_SIZE - (head - tail) - 1;
+
+		if (room <= 0)
+			room = ldata->icanon && ldata->canon_head == tail;
+
 		n = min(count, room);
 		if (!n) {
 			if (flow && !room)
@@ -1769,6 +1762,7 @@ static void n_tty_set_termios(struct tty_struct *tty, struct ktermios *old)
 			ldata->canon_head = ldata->read_head;
 			ldata->push = 1;
 		}
+		ldata->commit_head = ldata->read_head;
 		ldata->erasing = 0;
 		ldata->lnext = 0;
 	}
@@ -1909,7 +1903,7 @@ static inline int input_available_p(struct tty_struct *tty, int poll)
 	if (ldata->icanon && !L_EXTPROC(tty))
 		return ldata->canon_head != ldata->read_tail;
 	else
-		return read_cnt(ldata) >= amt;
+		return ldata->commit_head - ldata->read_tail >= amt;
 }
 
 /**
@@ -1941,10 +1935,11 @@ static int copy_from_read_buf(struct tty_struct *tty,
 	int retval;
 	size_t n;
 	bool is_eof;
+	size_t head = smp_load_acquire(&ldata->commit_head);
 	size_t tail = ldata->read_tail & (N_TTY_BUF_SIZE - 1);
 
 	retval = 0;
-	n = min(read_cnt(ldata), N_TTY_BUF_SIZE - tail);
+	n = min(head - ldata->read_tail, N_TTY_BUF_SIZE - tail);
 	n = min(*nr, n);
 	if (n) {
 		retval = copy_to_user(*b, read_buf_addr(ldata, tail), n);
@@ -1952,9 +1947,10 @@ static int copy_from_read_buf(struct tty_struct *tty,
 		is_eof = n == 1 && read_buf(ldata, tail) == EOF_CHAR(tty);
 		tty_audit_add_data(tty, read_buf_addr(ldata, tail), n,
 				ldata->icanon);
-		ldata->read_tail += n;
+		smp_store_release(&ldata->read_tail, ldata->read_tail + n);
 		/* Turn single EOF into zero-length read */
-		if (L_EXTPROC(tty) && ldata->icanon && is_eof && !read_cnt(ldata))
+		if (L_EXTPROC(tty) && ldata->icanon && is_eof &&
+		    (head == ldata->read_tail))
 			n = 0;
 		*b += n;
 		*nr -= n;
@@ -1997,7 +1993,7 @@ static int canon_copy_from_read_buf(struct tty_struct *tty,
 	bool eof_push = 0;
 
 	/* N.B. avoid overrun if nr == 0 */
-	n = min(*nr, read_cnt(ldata));
+	n = min(*nr, smp_load_acquire(&ldata->canon_head) - ldata->read_tail);
 	if (!n)
 		return 0;
 
@@ -2047,8 +2043,7 @@ static int canon_copy_from_read_buf(struct tty_struct *tty,
 
 	if (found)
 		clear_bit(eol, ldata->read_flags);
-	smp_mb__after_atomic();
-	ldata->read_tail += c;
+	smp_store_release(&ldata->read_tail, ldata->read_tail + c);
 
 	if (found) {
 		if (!ldata->push)
-- 
2.2.2

[PATCH v3 5/6] n_tty: Fix PARMRK over-throttling

[Peter Hurley]

If PARMRK is enabled, the available read buffer space computation is
overly-pessimistic, which results in severely throttled i/o, even
in the absence of parity errors. For example, if the 4k read buffer
contains 1k processed data, the input worker will compute available
space of 333 bytes, despite 3k being available. At 1365 chars of
processed data, 0 space available is computed.

*Divide remaining space* by 3, truncating down (if left == 2, left = 0).

Reported-by: Christian Riesch <christian.riesch@omicron.at>

Conflicts:
	drivers/tty/n_tty.c

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

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index f63b25b..7aeabb7 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -1669,9 +1669,8 @@ n_tty_receive_buf_common(struct tty_struct *tty, const unsigned char *cp,
 
 	while (1) {
 		/*
-		 * When PARMRK is set, multiply read_cnt by 3, since each byte
-		 * might take up to three times as many spaces (depending on
-		 * its flags, e.g. parity error). [This calculation is wrong.]
+		 * When PARMRK is set, each input char may take up to 3 chars
+		 * in the read buf; reduce the buffer space avail by 3x
 		 *
 		 * If we are doing input canonicalization, and there are no
 		 * pending newlines, let characters through without limit, so
@@ -1683,13 +1682,10 @@ n_tty_receive_buf_common(struct tty_struct *tty, const unsigned char *cp,
 		 * read_tail (so this producer will not overwrite unread data)
 		 */
 		size_t tail = smp_load_acquire(&ldata->read_tail);
-		size_t head = ldata->read_head;
 
+		room = N_TTY_BUF_SIZE - (ldata->read_head - tail) - 1;
 		if (I_PARMRK(tty))
-			room = N_TTY_BUF_SIZE - (head - tail) * 3 - 1;
-		else
-			room = N_TTY_BUF_SIZE - (head - tail) - 1;
-
+			room /= 3;
 		if (room <= 0)
 			room = ldata->icanon && ldata->canon_head == tail;
 
-- 
2.2.2

[PATCH v3 6/6] n_tty: Fix read buffer overwrite when no newline

[Peter Hurley]

In canon mode, the read buffer head will advance over the buffer tail
if the input > 4095 bytes without receiving a line termination char.

Discard additional input until a line termination is received.
Before evaluating for overflow, the 'room' value is normalized for
I_PARMRK and 1 byte is reserved for line termination (even in !icanon
mode, in case the mode is switched). The following table shows the
transform:

 actual buffer |  'room' value before overflow calc
  space avail  |    !I_PARMRK    |    I_PARMRK
 --------------------------------------------------
      0        |       -1        |       -1
      1        |        0        |        0
      2        |        1        |        0
      3        |        2        |        0
      4+       |        3        |        1

When !icanon or when icanon and the read buffer contains newlines,
normalized 'room' values of -1 and 0 are clamped to 0, and
'overflow' is 0, so read_head is not adjusted and the input i/o loop
exits (setting no_room if called from flush_to_ldisc()). No input
is discarded since the reader does have input available to read
which ensures forward progress.

When icanon and the read buffer does not contain newlines and the
normalized 'room' value is 0, then overflow and room are reset to 1,
so that the i/o loop will process the next input char normally
(except for parity errors which are ignored). Thus, erasures, signalling
chars, 7-bit mode, etc. will continue to be handled properly.

If the input char processed was not a line termination char, then
the canon_head index will not have advanced, so the normalized 'room'
value will now be -1 and 'overflow' will be set, which indicates the
read_head can safely be reset, effectively erasing the last char
processed.

If the input char processed was a line termination, then the
canon_head index will have advanced, so 'overflow' is cleared to 0,
the read_head is not reset, and 'room' is cleared to 0, which exits
the i/o loop (because the reader now have input available to read
which ensures forward progress).

Note that it is possible for a line termination to be received, and
for the reader to copy the line to the user buffer before the
input i/o loop is ready to process the next input char. This is
why the i/o loop recomputes the room/overflow state with every
input char while handling overflow.

Finally, if the input data was processed without receiving
a line termination (so that overflow is still set), the pty
driver must receive a write wakeup. A pty writer may be waiting
to write more data in n_tty_write() but without unthrottling
here that wakeup will not arrive, and forward progress will halt.
(Normally, the pty writer is woken when the reader reads data out
of the buffer and more space become available).

Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
---
 drivers/tty/n_tty.c | 92 ++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 62 insertions(+), 30 deletions(-)

diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index 7aeabb7..5793aa0 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -225,8 +225,6 @@ static void n_tty_check_throttle(struct tty_struct *tty)
 {
 	struct n_tty_data *ldata = tty->disc_data;
 
-	if (tty->driver->type == TTY_DRIVER_TYPE_PTY)
-		return;
 	/*
 	 * Check the remaining room for the input canonicalization
 	 * mode.  We don't want to throttle the driver if we're in
@@ -1483,23 +1481,6 @@ n_tty_receive_char_lnext(struct tty_struct *tty, unsigned char c, char flag)
 		n_tty_receive_char_flagged(tty, c, flag);
 }
 
-/**
- *	n_tty_receive_buf	-	data receive
- *	@tty: terminal device
- *	@cp: buffer
- *	@fp: flag buffer
- *	@count: characters
- *
- *	Called by the terminal driver when a block of characters has
- *	been received. This function must be called from soft contexts
- *	not from interrupt context. The driver is responsible for making
- *	calls one at a time and in order (or using flush_to_ldisc)
- *
- *	n_tty_receive_buf()/producer path:
- *		claims non-exclusive termios_rwsem
- *		publishes commit_head or canon_head
- */
-
 static void
 n_tty_receive_buf_real_raw(struct tty_struct *tty, const unsigned char *cp,
 			   char *fp, int count)
@@ -1658,12 +1639,45 @@ static void __receive_buf(struct tty_struct *tty, const unsigned char *cp,
 	}
 }
 
+/**
+ *	n_tty_receive_buf_common	-	process input
+ *	@tty: device to receive input
+ *	@cp: input chars
+ *	@fp: flags for each char (if NULL, all chars are TTY_NORMAL)
+ *	@count: number of input chars in @cp
+ *
+ *	Called by the terminal driver when a block of characters has
+ *	been received. This function must be called from soft contexts
+ *	not from interrupt context. The driver is responsible for making
+ *	calls one at a time and in order (or using flush_to_ldisc)
+ *
+ *	Returns the # of input chars from @cp which were processed.
+ *
+ *	In canonical mode, the maximum line length is 4096 chars (including
+ *	the line termination char); lines longer than 4096 chars are
+ *	truncated. After 4095 chars, input data is still processed but
+ *	not stored. Overflow processing ensures the tty can always
+ *	receive more input until at least one line can be read.
+ *
+ *	In non-canonical mode, the read buffer will only accept 4095 chars;
+ *	this provides the necessary space for a newline char if the input
+ *	mode is switched to canonical.
+ *
+ *	Note it is possible for the read buffer to _contain_ 4096 chars
+ *	in non-canonical mode: the read buffer could already contain the
+ *	maximum canon line of 4096 chars when the mode is switched to
+ *	non-canonical.
+ *
+ *	n_tty_receive_buf()/producer path:
+ *		claims non-exclusive termios_rwsem
+ *		publishes commit_head or canon_head
+ */
 static int
 n_tty_receive_buf_common(struct tty_struct *tty, const unsigned char *cp,
 			 char *fp, int count, int flow)
 {
 	struct n_tty_data *ldata = tty->disc_data;
-	int room, n, rcvd = 0;
+	int room, n, rcvd = 0, overflow;
 
 	down_read(&tty->termios_rwsem);
 
@@ -1683,19 +1697,27 @@ n_tty_receive_buf_common(struct tty_struct *tty, const unsigned char *cp,
 		 */
 		size_t tail = smp_load_acquire(&ldata->read_tail);
 
-		room = N_TTY_BUF_SIZE - (ldata->read_head - tail) - 1;
+		room = N_TTY_BUF_SIZE - (ldata->read_head - tail);
 		if (I_PARMRK(tty))
-			room /= 3;
-		if (room <= 0)
-			room = ldata->icanon && ldata->canon_head == tail;
+			room = (room + 2) / 3;
+		room--;
+		if (room <= 0) {
+			overflow = ldata->icanon && ldata->canon_head == tail;
+			if (overflow && room < 0)
+				ldata->read_head--;
+			room = overflow;
+			ldata->no_room = flow && !room;
+		} else
+			overflow = 0;
 
 		n = min(count, room);
-		if (!n) {
-			if (flow && !room)
-				ldata->no_room = 1;
+		if (!n)
 			break;
-		}
-		__receive_buf(tty, cp, fp, n);
+
+		/* ignore parity errors if handling overflow */
+		if (!overflow || !fp || *fp != TTY_PARITY)
+			__receive_buf(tty, cp, fp, n);
+
 		cp += n;
 		if (fp)
 			fp += n;
@@ -1704,7 +1726,17 @@ n_tty_receive_buf_common(struct tty_struct *tty, const unsigned char *cp,
 	}
 
 	tty->receive_room = room;
-	n_tty_check_throttle(tty);
+
+	/* Unthrottle if handling overflow on pty */
+	if (tty->driver->type == TTY_DRIVER_TYPE_PTY) {
+		if (overflow) {
+			tty_set_flow_change(tty, TTY_UNTHROTTLE_SAFE);
+			tty_unthrottle_safe(tty);
+			__tty_set_flow_change(tty, 0);
+		}
+	} else
+		n_tty_check_throttle(tty);
+
 	up_read(&tty->termios_rwsem);
 
 	return rcvd;
-- 
2.2.2