7. Device Management

  This chapter discusses the treatment of devices and I/O under DSI. We describe the stream I/O interface and its integration with DSI's process model. We then describe an implementation of input and output device drivers and their interaction with other system processes. We conclude with a discussion of the strengths and limitations of I/O in DSI.

       
7.1 The DSI I/O Model

DSI uses a character stream I/O interface; all data is presented to, or issued from, the device drivers using character streams.   An input device driver appears as a producer, reading bytes from the device and injecting a corresponding stream of characters into the heap.   An output device driver consumes a stream of characters and writes raw bytes to the device. An input-output, or bidirectional device driver both produces and consumes streams of characters. The drivers convert between raw bytes and DSI characters because the character representation is better suited for manipulation by programs dealing with lists and atoms.

  A DSI character is represented by a singleton literal (an atom consisting of a single character), as shown in figure 17.

  

Figure 17: DSI Character Representation

  The DSI hash module contains a table of statically preallocated characters. The input driver converts a byte to a character by indexing into this table with the byte. Thus, an input driver is really just generating a stream spine with the appropriate subreferences to existing identifiers.

Most DSI programs construct networks of streams that are considerably more sophisticated than this. These stream networks usually operate on higher level forms like expressions. The usual procedure is to parse the input stream into atoms and forms, process it through the network (evaluation) and convert the result back into a character stream for the output driver. Daisy provides four standard stream transducers for this purpose: a scanner, a parser, a deparser and a descanner. These filters were designed to support Daisy expressions, but can be used for general scanning of atoms, etc.

     
7.2 Device Drivers

Streams are naturally implemented in DSI using suspensions, so a system with drivers reading characters from a keyboard and echoing it to a terminal would look something like that depicted in figure 18. In the figure, DSI characters are shown as c's; character substructure has been omitted for the sake of simplicity.

  

Figure 18: Character Stream I/O

The input and output drivers are implemented in standard fashion for DSI stream producers and consumers (respectively). Suspending construction provides the synchronization and blocking mechanisms required for transparently interfacing other processes with the drivers. Processes operating on an input stream are not aware of the embedded driver suspension nor any accompanying I/O activity. Similarly, output drivers blindly consume their argument streams without regard to the source of that data; all that is required is that the argument stream conform to a list of characters.

  DSI supports the keyboard, terminal, TCP/IP stream sockets and Unix pipes as I/O devices. In addition, any file or device that can be accessed through the host's filesystem and can be read or written as a serial byte stream can be used.   Actual I/O to the various devices is handled by the host interface layer of the implementation, which provides a set of primitives for the DSI drivers. These primitives open and close devices, issue host I/O calls and buffer data, much like the C stdio library. The calls are listed in table 3.

 

Table 3: Host Interface Layer I/O Calls

CALL	DESCRIPTION
H_stdinp	Open stdin.
H_stdout	Open stdout.
H_stderr	Open stderr.
H_ttyin	Open /dev/tty for input.
H_ttyout	Open /dev/tty for output.
H_input	Open a file for input.
H_output	Open a file for output.
H_sockin	Create a socket for incoming connections.
H_sockout	Create a socket for outgoing connections.
H_accept	Make an incoming socket connection.
H_pipe	Open a Unix pipe.
H_ptypipe	Open a Unix pipe/pseudo-terminal.
H_close	Close a file or device.
H_poll	Non-blocking check for input data.
H_readreq	Issue disk read request.
H_get	Get a character.
H_put	Put a character.
H_iostat	Check device or file status.
H_prompt	Issue a short prompt to console.

 

  DSI interfaces with these host I/O functions via device descriptors. A descriptor is represented by a unary cell with a host I/O handle stored in the non-collectible data field. The tail is used to store a prompt string (a MSG-list) if the device (e.g. a terminal) supports one.

  

Figure 19: DSI Device Descriptors

The host I/O handle points to a structure containing information about the device, such as its type, buffers, optimal blocksize, and current state. The host I/O routines in table 3 create and use this information to handle differences between devices and to perform efficient transfer and buffering for each device type.

    The dvcin (input) and dvcout (output) modules define system primitives for instantiating a stream process (producer or consumer) of the appropriate device type.   The corresponding Daisy functions are listed in table 4.

 

Table 4: Daisy I/O Primitives

