\documentstyle[doublespace]{article}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.25in}
\addtolength{\textwidth}{1.0in}
%\addtolength{\textheight}{1.0in}

\author{David Golombek\\Working with Professor Frans Kaashoek}
\title{AUP Final Report:\\
Investigation and Extension of the Exokernel Driver Model}
\date{\today}
\begin{document}
\maketitle
\newpage

\section{Introduction}

The Exokernel Project \cite{exokernel} at MIT is in the process of
releasing a full distribution of its operating system (OS) for PCs,
called ExoPC.  While much of the functionality of the operating system
is complete, until now the release has lacked device drivers for much
of the hardware found in normal PCs.  One of the key components of any
PC is its hard drive, and for the vast majority of all PCs sold today,
that is an ATA IDE/EIDE drive.  Until now, ExoPC has only supported
SCSI hard drives, which are much typically much higher performing, but
also much more expensive, and thus usually only sold with
workstations.  Adding IDE drive support will greatly expand the range
of computers that ExoPC can run on, and thus the number of people able
to experiment with ExoPC.

I broke this project up into three major phases to group the
information I needed to learn.  The first phase was learning about
ExoPC itself.  Although I'd read many of the published papers about
Exokernel before entering this project, I had not examined any of the
source code or the driver model of the kernel.  The second phase was
examining the IDE drive support of other free operating systems, and
choosing the model that would be most appropriate to use for ExoPC.
Due to the size of the project, porting a device driver from another
operating system seemed the most realistic and timely approach to
take.  The final stage of the project was to actually perform the port
of the IDE driver and integrate it into ExoPC, then perform all the
debugging necessary to ensure proper compatibility. 

This document will be broken up according to the three phases of the
project, first covering the ExoPC driver model, then the evaluation of
other OSs, and finally the porting of the IDE driver to ExoPC and its
debugging.  

\section{The ExoPC Driver Model}

The ExoPC distribution already contains ports of several device
drivers from other free operating systems, including several network
card drivers from OpenBSD and NetBSD, and a SCSI controller from
NetBSD.  These drivers served as a model of the necessary changes for
adapting a driver from another operating system, indicating the areas
where ExoPC was closely related to more traditional OSs, and those
areas where extensive modifications would need to be made.  The
existing SCSI hard driver controller code was particularly useful,
because it interacted directly with the ExoPC disk subsystem,
modeling the upper level interface that the IDE driver would need to
adapt to.

The most immediately interesting part of the ExoPC driver model was
the boot sequence, because this was when the IDE controller would need
to be detected and initialized, followed by identification of the hard
drives attached to that controller.  The most relevant portions of the
boot sequence were those that communicated with the BIOS, then
initialized and searched the data busses, for this was where the IDE
initialization would need to take place.  The BIOS communication
routines of ExoPC are straight forward, providing the needed
functionality.  However, the data bus support was much less complete
--- only the PCI and SCSI busses were supported, and SCSI only through
an intermediary PCI adapter card.  This created immediate issues,
because traditionally IDE drives have been attached via the ISA bus.

Adding ISA bus support to ExoPC was discussed, but a feasibility
analysis suggested that finding an alternate solution would be more
reasonable.  The most complicated issues with adding ISA support were
the addition of interrupt handling on a much wider range of channels,
the need for intermediate buffers to handle DMA transactions to high
areas of memory (known as bounce buffers), and the the handling of DMA
requests in general.  The first was complicated because it involved
sizable amounts of assembly language coding which, while doable, would
be very time consuming.  The second and third issues involved heavy
interaction with the ExoPC virtual memory, which is substantially
different than the virtual memory system found in any other free OS,
and thus would require near complete rewrites.

Luckily, a reasonable alternative to adding ISA support was available,
in the form of PCI IDE controllers.  These devices are comparatively
new, and are found only on modern motherboards, but are widespread
enough to still make their support a valuable addition to ExoPC.  Most
PCs produced from this point forward will include PCI IDE controllers,
since this functionality is frequently built into the same chip that
holds many of the other critical system services, such as the cache
and DRAM controllers, interrupt controller, timer, and sometimes
universal serial bus support.  Intel, Promise, and VIA all make such
controller cards, and thus support for all these varieties of chips
must be added.  A PCI IDE drive includes support for accesses via the
traditional ISA I/O register set, as well as adding dynamically
configured PCI registers and DMA over the PCI bus, for potentially
higher performance (although it's rare that IDE drives are able to
even saturate the ISA bus).

