n_tty.c driver patch (semantic and performance correction) (all recent versions)

n_tty.c driver patch (semantic and performance correction) (all recent versions)

[Robert White]

Greetings,

Pleased find attached my first-ever contribution to kernel code... 8-)  It is 
both a "fix" and an "enhancement" (which I know is bad) but the same lines of 
code are involved in both so what are you going to do?)

Kernel Versions: 2.2, 2.4, 2.5 (all of them since 1996 really 8-)

The n_tty line discipline module contains a "semantic error" that limits its 
speed and usefullness in many uses.  The attached patch directly addresses 
serial performance in a completely backwards-compatable way.

In particular, the current handling of VMIN hugely limits, complicates, and/or 
slows down optimal serial use.  The most obvius example is that if you call 
read(2) with a buffer size less than the current value of VMIN, the line 
discipline will insist tha the read call wait for characters that can not be 
returned to that call.  The POSIX standard is silent on the subject of 
whether this is right or wrong.  Common sense says it is wrong.

What does it mean?  If you are running a protocol with variable packet sizes 
you either have to repeatedly reset VMIN or just set it to one (1) and 
potentially bounce in and out of the kernel.  In fact, if you look at 
virtually any code in the world you will find that VMIN is almost always 1 or 
0.  In any cases where it has been set larger than 1 (I havn't found any) the 
buffering of non-fixed-size frames would have to rely on timeouts (which 
would enherantly cost time) or still end up doing in-user-space packet 
recomposition.

Esentially, as it exists today, the in-kernel buffering possibilities must be 
almost unilaterally ignored at the cost of extra context switches and such.

What this patch does to fix this "semantic error" is fairly simple, if VMIN is 
larger than the current read buffer, the blocking code acts like VMIN were 
set to the buffer size.  (The actual value of VMIN is not changed, the lesser 
of VMIN and current read size is always in effect.)

This fix handles the near-end small-read requirements.  But VMIN is an 
unsigned character so the entire standard can not ever be set to explicitly 
satisfy a read of more than 255 characters.  A given read *CAN* return more 
than 255 characters if they have already been buffered, but all the 
multiple-wakeup and user-space buffer reassembly caveats still apply.  
Consider a simple protocol (Xmodem?) that sends 1024 byte packets at 
modem-esque speeds.  Such a protocol would tend to require more than four 
reads per packet.  Yech...

The "extension" is that if VMIN is set to 255 the effective VMIN for any given 
read is the exact size of the read buffer.  That is the minimum receive size 
becomes "set but unconstrained".

The extension is "different than" setting VMIN to 0.  When VMIN == 0, VTIME is 
an absolute timeout for the entire read (the existing behavior) but when VMIN 
!= 0 VTIME is the "intercharacter timer", e.g. a timeout event that is reset 
to time=0 whenever any characters are received.  At high baud rates this is 
fine but at low baud you get back into context-switches and packet 
reassembly.  With the VMIN==255 version you get the full scaled timeout but 
the reduced context switch and packet assembly behavior.

The patch is more comment than code 8-) and I wasn't sure how to split the 
patch up into the two components (fix separate from extension) since they 
involve the same lines of code.  [e.g. the guidelines didn't say whether this 
would be separated by making the "fix-and-extension" version a diff of the 
"fix" version or the original file, so I opted for the less-messy 
just-one-patch. 8-)]

The fix is more important than the enhancement.  The total text of the fix is 
the first non-comment chunk without the "(minimum == 255)" and without "the 
other code chunk" entirely.

The second code chunk in the patch prevents a deadlock in the flow-control 
mechanisim of the UART driver.  If the read buffer size is "too big" the 
internal driver buffer could fill and cause the serial flow-control logic to 
trip, which would, of course, stop characters from arriving.  This second 
chunk sets a rational ceiling on the minimum_to_wake, which makes the 
partial-copy mechanisim transfer the driver buffer contents into the read 
buffer.  This was previously handled by the assumption that VMIN was 
(effectively) never larger than 255.  Now that it can be effectively larger 
this block sets the ceiling explicitly.

(Wow, that was a lot of text for this little thing... 8-)

Rob White
Newcastle, WA
rwhite@pobox.com