INPUT	DESCRIPTION
console	Returns a buffered tty input stream.
rawtty	Returns a raw tty input stream.
dski	Returns a file input stream.
exec	Returns a pipe output stream.
OUTPUT	DESCRIPTION
screen	Writes a tty output stream.
dsko	Writes a file output stream.
BIDIRECTIONAL	DESCRIPTION
socki	Reads/writes a socket stream.
socko	Reads/writes a socket stream.
pipe	Reads/writes a pipe stream.
tpipe	Reads/writes a pipe stream.

 

The following sections describe the operation of the driver processes for input and output.

   
7.3 Input Devices

All input devices are handled by a single generic driver, the input device manager. When a DSI input primitive is invoked, it calls the appropriate host I/O routine to obtain a native I/O handle (e.g. dski calls H_input). It uses this handle to build a corresponding DSI descriptor. The primitive then calls a device manager subroutine to make the descriptor known to the device manager. The device manager subroutine instantiates the input stream and returns a reference to it. The input primitive may return this stream, or filter it, depending on the device (see 7.3.4 below).

7.3.1 The Device Manager

  The device manager configuration is shown in figure 20.

  

Figure 20: Input Device Handling

  The device manager maintains a list of descriptor/stream associations on the device list (DVCLST). The stream part of the descriptor/stream pair is a reference to the tail of the input stream of characters associated with the device. When DVISCAN wakes up it scans the device list and polls each descriptor in turn:

• If there is data pending, DVISCAN will enter an input loop, reading raw bytes from the descriptor, converting them into DSI characters and appending them onto the associated input stream. When there is no more pending data to be read from a descriptor, DVISCAN updates the tail reference in the descriptor/stream pair and moves on to test the next descriptor in the device list.
• If the descriptor indicates an end-of-file or error condition DVISCAN closes the descriptor, terminates the input stream and deletes the device/stream pair from the device list.

After it has processed the entire device list DVISCAN suspends itself and awaits its next activation.

DVISCAN is an example of a multi-way shared suspension; the kernel retains a reference to it, and all low-level input streams are formed by using the same reference. DVISCAN can be activated in one of two ways: by the kernel in response to receiving a SIG_IO signal, or by a consumer process probing it as an argument stream. In either case DVISCAN acts as described above, servicing all descriptors with pending input. This arrangement provides asynchronous I/O support, since any input activity results in all descriptors being serviced.

7.3.2 I/O Signals

There are three signals reserved for device handling. SIG_IO should be implemented by a hardware interrupt or host operating system exception that is asserted when there is data ready to be read from an input device. If the device is attached to a single processor, then only that processor should receive the SIG_IO. Otherwise, the signal may be multicast, and the processor which "owns" the device manager suspension will activate it. If there are multiple I/O channels that can be serviced concurrently (perhaps on a processor network), it might be desirable to have more than one instance of DVISCAN running. This is not conceptually difficult, and would simply require that each instance of DVISCAN manage a separate device list, or that they coordinate to avoid corrupting a single shared device list. The current implementation assumes a single instantiation of DVISCAN.

Both the DVISCAN and DVCOUT will assert SIG_IOBLOCK if there is no data to be read or the output device is not ready for writing, respectively. In either case the intent is to indicate that no headway is currently possible in the current process chain. Thus SIG_IOBLOCK is intended to signal a lateral scheduling change (preemption), and is, in fact, handled like a timer signal.

        
7.3.3 Garbage Collecting Devices

Occasionally an input stream may become unreferenced while the device or file is still open. The device manager operates in conjunction with the garbage collector to close these dangling file descriptors.

DVISCAN starts by loading the header cell of DVCLST from a fixed heap location, and it finishes by clearing any references to the device list before detaching itself. The result is that unless DVISCAN is running, there are no device list references in any suspensions in the system (although there are references to the descriptors and input streams). Thus, while descriptors, input streams, and the DVISCAN suspension are marked by the garbage collector, the spine and ribs of the device list are not marked^7.1. After the normal mark phase, the garbage collector makes a special pass over the device list, checking to see if any spine/rib elements have corresponding unmarked descriptors. If so, it means that the corresponding input stream has been dereferenced. The collector closes the unmarked descriptors and splices the corresponding elements out of the device list. The device list and the hash table are the only two structures that are collected specially by the garbage collector. The implementation is different, but the effect is identical to that of the files demon in MultiScheme [Mil87].

