Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site rlgvax.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gatech!seismo!rlgvax!dennis
From: dennis@rlgvax.UUCP (Dennis Bednar)
Newsgroups: net.dcom
Subject: XON/XOFF Deadlock
Message-ID: <848@rlgvax.UUCP>
Date: Thu, 12-Dec-85 23:21:52 EST
Article-I.D.: rlgvax.848
Posted: Thu Dec 12 23:21:52 1985
Date-Received: Mon, 16-Dec-85 04:01:07 EST
Organization: CCI Office Systems Group, Reston, VA
Lines: 120
Keywords: XON/XOFF protocol, deadlock, full duplex, tty driver, terminal

multiplexor(MUX), flow control, out of band data


Introduction - Overview

I recently came across a very interesting situation which can
cause deadlocks over an asynchronous serial computer link when
both machines use the xon/xoff protocol, and the traffic is full-duplex
(both machines can send data to each other at the same time).
The deadlock causes both machines to cease transmission - permanently.
The discussion below is dependent on how the tty driver
in the kernel interfaces to the terminal multiplexor (MUX) hardware:
the assumption being that part of the XON/XOFF processing is done
in the host, and part of the XON/XOFF processing is done in the MUX.
The problem described below occurs when the MUX processes XON/XOFF's
received from the network, ie, the host interfaces to a semi-intelligent MUX.
If the MUX is dumb, that is, the host tty driver has full control
of the MUX, then the problem described below *may* not appear.


			Figure 1 below - Overview

Application	host tty driver		 tty hardware	asynch serial line
-----------	--------------------	-------------	-----------------
Host-send >---> Send Half tty driver --> MUX Send ---> to network tty device
Host-rcv  <---  Rcv  Half tty driver <-- MUX Rcv  <--- from tty



		Figure 2 (below) - Data Received Too fast from network

Host-rcv  <--- 	Rcv Half generates XOFF <-- MUX Rcv <-- data too fast
		to send out of MUX         Passes All
		(to net) when rcv queue    Data Up to HOST
		goes above high water mark,
		and generates XON to send
		out of MUX when rcv queue
		goes below low water mark




		Figure 3 (below) - Data Sent Too fast to network

Host-send >---> Send Half tty driver --> MUX Send ---> too fast to network
					 MUX Eats <--- XOFF
					XOFF and does
					NOT pass up to
					host and now
					causes output to
					network to be
					blocked
						.... later
						  <--- XON
						 ---> resume sending


Assumptions:
	- no sophisticated Data Link Control protocol is used.
	- that only the XON/XOFF protocol be used for flow-control.
	- that both machines can send an XON/XOFF (to net), and that both
	  machines can understand an XON/XOFF if received (from net).
	- both machines may decide to send data to each other
	  at the same time (ie full duplex).
	- the model is a sending process that sends data over
	  the link to a receiving process at the other end, and
	  that this is symmetric for both machines.
	- that transmission of the XON/XOFF to the network is done
	  in the *host* receive half of the tty driver, to limit
	  the rate of data received from the network (System 3
	  IXOFF ioctl()), see figure 2.
	- that the *MUX* stops/starts sending data to the network if
	  if XON/XOFF is received from the net (S3 IXON ioctl()).
	  In this case, the MUX discards the XON/XOFF, and never
	  passes the characters up to the host receive half of the
	  tty driver, see figure 3.
	- *KEY POINT to this argument:
	  that the MUX refuses to send any data character to the network,
	  when XOFF last received from the network.  The assumption is
	  that all 256 bytes are "data" to the MUX, *including* XON and XOFF.


Scenerio of Problem:
	Both machines begin sending data to each other.  Suppose that
	the application receive process on each machine cannot process
	the data received from the other machine fast enough.
	The receive process gets behind, the rcv queue goes above the
	the high water mark, which causes the network-receive
	half of the tty driver to transmit an XOFF. Now suppose
	that both machines decided the send XOFF to each other at
	the same time.  Later, the receive process on both machines
	will consume the data buffered in the network-receive half
	of the tty driver, which causes the network-receive half
	of the tty driver to send an XON to the MUX (for transmission
	to net). What if the MUX is programmed not to send the "data"
	character XON, because its "XOFF'ed on output to the network".
	Suppose both MUX'es are implemented this way, then neither
	side can transmit an XON to the other, so neither side can
	transmit any data.


Result:
	Both senders and both receiver processes on both machines
	become deadlocked.


Solution to Problem:
	There are two different solutions.  The first is to use a dumb
	MUX which can always be controlled by the host CPU.  The second
	solution is to keep the "semi-intelligent" MUX, but the host
	should have the ability to send "out-of-band" data to the MUX
	in addition to sending normal data, which can be thought of as
	"high priority" data. The "out-of-band" data is the XON and
	XOFF characters. The MUX sends the "out-of-band" (XON/XOFF)
	data to the network, even when the MUX is blocked on sending
	to the network (ie XOFF last received from net.)
-- 
Dennis Bednar	Computer Consoles Inc.	Reston VA	703-648-3300
{decvax,ihnp4,harpo,allegra}!seismo!rlgvax!dennis
dennis@rlgvax.UUCP