(Sorry, I don't speak manual page so I didn't patch it... 8-)

BEGIN PATCH:

--- drivers/char/n_tty.c.orig	Tue Jan 29 18:26:54 2002
+++ drivers/char/n_tty.c	Thu Jan 31 02:28:51 2002
@@ -18,11 +18,35 @@
  * This file may be redistributed under the terms of the GNU General Public
  * License.
  *
+ * 2002/01/29	Fixed & Extended VMIN handling.
+ *		Patch By:  Robert White <rwhite@pobox.com>
+ *		Problem:  Where VTIME == 0 and VMIN > nr durring read,
+ *		   read would block for characters it couldn't possibly return.
+ *		   Reading variable sized blocks required multiple syscalls
+ *		   (termio set followed by read) or reliance on timeout.
+ *		   or multiple reads of fragments. For large reads n_tty
+ *		   was not capible of returning more than 255 bytes (bad
+ *		   for performance of any serial protocols. c.f. Z-MODEM etc)
+ *		Fix: if VMIN > nr, use nr to set minimum instead. (adjust down)
+ *		Extension: if VMIN == 255, always set minimum to nr (up OR down)
+ *		(Fix and Extension apply to each read call, VMIN itself is not adjusted)
+ *		Consider: (w/8 or 1500 chars from device to be delivered respectively)
+ *		VMIN=30, VTIME=0, read(fd,buf,8);
+ *		  Old: read never returns, New: returns immed on 8th char
+ *		VMIN=30, VTIME=200, read(fd,buf,8);
+ *		  Old: return in 20 seconds, New: returns immed on 8th char
+ *		VMIN=255, VTIME=0, read(fd,buf,1500); 
+ *		  Old: 5 reads of ~255 then deadlock, New: 1 read to complete
+ *		VMIN=255, VTIME>0, read(fd,buf,1500);
+ *		  Old: 5 reads then timout for remainder, New: 1 read
+ *			or more depending timeout occurences)
+ *
  * Reduced memory usage for older ARM systems  - Russell King
  *
  * 2000/01/20   Fixed SMP locking on put_tty_queue using bits of 
  *		the patch by Andrew J. Kroll <ag784@freenet.buffalo.edu>
  *		who actually finally proved there really was a race.
+ *		
  */
 
 #include <linux/types.h>