7.3.4 Flavors of Input Devices

This section describes the differences between the various kinds of of input devices supported by DSI.

7.3.4.1 Disk Input

      DSI relies on the host filesystem to manage files. Disk input is handled on a per-file basis. dski takes a host filesystem path as argument and creates a new descriptor and DVISCAN stream for each open file. It returns a stream of characters read from the file.

      
7.3.4.2 Keyboard Input

Keyboard input is differentiated from other kinds of input in that it is implemented at a lower level. Instead of relying on the host buffering to handle multiple instances of keyboard input, DSI requests a single stream of input and multiplexes the stream itself.

At the lowest level, a DVISCAN input process presents a single raw stream of characters issuing from the keyboard.   This stream is consumed by a single splitter process (SPLIT), as shown in figure 21.

  

Figure 21: Input TTY Handling

SPLIT, like DVISCAN, is a multi-way shared suspension. The splitter splits its input stream, serving up characters on demand to whichever consumer happens to be coercing it at the moment. To add another process into the keyboard input mix it suffices to create a new trolly-car stream using the single SPLIT reference. The splitter guarantees that no two clients will receive the same character.

  The streams produced by SPLIT are also all raw character streams. This is what you get using Daisy's rawtty primitive. Raw character streams are not particularly useful as keyboard input, however. Most operating systems will reserve certain characters for special interpretation, such as interrupting processes, job control or editing and buffering input. DSI filters the raw stream using a standard keyboard filter   (KBDFLTR in figure 21). KBDFLTR provides a filtered ("cooked") character stream,   which is what you get using Daisy's console primitive. The functionality provided by KBDFLTR is fairly limited. It issues a prompt and then attempts to read up to and including a newline before detaching; when it reawakens it will prompt again and iterate. This simple interleaving of prompts and inputs is sufficient to give programs the proper interactive feel, something can be tricky in a lazy environment. KBDFLTR also performs a few other character interpretations, summarized in table 5.

 

Table 5: Standard Keyboard Filter Actions

REFERENCE	CHARACTER	ACTION
ChrNL	newline	Detach; prompt when awakened.
ChrEOT	end of file	Terminate stream.
ChrDLE	??	Forced detach.
ChrESC	escape	Escape the next character.

 

You will note that their isn't very much in the way of editing keys; DSI relies on the host operating system to handle that. It would not be difficult to do, however. Using the rawtty primitive it is possible to write more complex or special purpose filters in Daisy.

There also aren't any process termination interpretations such as the ubiquitous Control-C. Which process would this affect? DSI's process model is vastly different from conventional systems; there are many, many processes associated with any "job". The Daisy Programmer's Manual [Joh89c] has examples of how to do job control in Daisy using multisets.

   
7.4 Output Devices

  

Figure 22: An Output Process

Output devices are symmetrically constructed to input devices. An output driver is a stream consumer of characters. Each character is converted to a raw byte and written to the output channel using the host I/O primitives which handle the proper buffering for the device type (e.g. disks are written in blocks, terminals are unbuffered. etc.).

As with input devices, output devices share a common generic output driver (DVCOUT), with differences between devices contained in the host I/O handle and handled at the host interface layer. Unlike the input manager, the output driver is multiply instantiated for each output occurrence; that is, a new process is created for each consumer. Output device primitives construct the appropriate descriptor, create a suspension for the DVCOUT process, and give it a converge context. That context is then probed to bootstrap the output process.

DVCOUT is a fairly simple loop. It probes its input stream for a character and converts it to a raw byte (see figure 17). It then checks the status of its output descriptor:

• If the descriptor is ready for writing the byte is emitted using H_put and the process iterates.
• If the device is not ready for writing, DVCOUT signals the kernel with a SIG_IOBLOCK, indicating that the process is blocked and a lateral context switch is in order.
• If the device indicates an error, DVCOUT converges to an erron.

If DVCOUT reaches the end of its input stream it converges to NIL. Note that DVCOUT may block, but never detaches; that is, it is infinitely strict in its argument.

7.4.1 Flavors of Output Devices

This section describes the differences between the various kinds of of output devices supported by DSI.

7.4.1.1 Disk Output

    dsko takes a filename and a stream of characters as arguments. It creates or truncates the named file and writes the characters to it. It returns NIL after the last character is written.

