\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.