@@ -974,6 +998,11 @@
 	if (!tty->icanon) {
 		time = (HZ / 10) * TIME_CHAR(tty);
 		minimum = MIN_CHAR(tty);
+		/* Added rwhite@pobox.com Jan 29, 2002 */
+		if ((minimum == 255) || (minimum > nr))	{
+			minimum = nr;
+		}
+		/* End Addition */
 		if (minimum) {
 			if (time)
 				tty->minimum_to_wake = 1;
@@ -1021,6 +1050,16 @@
 		if (((minimum - (b - buf)) < tty->minimum_to_wake) &&
 		    ((minimum - (b - buf)) >= 1))
 			tty->minimum_to_wake = (minimum - (b - buf));
+
+		/* Added rwhite@pobox.com Jan 29, 2002 */
+		// minimum and therefore minimum_to_wake could be much larger
+		// than the actual buffer here, so...
+		if (tty->minimum_to_wake >= TTY_FLIPBUF_SIZE)	{
+			// Flow Control would deadlock at  (N_TTY_BUF_SIZE - 
TTY_THRESHOLD_THROTTLE)
+			// using TTY_FLIPBUF_SIZE-1 is safe and likely linear/streaming.
+			tty->minimum_to_wake = TTY_FLIPBUF_SIZE - 1;
+		}
+		/* End Addition */
 		
 		if (!input_available_p(tty, 0)) {
 			if (test_bit(TTY_OTHER_CLOSED, &tty->flags)) {

Re: n_tty.c driver patch (semantic and performance correction) (all recent versions)

[Pavel Machek]

Hi!

> (Wow, that was a lot of text for this little thing... 8-)

Yep.

> --- drivers/char/n_tty.c.orig	Tue Jan 29 18:26:54 2002
> +++ drivers/char/n_tty.c	Thu Jan 31 02:28:51 2002
> @@ -18,11 +18,35 @@
>   * This file may be redistributed under the terms of the GNU General Public
>   * License.
>   *
> + * 2002/01/29	Fixed & Extended VMIN handling.
> + *		Patch By:  Robert White <rwhite@pobox.com>
> + *		Problem:  Where VTIME == 0 and VMIN > nr durring read,
> + *		   read would block for characters it couldn't possibly return.
> + *		   Reading variable sized blocks required multiple syscalls
> + *		   (termio set followed by read) or reliance on timeout.
> + *		   or multiple reads of fragments. For large reads n_tty
> + *		   was not capible of returning more than 255 bytes (bad
> + *		   for performance of any serial protocols. c.f. Z-MODEM etc)
> + *		Fix: if VMIN > nr, use nr to set minimum instead. (adjust down)
> + *		Extension: if VMIN == 255, always set minimum to nr (up OR down)
> + *		(Fix and Extension apply to each read call, VMIN itself is not adjusted)
> + *		Consider: (w/8 or 1500 chars from device to be delivered respectively)
> + *		VMIN=30, VTIME=0, read(fd,buf,8);
> + *		  Old: read never returns, New: returns immed on 8th char
> + *		VMIN=30, VTIME=200, read(fd,buf,8);
> + *		  Old: return in 20 seconds, New: returns immed on 8th char
> + *		VMIN=255, VTIME=0, read(fd,buf,1500); 
> + *		  Old: 5 reads of ~255 then deadlock, New: 1 read to complete
> + *		VMIN=255, VTIME>0, read(fd,buf,1500);
> + *		  Old: 5 reads then timout for remainder, New: 1 read
> + *			or more depending timeout occurences)
> + *
>   * Reduced memory usage for older ARM systems  - Russell King
>   *
>   * 2000/01/20   Fixed SMP locking on put_tty_queue using bits of 
>   *		the patch by Andrew J. Kroll <ag784@freenet.buffalo.edu>
>   *		who actually finally proved there really was a race.
> + *		
>   */
>  
>  #include <linux/types.h>
> @@ -974,6 +998,11 @@
>  	if (!tty->icanon) {
>  		time = (HZ / 10) * TIME_CHAR(tty);
>  		minimum = MIN_CHAR(tty);
> +		/* Added rwhite@pobox.com Jan 29, 2002 */
> +		if ((minimum == 255) || (minimum > nr))	{
> +			minimum = nr;
> +		}
> +		/* End Addition */
>  		if (minimum) {
>  			if (time)
>  				tty->minimum_to_wake = 1;

Kill comments who added it. Imagine if everyone done that.

> @@ -1021,6 +1050,16 @@
>  		if (((minimum - (b - buf)) < tty->minimum_to_wake) &&
>  		    ((minimum - (b - buf)) >= 1))
>  			tty->minimum_to_wake = (minimum - (b - buf));
> +
> +		/* Added rwhite@pobox.com Jan 29, 2002 */
> +		// minimum and therefore minimum_to_wake could be much larger
> +		// than the actual buffer here, so...
> +		if (tty->minimum_to_wake >= TTY_FLIPBUF_SIZE)	{
> +			// Flow Control would deadlock at  (N_TTY_BUF_SIZE - 
> TTY_THRESHOLD_THROTTLE)
> +			// using TTY_FLIPBUF_SIZE-1 is safe and likely linear/streaming.
> +			tty->minimum_to_wake = TTY_FLIPBUF_SIZE - 1;
> +		}
> +		/* End Addition */

No C++ comments, please.
									Pavel
-- 
(about SSSCA) "I don't say this lightly.  However, I really think that the U.S.
no longer is classifiable as a democracy, but rather as a plutocracy." --hpa

RE: n_tty.c driver patch (semantic and performance correction) (a ll recent versions)

[Ed Vance]

Hi Rob,

On Thu, June 27, 2002 at 9:37 AM, Robert White wrote:
> 
> Actually you are wrong about the "Standard".  The Linux manual 
> pages only say the read will return when so many characters 
> have been received.  Alternately, the System V Interface 
> Definition (in every version I have been able to find on the 
> net) speaks in terms of "satisfying the read" .  Both are 
> silent on the issue of what to do if the read is asking for 
> less than VMIN characters.

The Linux termios man page says rather clearly that "If only MIN 
is set, the read will not return before MIN characters have been 
received". Your change would create cases where the read _will_ 
return before MIN characters have been received. That is a conflict. 

> That is, since the VMIN/VTIME mechanism exists only with respect 
> to each individual read request and not with respect to any 
> kind of driver state, there is no inference or onus that says 
> the state applies to anything other than the receipt of 
> characters from the driver to the read itself.
> 
> That is, the context for the word "received" MUST BE "received 
> into the read buffer."  [or perhaps "received into the user 
> context"].  How so, you may ask?
> 
> If "received" is in respect to the UART (e.g. the machine/
> hardware boundary) then it would be true that if there were 100 
> characters in the driver's internal buffer, VMIN were 1, VTIME 
> were 1, and a read were issued but no more characters were 
> "received" by the UART then the read would never return.  
> That is, by the standard, "one character must be received to 
> start the timer, and one character must perceived minimum" so 
> if "received" means "into the driver" instead of "into the user 
> context" the 100 characters in the buffer, having been received 
> in the past would not relate the read (and so on ad nauseum 8-)   
> That would be ridiculous.

Termio, etc. specify the API, not the kernel's implementation of the 
API. All such driver software implements at least two levels of 
buffering to deal with the raw vs. canonical mode. The received data 
does not go directly to the user buffer. The data moves into the user 
buffer only when the read completes. Usually, the data received by 
the UART is handed up to a "line discipline" layer. In Streams 
implementations, there are (at least) three levels of buffering below 
the user's buffer: driver raw queue, line discipline private line 
assembly queue, and the stream head's queue. 

> Since in every stated and useful sense the VMIN and VTIME 
> mechanisms exist specifically and expressly for the purpose of 
> satisfying individual read requests, that is in terms of the 
> user-context/program "receiving" data from the abstract "device" 
> at the file interface, data that can not possibly relate to a 
> read because it is "out of bounds"  is immaterial to the act by 
> definition.  So waiting for the user context to receive 
> characters it has not asked for and cannot possibly receive is 
> a "bad thing".

It operates as specified and does what you tell it to through the API. 
That is neither good nor bad, per se. That's just compliance. If you 
tell it to do something that you don't want, that's not a driver bug. 

> The "waiting for data that can't be returned" and/or the 
> inconsistent application of the concept of "received" serves 
> nobody's interests.

Please make your good changes in a way that does not conflict with the 
existing API. Ioctl is your friend. 

> 
> I was going to simply dismiss that bit of hyperbole about 
> poll as a cheap bit of bad "debate technique" but I've decided 
> to respond.

Surprise. 

> Poll already and explicitly addresses the size of the read and/
> or write as one character, so tossing it in as if it were an 
> example was logically junct.  Additionally, to make the example 
> work you "threw in" with a comment about "adding an argument to 
> poll."  The reason that this was fatuous is that the parameter 
> you would "add"  to poll would be disruptive (which is why you 
> put it in 8-) but the information is already provided in the 
> read, the buffer length IS ALREADY being passed.  The analogy 
> and the allegation of difficulty or disruption is inapplicable.

That's not how poll and select are used. For the read case, Poll and 
Select are active when waiting for the availability of data. When data 
becomes available, they return and you post a read to scoop up the new 
data. There is no pending read during poll and select to supply a read 
buffer length to the driver.

I have no problem with innovation. Just don't pollute the existing API. 

Regards,
Ed

----------------------------------------------------------------
Ed Vance              edv@macrolink.com
Macrolink, Inc.       1500 N. Kellogg Dr  Anaheim, CA  92807
----------------------------------------------------------------

Re: n_tty.c driver patch (semantic and performance correction) (all recent versions)

[Robert White]

My final comment on the mater (I am known around the office for my long 
emails... sorry 8-):

It is clear to me that you didn't really read what I wrote.

Consider:

I make the assertion "The linux manual pages only say the read will return 
when so many characters have been received" and then you CORRECT me by saying 
"The Linux termios man page says rather clearly that 'If only MIN is set, the 
read will not return before MIN characters have been
received'"

Ok, so the "only" didn't belong in my sentence but we were saying the same 
thing.  That is at least a little indicitive of the respondent not really 
reading the original.  But it continues.

I make an observation about how the (three messages back now) sender made an 
allusion to this correction being like "adding a buffer length parameter to 
poll"  When I point out that that allusion isn't applicable because the poll 
semantics really say "can read/write at least one character" (and therefore 
there is already a "buffer" length implicit in the spec, and further, "adding 
a buffer length to the poll would disrupt things in a way that USING the 
length already available in the read would not and blah blah blah).

Well, your response to my comment is that "that isn't how poll works" and then 
lecture me on how it does work, which was my essential lecture to the prior 
poster.

Ok so you are not reading what I have written on this matter with any 
attentiveness.  Let me put it in VERY SIMPLE WORDS.

-- Making a read wait for characters it can't accept is unilaterally stupid, 
at best it creates a relyance on "hidden magic state" that makes for 
unstable.

-- Living with the 1980 idea of the maximum reasonable frame size for 
any/every serial protocol is stupid.

-- Putting in an alternate ioctl (instead of putting in a two-statemet fix) 
that would largely duplicate the old behavior while releiving the stupid 
limits is (wait for it...) stupid, it rases code size and the level of 
complexity disproportionately and will tend to remain unused by the very 
people it would most benefit.

-- Decrying a fix you havn't tried because it "violates" a (porely written and 
demonstrably flawed) standard in a way that doesn't break a single existing 
program is not exactly "foreward thinking."

Or perhaps as a decomposition:

1) The current behavior is *STUPID* when MIN > read_buf_length.  I defy you to 
show me one program that deliberately uses this technique on any *NIX 
platform.

1a) NOTE: I didn't say I defy you to write one nor did I defy you to give the 
"pre-cache a few frames" theoretical example.  (that example still decomposes 
into inefficency, as the cost of prefetching frames into the buffer but then 
reading them via seprate calls is more costly over the domain of time than 
waitig for the frames individually "if necessary")