7.4.1.2 Terminal Output

    Terminal output is the complement to keyboard input; screen takes an input stream and writes it to the terminal, returning NIL after the last character has been written. Terminal output is not implemented at the same level of detail as keyboard input, however. If it were, multiple output streams would be merged by a MERGE process into a single output stream before being delivered to a single (tty) instantiation of DVCOUT. As it is, DSI lets the host handle the multiplexing of outputs. An upgrade to DSI's terminal output system is planned to make it complementary to keyboard input.

7.4.2 Output Driven Computation

The effect of output devices is more than just to output characters. Because the output device driver is infinitely strict, it presents a point source of continuous demand that propagates down through its input stream and through the data space to the fringes of the computation (and ultimately, to any input drivers). It is the output devices which ultimately provide the impetus for DSI's demand-driven behavior. In between the the output drivers and the inputs, the user program controls the direction of this demand flow.

Note that with the valid implementation of SIG_IO, DSI's input drivers are event-driven rather then demand-driven. This makes sense, given the transient nature of data on the I/O bus; most devices implement some form of buffering, but will experience overruns if their interrupts are not serviced in a timely manner.

7.5 Bidirectional Devices

In addition to input-only and output-only devices, DSI also supports bidirectional devices. A bidirectional device is one that can be modeled as having both input and output channels. For example, although the display and keyboard are actually two separate physical devices, under Unix they are integrated into a single logical device (e.g. /dev/tty) from which you can read and to which you can write.

There are two kinds of interfaces that can be used for bidirectional devices in DSI. One is to split the device into two logical devices corresponding to its input and output components; this is the basic approach used for terminals. The read and write terminal I/O streams are accessed by separate input (rawtty) and output (screen) primitives, which create distinct input and output driver suspensions, as described above. Another approach to bidirectional devices is to model the device like a stream transducer; i.e. a driver process that is both a producer and consumer of streams. Figure 23 shows how this is implemented using a single suspension. The driver multiplexes input and output functions; the input stream is written to the device and the data read from the device is appended to the output stream.

DSI provides two kinds of bidirectional "devices" in the transducer-type interface: sockets and pipes.

7.5.0.1 Sockets

      DSI provides an interface to BSD-type stream sockets, a high-level TCP/IP networking standard on many operating systems, including most flavors of Unix. Sockets provide full-duplex (bidirectional) data streams between two points (sockets) over a network. Two Daisy primitives provide access to the Unix socket interface. Both socki and socko are higher-order primitives. They both return functions (closures) that map character streams to character streams; i.e. they create a producer-consumer process as described above. The input stream is the characters to write to the socket and the output stream is the characters read from the socket.

The difference between socki and socko is in how the socket connections are established; socki accepts incoming connections (server-style) and socko makes outgoing connections (client-style). The socki primitive takes a port number as argument, creates a socket, binds it to the port address on the host, and returns a function. When that function is applied to an input stream, DSI watches the port, establishing the bidirectional data flow when an incoming connection is made. This action corresponds to the Unix accept call, except that it does not block. socko takes a list argument containing two items: a host name and a port number on the network; it returns a function. When that function is applied to a stream it tries to connect to the named socket, and also establishes a a bidirectional data stream.

7.5.0.2 Unix Pipes

    Another useful bidirectional device interface provided in DSI is a Unix pipe.

  

Figure 23: A Bidirectional Unix Pipe "Device"

Like the socket primitives, the pipe primitive is higher-order. It takes a flat list of literal arguments which are intended to be the elements of the argv argument vector passed to a forked Unix process, and returns a function. When that function is applied to a stream it creates a pipe, and forks and execs a Unix process. The forked process's I/O is redirected to the pipe, so that the input stream to the pipe interface suspension (see figure 23) is fed to the process's stdin, and the process's stdout (and stderr) are returned through the interface suspension as the output stream. The connections are illustrated by figure 23.

    Two variations on pipe are provided. tpipe operates just like pipe, but opens a pseudo-terminal between the process and the I/O streams. This fools the forked process into thinking it is connected to an actual tty device, which some Unix programs require to work correctly. exec is a first-order function for creating processes that only write to stdout; its argument is in the same format as the function returned by pipe.

7.6 Limitations of DSI's I/O Model