The final issue with ExoPC is its lack of a kernel configuration
file.  It is very difficult to reliably probe for and recognize IDE
drives due to the different interpretations of the ATA specification by
different vendors, and thus most free OSs use a kernel link-time
configuration file to supply information about the number and location
of IDE drives to be found on the destination system.  ExoPC's bus
configuration system is designed with configurable and easily
identifiable peripherals in mind, such as are found on the PCI bus,
and thus no kernel configuration file is needed.  Thus, the PCI IDE
driver currently contains it's own set of configuration definitions to
allow a user to choose the number of drives attached.  This solution
lacks the elegance of a full kernel configuration file, but until
ExoPC requires more static definitions, a kernel configuration file is
overkill.


\section{Other Free Operating Systems}

The large volume of code and complexity of design needed for a IDE
drive made the porting of a driver from another free OS seem much more
feasible than writing a driver from scratch.  The primary free
operating systems to borrow from are Linux, NetBSD, OpenBSD, and
FreeBSD.  Each of these operating systems has its strengths and
weaknesses, and the quality of the IDE driver varied greatly in
between them.  NetBSD or OpenBSD were the most obvious candidates for
porting, because much of the rest of ExoPC is based on code taken from
one of these two OSs.  Indeed, most of the code within is extremely
similar, because OpenBSD is based on a relatively recent branch of the
NetBSD source tree.  The IDE driver from these OSs was relatively
straight forward and clean, and seemed like a logical choice.

Unfortunately, NetBSD (and therefore OpenBSD also) switched to the
``bus map'' system internally in the recent past to allow for greater
cross-platform source compatibility, and these routines looked to be
fairly difficult to extract from NetBSD and replicate for ExoPC.  The
linux driver model is sufficiently different from the ExoPC driver
model to make porting it infeasible, due to the roots in System V that
Linux comes from, as compared to OpenBSDs, and therefore ExoPCs,
origins with the BSD kernel.  This left FreeBSD, which luckily turned
out to be a very good match for ExoPC.  The FreeBSD code was the
simplest of all the free OSs, and grouped into a relatively small set
of files.  The FreeBSD driver model matched well with that of ExoPC,
and their IDE PCI support was the best of all the free OSs examined,
thus making it the obvious choice.

The only major issue with the FreeBSD IDE driver was that it used a
self-described hack to avoid conflicts between the PCI and ISA busses,
in which it passed large amounts of data around via the ISA
subsystem.  Removing this extra layer of indirection simplified the
data flow of the ExoPC driver greatly, and made control flow of the boot
sequence much simpler, in comparison to the FreeBSD driver.

\section{Porting to ExoPC}

With the selection of the FreeBSD IDE driver as a base, porting to
ExoPC was a fairly straightforward proposition.  The driver was broken
into two major portions, the PCI IDE controller probing and
initialization routines (contained in {\bf ide\_pci.c} \cite{idepci}),
and the actual hard drive initialization and communication routines
(contained in {\bf wd.c} \cite{wd}).

\subsection{PCI Interface}

The first portion of code (in {\bf ide\_pci.c}) is responsible for
interfacing with the PCI bus initialization routines to identify each
card in the bus, then calling the appropriate initialization routines
for that card.  These initialization routines perform any hardware
initialization that still needs to be done, and setup OS internal data
structures that will allow for communications with the device later
on.  For the PCI IDE driver, this meant adding the identifiers for
various PCI IDE controllers into the list of identifiers that ExoPC
matches each card against, and a pointer to the PCI IDE attach routine
({\it ide\_pci\_attach}), to be called when an IDE controller is
found.

\subsection{Probe and Attach Routines}

This attach routine is responsible for reading all the configuration
details of the card, and modifying them as needed, then reconfiguring
the card as appropriate.  Then the attach routines sets up internal
routines to handle interrupts from this device, and requests for DMA
transfers to or from the device.  Finally, for the ExoPC driver, it
searches for hard drives attached to the controller (using the {\it
wd\_pci\_probe} function), and then calls the hard drive initialization
routines if drives are found (using the {\it wd\_pci\_attach}
function).  Each PC usually contains two IDE controllers, each capable
of handling two hard drives.  Thus, the probe routine is responsible
for querying the given controller to check if any hard drives are
attached to it; if not, the controller is ignored, otherwise the
hard drive attach routine is called for that controller.