1b) I further defy you, should you find such a program, to show this patch 
adversely effecting it in any way.

2) People have been whining about the serial performance of linux for years.  
The fact remains that the repeated switches in and out of the kernel to 
satisfy fragmentary reads is almost certianly to blame.

2a) If the program knows the frame sizes of expected reads, and those frame 
sizes varry, the problem is compounded heniously (more than doubled) by 
actively manipulating VMIN. (repeadtely calling the ioclt to change this 
value)

2b) Virtually every program written today that does any sort of serial frame 
processing not only has a tight loop around the read() call to do frame 
assembly, it invariably ends up actually iterating into that loop for every 
read.  Each iteration is two context switches and some work.

2c) The current behavior MANDATES sucky performance in large-frame protocols.

2c1) Have you ever profiled X, Y, or Z modem performance?

2d) Have you ever dealt with vairable framed protocols that interract with 
specialty devices? (The "T equals 0" protocol for talking to smart-card 
readers is a perfect example of an application that improves by an order of 
magnitude with this patch.  Set VMIN to 255 with the patch on and your reads 
will always return the proper frame size which varry from 2 to 258;  But you 
can't use VMIN = VTIME = 0 because you need the timeout, and so on...)

3) The values of VMIN greater than 1 are almost unilaterally unheard of "in 
the wild" because the mechanisim sucks.  In the few cases where you find such 
a program this patch will, at the least, have a zero-sum effect; at the most 
it will speed the program up.

