Tom Nelson is an independent author, consultant, and part-time artist. You can reach him at 5004 W. Mt. Hope Rd., Lansing, MI 48917.
A state machine is a useful logical construct for writing device control code. By mirroring the device's actual operation, the state machine makes the code easier to comprehend and therefore modify. Since a state machine usually relies heavily on initialized data in tables, the amount of logical branching in the associated code is minimized, thus helping the programmer avoid "spaghetti" code. When properly employed, a state machine adds a layer of abstraction between the user and the controlled device. It also isolates device-dependent code within a limited number of functions.
From the point of view of an operating system, a device driver must present a consistent interface to application programs that access devices you may upgrade at any time or even to devices not yet on the market. The standard, installable device driver does all this and more. It functions as an extensible, user-modifiable part of an operating system.
This article attempts to combine what is necessary (the device driver) and what is desirable from a coding standpoint (the state machine). The result is a method of coding DOS device drivers (either PC-DOS or MS-DOS) that provide a programmatic interface to a finite-state machine. The article presents a working device driver that controls an idealized tape backup unit. I left out the specifics of controlling an actual device (such as port assignments and bit settings) to focus on the connections you must make between an actual device and your application program.
Driver Design Considerations
Designing a DOS device driver is a relatively simple task, since any driver must follow a standardized design. Getting one to actually run is another matter. Many consider device drivers a specialized systems task, one to be tackled only by the programming elite. However, the art need not be mysterious, especially when you code mostly in C. I organized Listing 1 and Listing 2, which form the kernel of a DOS device driver, as a template from which you can build any device driver. The template lets you concentrate on the actual device controller code. If you use the Borland compiler/assembler combination, you don't even have to know assembly language, although some knowledge of it will help you follow the ensuing discussion. If you use another compiler and assembler, you will need to modify the code to some extent.I'll touch on a few basics of device drivers, but will concern myself mainly with some important design considerations in coding a driver in C, as well as some usage caveats. Many journal articles and book chapters deal with device drivers. I refer the reader to the References section.
The Template
Listing 1, start.asm, presents the assembly language start-up code. At this level, you must use assembly language in raw form (even inline assembly won't do) because C can't provide the necessary control. All drivers consist of one segment up to 64Kb in length, forcing all code and data into a single segment. Some compilers can produce a tiny model .COM file that satisfies these requirements. However, a device driver is a binary image file with an origin of (i.e., no Program Segment Prefix block), the first bytes of which are not executable. I believe few compilers could deal with such a situation.Listing 1 begins by defining segments common to both the Borland and Microsoft compilers. If your compiler uses different segment names, you must change them. The segments must also be defined in the proper order. You must place start.obj first in the link order so that segments declared in other modules will be ordered the way you specify here (see the MAKE file in Listing 7). A compiler will usually define DGROUP (in the small model default) as a group of all data segments, keeping the code segment separate. Here I define DGROUP by combining both code and data segments, the same as for a tiny model .COM program.
I also defined another segment called ENDSEG, which is also part of DGROUP and will be linked in behind all other segments. The offset to ENDSEG allows DOS to calculate the driver's size (the break address) when DOS loads another driver behind yours.
As mentioned earlier, all drivers have an origin of 0, specified by the org 0 statement. You must place the driver's header block immediately after, at offset in . The four-byte pointer field in the header usually contains -1L (0xffffffff) unless your file contains code for more than one driver, in which case it points to the next driver's header block. Whatever the case, the pointer in the last driver's header block must contain -1L. DOS fills it with a pointer to the next driver's header in the chain at driver load time.
DOS always communicates with its device drivers using a curious two-step call. Most authors assume this was intended as a bridge to the future when DOS would support full multitasking. In view of the present status of DOS, multitasking is at best a remote possibility. The first part of this two-step call, the _dev_strategy() routine, merely saves a pointer to the caller's request header block. To maintain backward compatibility, all DOS drivers must include this routine, which represents a bit of additional overhead.
The real work of the driver is performed by the second of the two procedures called by DOS, the interrupt routine. Although not a true interrupt handler, it shares many characteristics with them. The main difference is that it terminates with a far ret rather than an iret. Like an interrupt handler, however, the routine saves the CPU state and performs other housekeeping chores. If you're going to support compiled C code, the startup procedures must occur here also. Your startup code must duplicate as closely as possible the environment created by the compiler's normal startup code. The difference is that startup occurs on every call to the driver, not just once when DOS executes an application.
After saving the CPU state and caller's stack context, the interrupt routine reclaims its own data segment, contained in the CS register. Since code and data are contained in one segment, the routine loads the DS register with the same value. Loading ES is probably optional, since most DOS compilers seem to make no assumptions regarding ES.
The interrupt routine sets up its own internal stack by loading the SS:SP register pair with the appropriate values. One difference here is that the driver's stack does not have its own segment, as is usually the case. The linker expects a separate stack segment, however, and will complain about it. This is one warning you can ignore. Although creating a separate stack for the driver is not strictly necessary, supporting a stack-intensive language like C makes separate stacks highly desirable. (I have seen attempts to program device drivers in C where all variables were declared global to avoid blowing the short stack provided by DOS, reportedly as short as 40-50 bytes.) Providing your device driver with its own stack is simple, and the benefits easily outweigh the small overhead in space. If you're really worried about memory usage, you should code the whole device driver in assembly language.
Having set up the appropriate machine environment, the interrupt routine then branches into C code. It pushes a far pointer to the caller's request header (saved earlier by the strategy routine) and calls exec_command() in Listing 2. exec_command() serves as a central dispatch point where the call branches to the appropriate function, or command code routine. exec_command() uses the jump table (*Dispatch[])(), an array of pointers to the command code routines. Using a jump table seems more elegant and less code intensive than the more cumbersome switch statement.
exec_command() also makes the caller's request header, defined in Listing 3, available globally, assigning it to the pointer Rh. exec_command() branches to the correct command code routine based on the command code Rh->cmd passed in the request header. The function uses the command code as an index into the Dispatch jump table.
exec_command() expects all command code routines to return zero if they execute normally. If errors arise while a command code routine executes, the routine returns IS_ERROR plus the appropriate error code, defined in Listing 3. On return from the command code routine, exec_command() assigns the routine's return code to the request header. exec_command() also sets the done bit in the same status field in the header. This bit seems something of an anachronism, but you should nevertheless set it before returning from the interrupt routine. The remainder of the interrupt routine restores the caller's CPU and stack context.
After loading your driver, DOS immediately calls the driver initialization routine, command code 0 (see init() in Listing 2) . You must perform any driver setup procedures inside this routine. Note that you are restricted to DOS functions 0x01-0x0C and 0x30. Other than these functions, you should avoid making DOS calls anywhere in your driver code. In general, since device drivers serve as a bridge between applications and the BIOS, you should restrict your driver code to BIOS-level calls (or port in/out code if needed) and avoid DOS entirely. More to the point, any call your driver makes to DOS commits the sin of DOS re-entrancy, since DOS called your driver in the first place.
To inform DOS where to locate the next driver in the chain, the initialization routine must return a break address in the request header that specifies the end of the driver image in memory. Here I simply label the ENDSEG segment (discussed earlier), a segment guaranteed to fall at the end of the driver image. init() passes the far address of the labeled segment to DOS as the break address. This quick and dirty method, however, means that init() remains in memory, where it becomes dead code once DOS has initialized your driver. To save memory, most drivers (those written in assembly language, that is) locate the break address above the init() code and any data that init() will use only once. DOS will then load the next driver over the unneeded parts.
Although more difficult, this trick can be simulated in C. Since the code segment is located first, you can place all code and data in _TEXT, put init() in a separate module, and place init.obj last in the link order. You could then pass the (void far *) address of the start of init()'s code to DOS as the break address. The main obstacle is that most compilers will automatically place all data in the _DATA segment. In order to get your data into _TEXT, you must define all global data inside an assembly language module and make extern references to them in your C modules. Although this scheme works, it complicates making changes later. Unless you have particularly lengthy driver initialization code, attempting to drop init() is probably more trouble than it's worth. To repeat, you're programming a driver in C for C's relative ease of use, not primarily to save memory.
Let The Programmer Beware
When choosing a name for your device, which goes in the last field of the header block, choose a name you won't use for a file. When DOS opens a file, it first checks the driver chain for a device driver with the same name. At this level, DOS treats devices and files in the same manner. If your file and a device name conflict, DOS will open the device instead of your disk file and you will get some unexpected results. To illustrate, create a file called lpt1 with your text editor. Try writing some text to it using the DOS TYPE or COPY commands. The data will go to the line printer instead of the disk file. You won't be able to delete the file from the DOS command line either.It's difficult to incorporate many of the standard C library functions in device driver code. You must be absolutely sure you know what they do, since some depend on initialized data in other modules or may take actions that in some way compromise your driver code. Neither should you use standard library functions that call malloc(), because the driver has no heap. You should write your own versions of most standard library functions, unless you use only simple, compact ones like strcpy().
Most compilers put uninitialized global data in a special segment that the startup code initializes to zeros when a program executes. Many programmers write C code that relies on this behavior, but it's an assumption you can't make in a device driver written in C. Make sure all data is initialized in some way before you use it, the same as you would do when using automatic (stack-based) variables. Also, make sure you instruct the compiler to enforce byte-packing of structures. Borland enforces byte-packing by default, but I believe the Microsoft compiler uses word-packing unless instructed not to.
Stack probing is a useful adjunct to program debugging, but it is difficult to implement a method in a driver that works with a variety of compilers. Though I have ignored stack probing in my driver code listings, you may find a way to implement it. If your compiler inserts stack probes by default, make sure you turn them off.
State Machines
State machines are useful in the control of any rule-based system, and their application to device control is a prime example. Briefly, you can apply state machines to any system you can define in terms of a finite number of states (or "islands") with a definite set of rules for traveling or navigating between them. The state machine uses initialized data in tables (a state table) to organize these states and rules into a structure that reflects the actual operation of the system.The state machine knows only the current state of the system. Given a command or event, the state machine refers to the state table to determine whether that event is valid for that state. The event determines the state to which the system will travel next. The state table also contains a set of procedures (functions) that tell the system how to effect the transition to the next state. When the machine reaches the next state, it waits until it receives another event or command, then repeats the cycle.
The State Table In C
To illustrate the basic concepts of device control using a state machine, I developed a simple example that controls a hypothetical tape backup unit. To build the state table, start with a list of the available device controller commands, as in the simplified list in Figure 1. These commands form the basis of a list of valid events, or user commands (see Listing 4, tape.h). You may also need to define other user commands, formed from combinations of the basic device commands.Next, define the various states in which your device will exist at any one time. For my tape backup unit, I defined states such as READY, PLAY, and RECORD (see Listing 4) . Then, given a set of well-defined states, decide which events will be valid for each state. These valid events determine the subset of states to which you can move, given your current position. For instance, if the tape unit is currently in a READY state, meaning you just inserted a cassette, you can move directly to any other state. If you're currently in the REWIND state, however, you can only stop rewinding and return to a READY state.
When you have defined all your states and the valid connections between them, you should end up with something like the table in Table 1, the State Transition Table. Along the way you may want to draw some simple diagrams. Such diagrams quickly become complex when the number of valid connections between states (represented by lines with arrowheads) averages more than two or three. You may also want to include a list of the functions needed to effect the transition from one state to the next, as I've done in Table 1.
You can translate the State Transition Table almost directly into a single array of structures. Although easy to understand, such an array will mean some degree of data repetition. I have instead used a series of cascading or multi-level tables connected by pointers, resulting in an efficient use of memory as well as reduced coding effort. Each valid state in the system uses an array of S_TABs, the basic data element, to create an event table (Listing 4) . The last member of an event table must be the macro END, which indicates the end of the table. An event table defines the valid events for each state, the next state to move to, as well as a pointer to the list of functions to effect the transition. All the event tables are connected at the top by an array of pointers (the state table). Note that the current state of the system serves as an index into this array. The order of states in the array should correspond to the order in which you initially defined the states, as in Listing 4.
Listing 5 contains the state table. One of the most difficult tasks is finding descriptive names for all the tables, especially the lists of pointers to functions. At first this may seem overly complex, but working with initialized data in tables significantly reduces your coding effort. Without them, your code would be littered with logical branching statements.
The IOCTL Interface
DOS device drivers make available at least two command code routines to control the driver itself. Applications use these IOCTL functions to pass control information directly to the driver to control the driver's other I/O functions. An IOCTL call does not necessarily result in any input/output interaction with the physical device. The control information's format is unspecified and is known only to the driver and the application program. DOS takes no part except to provide a standard interface for using the IOCTL functions. An application wishing to pass control data to a driver uses DOS function 44h, sub-functions 2 and 3, which read and write I/O control data, respectively.DOS passes requests for functions 44h, subfunctions 2 and 3 directly to the device driver once you have obtained a device handle using the DOS open file/device function, 3Dh. Calls to the DOS IOCTL functions end up in command code routines 3 and 12 inside the device driver, ioctl_read() and ioctl_write(), respectively ( Listing 2) . A developer can use these functions for any purpose since nothing is specified other than the calling protocol.
As you can see in Listing 5, I have used the DOS IOCTL interface as a direct channel to control the hypothetical tape drive. The driver uses only command routines 0, 3, and 12. Most of the unused routines deal with more "normal" device I/O, such as servicing DOS read/write requests. A real tape unit must protect itself from such actions, which could easily corrupt data already stored on the tape. Without this protection, anyone could write to the tape unit using the DOS TYPE command with command-line redirection. However, since command routine 8 (device_write() in Listing 2) returns 0 on every call, DOS thinks it's writing to a real device, even though nothing is actually done.
Note also that command routines 3 and 12 both call tape_io() in Listing 5. In the interest of uniformity, I combined these two functions, since the only real difference between them is semantic. You can therefore use either subfunction 2 or 3 of DOS 44h to make IOCTL calls to the tape unit.
Putting It All Together
Function tape_io() serves as the entry point into the state machine driver. tape_io() receives a far pointer to the command IOCTL string. The pointer is passed in the request header's transfer buffer (Listing 3) . Since DOS does not specify the format of the command information, I defined it as a structure of type CMDARG (Listing 4) . This structure serves as the state machine's primitive memory. It contains the current state of the system, the command for the tape unit to execute, and the return status of the command and/or the tape unit hardware.tape_io() first points to the correct event table, using the CMDARG argument as an index into the *s_table[] array. tape_io() then enters a loop, attempting to match a valid event for the current state with the command code passed in CMDARG. If the function can find no match, it returns immediately with an error code. Otherwise,tape_io() updates CMDARG's current state with the next valid state from the event table, then immediately executes the functions associated with the state transition. The array of function pointers doesn't arbitrarily limit the number of functions needed to effect the transition, nor does it require null padding to fill unused spaces in the array.
Commands sent to the state machine driver, tape_io(), originate from a separate controller program that issues DOS IOCTL calls. The code in ctl.c (Listing 6) acts as the tape unit's user interface, something the device driver controller code need not be concerned with.
To use the DOS IOCTL functions, you must first obtain a device handle using open () (Listing 6) . If open () reports an error, the device driver wasn't installed. DOS next determines if the device driver is functioning correctly, using function _dos_dev_info(). Two possibilities exist here, one that the device name is actually a disk file, or that the "IOCTL" bit (0x4000) in the driver's header block was not set. In the latter case, DOS will not complete an IOCTL function call because it assumes the device driver doesn't have an IOCTL interface. The program uses functions _dos_ioctl_read() and _dos_ioctl_write() to actually communicate with the tape unit. As outlined earlier, using either function accomplishes the same result, since both end up in the state machine driver function, tape_io().
Alternatives To IOCTL
Several alternatives to using the DOS IOCTL functions exist. Since DOS serves only as an intermediary, you could dispense with the overhead of a DOS call entirely and set up the driver as a combination standard device driver and TSR, like the Expanded Memory Manager. When DOS initializes your driver (command code 0), you would set up a software interrupt to point to the device controller code. Application programs would access the driver through the interrupt, using much the same command interface as described earlier. You're then free to make DOS calls from inside the controller code, since DOS is no longer involved up front.Continuing along these lines, you could do away with the device driver altogether and put the entire controller code inside a TSR. Since the tape unit driver doesn't have to service normal I/O requests via DOS, as device drivers usually do, you're free to do this.
However, using a TSR involves a varying amount of risk since DOS never fully supported them. Using a state machine in a device driver, on the other hand, gives the device driver full support of DOS. By using standard DOS function calls, you also avoid potential conflicts over the use of software interrupts.
Rolling Your Own Driver
I have presented the driver code in Listing 1 and Listing 2 as a sort of template, which you can use to get a head start past the coding basics. The template code allows you to concentrate on writing the actual device controller code in the language you probably know best. However, even with solid support behind you, you can still get stuck when testing and debugging your driver.Make sure you keep all device controller code in a separate module, as I did in Listing 5, tape.c. You can easily convert the module into a transient .EXE test bed, using compile-time #defines. Leave the test bed code in place, inactivated, when you produce the finished driver. When you make changes and retest, simply unpack the test bed code.
Testing your code as a normal .EXE program means you can easily use a software debugger. Your test code should include a means to load a request header with appropriate data, exactly as DOS would, and make calls to the exec_command() routine. You can then examine the data and status codes returned in the request header when the call completes. Making actual calls to the strategy and interrupt routines (Listing 1) , as DOS does, is probably unnecessary since this code is fully debugged.
A driver still needs to be tested when linked into the DOS driver chain. To prepare for this, create a bootable floppy complete with a dummy config.sys that includes a command to load your test driver from the hard disk. Also include a dummy autoexec.bat that simply calls your normal autoexec.bat file on the hard disk.
You'll probably find a software-only debugger difficult to use when testing a driver in place, although I have never tried it. You can set breakpoints within the body of the driver much as you normally would. However, most debuggers make DOS calls too. When they do so, they re-enter DOS, corrupting the DOS stack and leading directly to a system crash. Instead of using a debugger, you should rely as much as possible on testing the code thoroughly as an .EXE transient, as outlined above. To test the driver in place, you may find a "non-intrusive monitor" to be of some help (see reference [5]). You can then monitor the values of selected variables inside the driver during execution of a normal test program running in the foreground.
Some Final Thoughts
If you've tinkered with device drivers before and gotten stuck, this article may give you new impetus to try again. Even if you know your way around DOS drivers, it always helps to have a fresh slant on them, if only to affirm that your own way of doing it is better.This article has also shown that a state machine approach to writing device control code can provide considerable benefits. Its table-driven strategy forms a natural, built-in Application Program Interface (API) for device control from an application program. Using the API, anyone can build a desired user interface to the tape unit. You're also able to modify the user interface at any time without touching the device driver.
This arrangement is very flexible, since you can locate the user interface code in any situation. You could place such code in a normal .EXE application that includes tape backups as an option. Another possibility would be a TSR that uses the tape driver to make background saves of specified files when the TSR detects that the files have been modified.
References
Duncan, Ray. Advanced MS-DOS Programming, 2nd Ed.. Microsoft Press, Redmond, WA.Fischer, Paul. "State Machines in C," The C Users Journal, December 1990, pp. 119-122.
Johnson, Marcus. "Writing MS-DOS Device Drivers," The C Users Journal, December 1990, pp. 41-57.
Lai, Robert. S. and The Waite Group. Writing MS-DOS Device Drivers. Addison-Wesley.
Naleszkiewicz, John R. "A Non-Intrusive TSR Monitor," TECH Specialist, June 1991, pp. 32-40.