The hard drive attach routine is responsible for identifying the exact
characteristics of the drives under the current controller, setting
the drives up for usage, and saving all information needed for later
communications with that disk.  Disk identification is still an
inexact procedure, because different hard drives respond differently
to probing routines.  Properly compliant hard drives respond to a
READP request with all the information necessary to identify them, but
too many drives (especially older ones) fail to execute this request
properly, or don't support it at all.  In this case, it's necessary to
probe the BIOS for the details of this drive.  For ExoPC, all hard
drive information is stored in a global Sysinfo structure, for use
later on, and thus all garnered information is fed into the
appropriate fields of this structure.  

\subsection{Disk Strategy Routine}

The core communications routine used during program execution to read
or write data to the disk is the {\it wdstrategy} function.  A pointer
to this function is stored in the kernel during system initialization,
and when an application wants to perform a data transfer, it creates a
{\it buf} structure, containing the parameters of the transfer, such
as disk data location (specified in terms of the block number on the
disk), memory data address, the direction of transfer, and the number
of blocks to transfer.  The {\it wdstrategy} routine performs error
checking on this {\it buf} structure to avoid invalid parameters, then
inserts it into a queues for the appropriate disk controller.  When
the {\it buf} structure reaches the front of the queue (immediately if
the queue is empty, otherwise checked at the completion of other
transfers), the block number is translated into the the sector,
cylinder, and head to reach the physical disk location.  Finally,
the transfer is performed, using DMA if the device is capable and the
transfer is long enough to make it worthwhile, otherwise using
programmed I/O to transfer the data.  When the transfer is complete,
the {\it buf} structure is marked as complete, and the application can
continue.

\subsection{Complex Issues}

The two most complex issues of the IDE driver are bad block handling
and disklabel handling.  Bad block handling is performed by forcing
all data transfers to be handled in minimal size chunks, so that each
can simply time out if errors occur, and other blocks can be
substituted, according to the bad sector table on the drive.
Currently parts of this support are not added into the ExoPC driver,
specifically the substitution from the bad sector table.  This will be
added on a soon as a more flexible way of handling the bad sector
table is handled --- the FreeBSD driver relies upon a series of drive
characteristics that seemed to be very OS specific.  Disklabel
handling is similarly complex, because it contains many of these
important drive characteristics, including the location of the bad
sector tables, and if someone writes to the disklabel locations on
disk, then the copy of the disklabel in memory must be similarly
updated.  When the bad block handling is added into the ExoPC driver,
the disklabel handling will be added as well --- until then, this code
is unnecessary.  These two tasks compromise the majority of further
work on this driver; the basic functionality works, and now stability,
performance, and error handling must be further enhanced.

\section{Conclusion}

Adding PCI IDE support to ExoPC was a very broadly scoped project,
because it required knowledge of such a wide variety of systems, both
inside ExoPC and other operating systems.  However, this information
could be compartmentalized easily by breaking the project into phases,
avoiding overly complicating any issues.  By first understanding
ExoPC, then examining other OSs for similar driver models, an easily
portable PCI IDE driver was found.  The act of porting this driver was
relatively straight forward, largely due to the work done in preparing
beforehand.  Thus, ExoPC now supports a much wider range of PCs due to
its support of more standard hardware, enabling a broader base of
users to work with it.

\section{Acknowledgments}
I'd like to Frans Kaashoek for his guidance and support on the
project, Thomas Pinckney for his introduction to ExoPC, and Russel
Hunt for his suggestions on debugging ExoPC. 

\newpage
\singlespace
\begin{thebibliography}{9}

\bibitem{exokernel} D.R. Engler, M.F. Kaashoek, and J. O;Toole Jr.
Exokernel: an operating architecture for application-specific resource
management.  In Proceedings of the Fifeenth ACM Symposium on Operating
Systems Principles, pages 251-266, December 1995.

\bibitem{idepci} FreeBSD, Inc.  ide\_pci.c, version 1.9.
http://www.freebsd.org.

\bibitem{wd} FreeBSD, Inc.  wd.c, version 1.156.
http://www.freebsd.org.

\end{thebibliography}

\end{document}