3a) For various reasons, interractive programs will continue to generally be 
written as VMIN = 1, VTIME = 1 reguardless of this patch. (somewhat by 
definition, this patch doesn't apply to interractive programs.)

4) The current VMIN behavior was thought up back when 1200 baud was rather a 
lot and CPUs weren't that fast.  As the CPU speed rises with respect to 
serial device speed the cost in context switches will approach 2 switches per 
character received.

5) "ioctl is your friend" isn't true here.

5a) adding another whole IOCTL et al would be needlessly adding to a module 
that is already quite large.  (compared to this tiny adjustment)

Ok, well, now I am just ranting.

Seriously, try this thing and look for one single bad case asside from the 
obvious "purest" objection.  Describing this patch as "pollution" is hardly 
applicable.

Rob.


On Friday 28 June 2002 11:12, Ed Vance wrote:
> Hi Rob,
>
> On Thu, June 27, 2002 at 9:37 AM, Robert White wrote:
> > Actually you are wrong about the "Standard".  The Linux manual
> > pages only say the read will return when so many characters
> > have been received.  Alternately, the System V Interface
> > Definition (in every version I have been able to find on the
> > net) speaks in terms of "satisfying the read" .  Both are
> > silent on the issue of what to do if the read is asking for
> > less than VMIN characters.
>
> The Linux termios man page says rather clearly that "If only MIN
> is set, the read will not return before MIN characters have been
> received". Your change would create cases where the read _will_
> return before MIN characters have been received. That is a conflict.