DSI's I/O model reflects its roots in functional programming research. The stream representation provides a non-temporal, applicative interface to asynchronous device I/O that integrates well with DSI's process model. The stream interface is useful for a wide variety of devices, but some devices work better with stream model than others. In this section we will explore some of the limitations of stream I/O under DSI.

7.6.1 Interleaved Terminal I/O

This is an instance of more general problem involving non-strictness, but it becomes particularly evident with interactive stream I/O. Proper interleaving of input and output from a terminal is difficult when there is no intuitive sense of the demand patterns ordering execution of stream processes. The most typical manifestations of this problems are that input is requested before a prompt appears, prompts for various input channels are interleaved (so that one does not know which input channel he is typing to), and so on.

One solution to this problem is to insert explicit point-source coercion or laziness operations into the code to achieve the proper interleaving of prompts, input, and output [HS88, p.2]. At best this is a trial and error, ad-hoc procedure. Fortunately this problem is alleviated to a great extent by the ubiquitous use of modern windowing shells. The ability to direct I/O to individual windows usually does away with the sorts of machinations just described and the vagaries of multiplexing the console among many active I/O processes.

  The xdsi interface allows DSI/Daisy programs to manipulate multiple character-mode I/O windows under the X window system. xdsi is implemented as a separate, non-integrated server that is bundled with the DSI source distribution. It relies on DSI's support for sockets (see above) to communicate with programs running on DSI. This arrangement nicely avoids the need to link in a number of large host X libraries into the DSI host executable; the only requirement is that the host operating system have TCP/IP networking support. It also makes possible a number of flexible connection arrangements. DSI programs can connect to multiple xdsi servers (usually on different workstations); conversely, an xdsi server can be connected to multiple DSI sessions (usually on different workstations or multiprocessors). This flexibility provides different ways to experiment with applicative operating systems, distributed computing, and other applications of networked user I/O.

DSI programs establish a control stream with the xdsi server by connecting to a specified socket address. Over this stream it can send commands to create and manipulate input and output windows on the display that xdsi is controlling; the model is very similar to that used by the X window system itself. Each window is associated with a DSI character stream. Input windows are stream producers in DSI; output windows are stream consumers. The streams interface in the normal way with user programs running on DSI.

One of the problems alluded to above in the description of terminal I/O is the difficulty of determining which process is requesting input. This is handled in xdsi by a special command on the control stream which inverts the background and foreground of an input window. The command is issued automatically by the xdsi interface in DSI on behalf of the input window when demand is applied to the input stream. The effect allows the user to know which windows are requesting input. A screen snapshot of the xdsi system in action is shown in figure 24. The screen shows several input and output windows connected to a Daisy program which models a hardware blackjack machine. The black windows are quiescent; the white windows are currently expecting input.

  

Figure 24: An xdsi Session

(Click on the image to see a full screen 1280x1024 (124Kb) image)

As of this writing, xdsi only supports unidirectional text windows. An obvious extension to this approach is to allow other specialized types of windows, such as GUI widgets. The xvi system [Sin91] is a windowing interface for a lazy functional language that is also implemented using a server approach (although in a more tightly coupled way than xdsi). It allows widgets and even lower level drawing to be controlled from the language by interpreting text strings issued by the program to the standard output, and parsing them calls to the X graphics libraries. This approach requires a working knowledge of the widget and drawing interfaces in C. The eXene environment for CML [Rep91] is an example of a more general lower level use of streams to control a GUI interface. eXene models each window as a collection of streams: mouse, keyboard and control streams. Widget libraries can be created in CML using these stream interfaces.

7.6.2 Non-Character Mode Devices

Integrating non-character-oriented I/O devices is not superficially difficult--it just involves streaming data other than characters and converting it as appropriate in the driver. This would require a less generalized driver to interface these kinds of devices to the system. For example, a plotter might consume a stream of commands and integer coordinates.

7.6.3 Stateful Devices

For serial "stateless" devices, such as keyboards, mice, terminals, or network sockets, the stream interface is a reasonably accurate model of the underlying events. For "stateful" devices, such as disks, the stream interface provides only a limited subset of the device's capabilities. Some devices, such as bitmapped displays, seem very unlikely to be handled by a stream I/O interface under current technology, other than at a high level, such as the xdsi interface. Part of the problem is the large, stateful nature of a bitmapped display memory and part can be attributed to processor speed and bandwidth limitations of serializing a bitstream to the display.