\chapter{SOTEST}

SOTEST consists of three main components: a generic Intel 80186
microprocessor simulator, a symbolic debugger, and an interpreter for
SOTL, a general Turing-equivalent high-level language designed for
hardware modeling.  Of course the pieces must interface to one another
in a variety of ways, but the boundaries are sufficiently well-defined
to make it possible to change to a different microprocessor type with
a reasonably low investment of effort.

\section{80186 Engine}

The 80186 interpreter works at an instruction level.  It makes no
attempt to simulate individual bus cycles, logic levels on 80186 pins,
and so forth.  Instead, it represents memory with a large array,
remembers the values of registers and flags, and keeps track of the
state of other internal components of the 80186 (including its
built-in interrupt controller, timer block, and DMA controller).  It
reads instructions from its memory array, decodes them, and performs
the operation required, updating its internal state appropriately.  In
addition, it knows how long each instruction takes to execute on a
real 80186, and keeps a running total of the amount of time (in clock
cycles) that a real 80186 would have spent executing the software.

\section{Symbolic Debugger}

The symbolic debugger contains facilities for loading Intel absolute
object module files, interpreting Microsoft symbolic debugging
information, setting breakpoints, displaying stack frames, displaying
the values of variables, locating positions in source files, and so
on.  It has essentially the same facilities as any standard symbolic
debugger, such as dbx or gdb.  It is part of the 80186 interpreter in
the sense that it is heavily 80186-dependent, but it is tied to the
SOTL interpreter insofar as symbolic debugging commands can be issued
by SOTL programs.

\section{SOTL Interpreter}

The other major component of SOTEST is the SOTL interpreter.  SOTL is
a block-structured, high-level, multi-threaded, event-driven language
designed for hardware modeling at an instruction (rather than signal)
level.  It is very rich, providing subroutines, local variables,
automatic memory management, dynamic strings and arrays, regular
expression matching, and access to certain host system calls, as well
as operators that access and manipulate the 80186 simulation and
access to the symbolic debugging facilities.  A full reference manual
for the language is included in the appendix.

\psfig{sotest-architecture.idraw}{SOTEST Architecture}{sotest:arch}

\section{Interactions between the 80186 Engine and SOTL}

The model chosen for interactions between the 80186 engine and SOTL
threads is an event-driven model.  The 80186 engine generates events,
which can be received by interested SOTL threads.  There is an event
generated whenever an instruction is fetched (breakpoint event), the
count of clock ticks reaches a certain value (breaktime event), a
memory location is read or written, or an I/O port is read or written.
Each SOTL thread specifies a set of events that it's interested in.
Typically, a thread is modeling an external device which is, for
example, mapped into the processor's memory at a certain range of
addresses.  The thread modeling this device would first {\it
subscribe} to memory read and write events over that range of
addresses, and then {\it block} (go to sleep).  When a relevant event
is received, the thread would wake up, examine the event, and act
accordingly.  Actions to take could include displaying messages,
modifying internal state, or writing values into simulated memory.  A
return value can be provided in response to a memory read event, so
that the thread can specify the value that the processor should see.
The user may also subscribe to events, and will be notified when an
event matching his subscription is received.

Events actually have sources other than the 80186 engine.  A thread
can ask for events when a UNIX file descriptor or message queue
becomes readable, when a message is sent from another thread, or when
another thread exits.

\section{Scheduling}

There are three things that SOTEST might be doing at any given time.
It could be running 80186 instructions, running SOTL threads, or
reading commands from the user.  How to prioritize these duties is
subtle and important.  The rules governing scheduling of these jobs
are somewhat complicated.  I will first state them, and then explain
their motivation.  

\subsection{Scheduling Rules}

\psfig{scheduling.idraw}{SOTEST Scheduling}{sotest:sched}

SOTEST has three states as diagrammed in Figure~\ref{sotest:sched}:
waiting for a command from the user, running threads, and simulating
80186 instructions.  SOTEST begins in the first state.  When the user
types a command, the command is parsed and run as a thread.  This
thread is special, and is called the {\it foreground thread;} all
other threads are called {\it background threads.} SOTEST then changes
into the state in which it runs the threads.  The order in which
individual threads are run is unpredictable and generally not
relevant.  It will stay in this state until all background threads are
blocked, and the foreground thread is either blocks or exits (or is
killed).  If the foreground thread is gone, it resumes waiting for
commands.  If the foreground thread blocks, then SOTEST runs 80186
instructions.  It does this until an event is generated which unblocks
a thread, in which case it resumes running threads, or until the
foreground thread spontaneously exits, in which case it resumes
reading commands.  The foreground thread spontaneously exits if the
user presses control-C, or if the user receives an event.

It is possible that more than one thread will have an event in its
event queue at the same time.  In this case, the system must make a
decision about which thread to run first.  In SOTEST, events are not
processed in any particular order; if events are waiting for more than
one thread, the choice of which thread to run is arbitrary.  While it
is possible to construct a program that depends on the order in which
events are received, we have been unable to come up with a useful
program of this type.  Of course, all events generated by a single
instruction are processed before the next instruction is interpreted,
so it will never be the case that an event for a given instruction is
processed after an event for a subsequent instruction.

\subsection{Motivations for Scheduling Rules}

Clearly SOTL threads must have priority over the 80186 engine.  When
an 80186 instruction performs, for example, a memory read, which
causes an event to be sent to a thread, the engine must wait for the
thread to calculate the value that should be read before it can
proceed.  In general, therefore, if any thread is {\it unblocked} then
it his priority over the 80186 interpreter.  Thus, the first rule is
that all threads must block or exit before any instructions will be
interpreted.

Remaining scheduling semantics are motivated by the intended use of
foreground and background threads.  Background threads are intended to
be doing hardware simulation.  If they have computation to do, it is
likely because the external hardware they are simulating needs to
update its state.  The thread blocks when this state is determined,
and it is waiting for interaction with the microprocessor.  If a
thread needs to spread a computation over 80186 time, it can
explicitly block until the clock advances a sufficient amount.  Since
the threads simulate relatively independent hardware units, the
threads' computations are generally independent as well, and so it
does not matter which thread runs first if multiple threads have
queued events.

The foreground thread, on the other hand, is treated specially because
it is meant to be performing a simple action on behalf of the user; it
represents the user's intentions.  The user probably wants this action
to complete before entering another command.  If this action causes
other threads to run, then we probably want them to run to completion
before allowing the user to enter another command.  If this action
blocks, then the user probably wants the 80186 interpreter to run.
For example, the ``go'' command is implemented as an infinite block.
It carries out the user's intentions of relinquishing control and
letting the simulation run.

\subsubsection{Breakpoints}

In SOTEST's model of simulation, the users ``sets a breakpoint'' by
subscribing to breakpoint events at the desired code location.  When
the code reaches the given location, the breakpoint event is sent to
the user.  Whenever the user receives an event, the event is displayed
and the foreground thread is killed.  Then, after all background
threads block (they may have subscribed to the same breakpoint event),
control returns to the user.

\subsubsection{Control-C Interrupts}

If the user presses control-C, the foreground thread is immediately
killed.  If SOTEST was simulating instructions at the time, control is
returned immediately to the user.  If SOTEST was running threads, the
background threads continue to run until all block (or exit); only
then is control returned to the user.  The user must take care not to
allow a background thread to get stuck in an infinite loop.  If a
background thread is under development, the user may place the thread
in ``debug mode''.  When the user presses control-C, all threads in
debug mode become ``frozen'' (blocked until granted permission to run
by the user).  When all other threads block, threads being debugged
can have their state examined, and may be unfrozen or killed.