>
> > That is, since the VMIN/VTIME mechanism exists only with respect
> > to each individual read request and not with respect to any
> > kind of driver state, there is no inference or onus that says
> > the state applies to anything other than the receipt of
> > characters from the driver to the read itself.
> >
> > That is, the context for the word "received" MUST BE "received
> > into the read buffer."  [or perhaps "received into the user
> > context"].  How so, you may ask?
> >
> > If "received" is in respect to the UART (e.g. the machine/
> > hardware boundary) then it would be true that if there were 100
> > characters in the driver's internal buffer, VMIN were 1, VTIME
> > were 1, and a read were issued but no more characters were
> > "received" by the UART then the read would never return.
> > That is, by the standard, "one character must be received to
> > start the timer, and one character must perceived minimum" so
> > if "received" means "into the driver" instead of "into the user
> > context" the 100 characters in the buffer, having been received
> > in the past would not relate the read (and so on ad nauseum 8-)
> > That would be ridiculous.
>
> Termio, etc. specify the API, not the kernel's implementation of the
> API. All such driver software implements at least two levels of
> buffering to deal with the raw vs. canonical mode. The received data
> does not go directly to the user buffer. The data moves into the user
> buffer only when the read completes. Usually, the data received by
> the UART is handed up to a "line discipline" layer. In Streams
> implementations, there are (at least) three levels of buffering below
> the user's buffer: driver raw queue, line discipline private line
> assembly queue, and the stream head's queue.
>
> > Since in every stated and useful sense the VMIN and VTIME
> > mechanisms exist specifically and expressly for the purpose of
> > satisfying individual read requests, that is in terms of the
> > user-context/program "receiving" data from the abstract "device"
> > at the file interface, data that can not possibly relate to a
> > read because it is "out of bounds"  is immaterial to the act by
> > definition.  So waiting for the user context to receive
> > characters it has not asked for and cannot possibly receive is
> > a "bad thing".
>
> It operates as specified and does what you tell it to through the API.
> That is neither good nor bad, per se. That's just compliance. If you
> tell it to do something that you don't want, that's not a driver bug.
>
> > The "waiting for data that can't be returned" and/or the
> > inconsistent application of the concept of "received" serves
> > nobody's interests.
>
> Please make your good changes in a way that does not conflict with the
> existing API. Ioctl is your friend.
>
> > I was going to simply dismiss that bit of hyperbole about
> > poll as a cheap bit of bad "debate technique" but I've decided
> > to respond.
>
> Surprise.
>
> > Poll already and explicitly addresses the size of the read and/
> > or write as one character, so tossing it in as if it were an
> > example was logically junct.  Additionally, to make the example
> > work you "threw in" with a comment about "adding an argument to
> > poll."  The reason that this was fatuous is that the parameter
> > you would "add"  to poll would be disruptive (which is why you
> > put it in 8-) but the information is already provided in the
> > read, the buffer length IS ALREADY being passed.  The analogy
> > and the allegation of difficulty or disruption is inapplicable.
>
> That's not how poll and select are used. For the read case, Poll and
> Select are active when waiting for the availability of data. When data
> becomes available, they return and you post a read to scoop up the new
> data. There is no pending read during poll and select to supply a read
> buffer length to the driver.
>
> I have no problem with innovation. Just don't pollute the existing API.
>
> Regards,
> Ed
>
> ----------------------------------------------------------------
> Ed Vance              edv@macrolink.com
> Macrolink, Inc.       1500 N. Kellogg Dr  Anaheim, CA  92807
> ----------------------------------------------------------------