
\chapter{SOTEST Implementation}

%
%% SOTEST Implementation
%

%%% \psfig{thread-anatomy.idraw}{The Anatomy of a Thread}{sotl:thread}

General techniques for implementing each of SOTEST's major components,
namely, the hardware modeling language, the microprocessor simulator,
and the symbolic debugger, are well understood.  One interesting
aspect of SOTEST's implementation is efficient event dispatching;
another is efficient handling of time periods when the simulated
machine has nothing to do (idle trapping.)

\section{Event Dispatching}

For each thread, SOTEST maintains a list of {\it event specifiers}
that describe the class of events that the thread is interested in.
Clearly the system would be terribly inefficient if it searched each
thread's event specifier list every time anything happened that can
generate an event (there are typically two or three such occurrences
for each simulated instruction: an instruction fetch and a memory read
or write).  SOTEST employs different strategies for different event
types, in an ad-hoc attempt to squeeze as much performance out of the
system as possible.

\subsection{Breakpoint Events}

SOTEST implements breakpoints without performance degradation of the
80186 interpreter.  The 80x86 instruction set contains breakpoint
(\(INT3\)) instruction, which causes a trap when executed.  When the
user of a native 80x86 debugger requests a breakpoint, the debugger
actually stores the instruction into the code segment of the target
program at the location indicated by the user.  Then, when the program
is executed, when it reaches that point, the 80x86 traps to the
debugger.  SOTEST uses a very similar strategy.  When a thread
requests a breakpoint event, the request is recorded in a list of
breakpoints and the program text is modified.  The interpreter's main
loop contains a jump table based on the opcode of the instruction; the
jump table entry for the \(INT3\) is a breakpoint handler, which scans
the list of breakpoints generating the appropriate events.  The
threads are allowed to run, and, when the thread subsystem is
quiescent, the instruction originally stored at the breakpoint address
is executed.

One drawback of this technique is that the program code modifications
need to be temporarily undone when the user, for example, unassembles
the program near the breakpoint; in addition, attempts to set
breakpoints at locations where self-modifying programs write
instructions will cause unpredictable behavior.  However, the
ability to support breakpoints without slowing down the 80186
interpreter's general case was too attractive to pass up.

\subsection{Memory Read and Write Events}

It is assumed that for most applications, the number of subscriptions
to memory read events is fairly small, and that these subscriptions
are likely to be localized.  This makes sense because system
architects generally partition the 80186's address space into a large
region for RAM and ROM and a small region for memory-mapped external
hardware.  To attempt to implement memory read and write events
efficiently, SOTEST divides the simulated one-megabyte address space
into 4096 256-byte ``pages.''  A bit array contains two bits for each
page, one which is set if some thread might be subscribed to read
events for some locations in the page, and one for write events.  On
each memory read or write, SOTEST checks the bit corresponding to the
page, and, if set, scans the list of memory read (write)
subscriptions.  If no subscription is found for the page, the bit is
cleared.  For each subscription in the list which contains the
location in question, an event is sent to the corresponding thread.
This strategy slows down memory accesses only very slightly for normal
memory pages ({\it i.e.,} pages on which no subscriptions are
registered.) 

\subsection{Port Read and Write Events}

While it may seem that port reads and writes should be handled exactly
like memory reads and writes, SOTEST in fact uses a much simpler
strategy.  On every port read or write, the entire list of port
subscriptions is scanned.  The reason for this is that port reads and
writes are meaningless unless some thread is subscribed to the port; 
therefore, it is assumed that the vast majority of port reads and
writes will result in some thread receiving an event.  In this case,
the cost of processing the event is so much greater than the cost of
scanning the list that we felt there was no need for a more complex
mechanism.

\subsection{Conclusions}

Efficient event distribution is an important requirement for attaining
reasonable performance in SOTEST.  Different mechanisms are used for
different event types because of the different characteristics of
their usage patterns.  While no detailed performance measurements have
been taken, SOTEST, running on a Sun SparcStation II, runs 80186
programs at approximately 5\% of the speed they would run on a real 16
megahertz 80186; that is, they take 20 times longer to run on a Sparc.
A factor of 20 slowdown ends up being acceptable for many
applications, since most embedded systems are I/O-bound, not
CPU-bound, most of the time.

\section{Idle Trapping}

A real embedded system is idle much of the time.  Most systems are
constructed to have some sort of idle loop, where the machine is doing
some boring task, such as calculating a checksum of itself, waiting
for an interrupt (timer or device) to wake it up.  In a typical SOTEST
simulation, the simulated target is being stimulated by interrupts
generated at appropriate times by threads.  For example, suppose an
embedded system is set up to poll for events each time a
one-millisecond timer interrupt is received.  The SOTL simulation code
might be set up as follows:

\code
    fork {
        while (1) {
            blockuntil breaktime(clock + 16000);
            print "Sending poll interrupt";
            interrupt 8;
        }
    };
\code

When the user starts the simulation, the target software will run,
receiving an interrupt every millisecond.  Once initialization is
complete, the target software will be idle most of the time.  Unless
the user wishes to test the idle loop itself, time spent by SOTEST
simulating the instructions in the idle loop is wasted.  It would be
much better for SOTEST to send interrupts as fast as possible, until
the target software decides it has something to do.  This is
implemented by the \(machineidle\) command.  This SOTL command
declares that the current machine has nothing to do, and should go
into idle mode.  When in idle mode, SOTEST does not actually interpret
instructions; instead, it spins the machine's clock until a thread
subscribed to a breaktime event wakes up.  If that thread does
something that would bring the target software out of the idle loop,
then the machine leaves idle mode.  Suppose our machine has a label
called \(_IDLE\) which contains the idle loop.  Then the user may
write

\code
    fork {
        while (1) {
            blockuntil _IDLE;
            machineidle _IDLE;
        }
    };
\code

This enhancement saves tremendous amounts of simulation time for
programs which are I/O-bound; it collapses time spent in I/O-wait to
almost nothing.  It brings no improvement for programs that are
CPU-bound, but they are not slowed either.

