\begin{abstract}
-We present a new approach to utilizing unsafe legacy unsafe code
+We present a new approach to utilizing unsafe legacy code
within safe virtual machines by compiling to MIPS machine code as an
intermediate language. This approach carries N key benefits over
existing techniques:
\item (Optional) compile the resulting bytecode into a {\it safe}
native binary using {\tt gcj}.
-\item From java code, invoke the {\tt execute()} on the generated
+\item From java code, invoke the {\tt run()} method on the generated
class. This is equivalent to the {\tt main()} entry point.
\end{enumerate}
\begin{itemize}
-\item The original MIPS ISA supports only 32-bit aligned memory loads
- and stores. This allows NestedVM to represent memory as a Java
- {\tt int[]} without introducing additional overhead.
+%\item The original MIPS ISA supports only 32-bit aligned memory loads
+% and stores. This allows NestedVM to represent memory as a Java
+% {\tt int[]} without introducing additional overhead.
+\item Most of the instructions in the original MIPS ISA operate only on
+ 32-bit aligned memory locations. This allows NestedVM to represent
+ memory as a Java {\tt int[]} array without introducing additional
+ overhead.
\item Unlike its predecessor, the R2000 supports 32-bit by 32-bit
multiply and divide instructions as well as a single and double
example is the treatment of the {\tt r0} register, which is fixed as
{\tt 0} in the MIPS ISA.
-Now that the binary-to-binary compiler is available, the
-binary-to-source compiler is only useful for generating input to {\tt
-gcj}, as discussed in section FOOBAR.
-
Lacking the ability to generate specially optimized bytecode
sequences, a straightforward mapping of the general purpose hardware
registers to 32 {\tt int} fields was optimal.
for(;;) {
switch(pc) {
case 0x10000:
- r29 = r29 ? 32;
+ r29 = r29 - 32;
case 0x10004:
r1 = r4 + r5;
case 0x10008:
is no corresponding limit on the size of a classfile as a whole.
Another interesting problem that was discovered while creating the
-trampoline method was javac and Jikes? inability to properly optimize
+trampoline method was javac and Jikes' inability to properly optimize
switch statements. The code in Figure~\ref{lookupswitch} is compiled
into a comparatively inefficient {\tt LOOKUPSWITCH}, while the code in
Figure~\ref{tableswitch} is optimized into a {\tt TABLESWITCH}.
\begin{figure}
{\footnotesize\begin{verbatim}
-Brian, we're missing the code here... can you put it in?
+switch(pc>>>8) {
+ case 0x1: run_100();
+ case 0x2: run_200();
+ case 0x3: run_300();
+}
\end{verbatim}}
\caption{\label{tableswitch} Code which {\it is} optimized into a tableswitch}
\end{figure}
-Javac isn?t smart enough to see the patter in the case values and
+Javac isn't smart enough to see the pattern in the case values and
generates very suboptimal bytecode. Manually doing the shifts
convinces javac to emit a tableswitch statement, which is
significantly faster. This change alone nearly doubled the speed of
the compiled binary.
Finding the optimal method size lead to the next big performance
-increase. It was determined with experimentation that the optimal
+increase. It was determined through experimentation that the optimal
number of MIPS instructions per method is 128 (considering only power
of two options). Going above or below that lead to performance
decreases. This is most likely due to a combination of two factors.
\item The two levels of switch statements jumps have to pass though -
The first switch statement jumps go through is the trampoline
- switch statement. This is implemented as a TABLESWITCH in JVM
+ switch statement. This is implemented as a {\tt TABLESWITCH} in JVM
bytecode so it is very fast. The second level switch statement
in the individual run\_ methods is implemented as a
- LOOKUPSWITCH, which is much slower. Using smaller methods puts
- more burden on the faster TABLESWITCH and less on the slower
- LOOKUPSWITCH.
+ {\tt LOOKUPSWITCH}, which is much slower. Using smaller methods puts
+ more burden on the faster {\tt TABLESWITCH} and less on the slower
+ {\tt LOOKUPSWITCH}.
\item JIT compilers probably favor smaller methods smaller methods are
easier to compile and are probably better candidates for JIT
\begin{itemize}
-\item The .text segment ? Every instruction in the text segment in
+\item The .text segment - Every instruction in the text segment is
scanned for jump targets. Every branch instruction (BEQ, JAL,
etc) has its destination added to the list of possible branch
targets. In addition, functions that set the link register have
- theirpc+8 added to the list (the address that would?ve been put
+ theirpc+8 added to the list (the address that would've been put
to the link register). Finally, combinations of LUI (Load Upper
Immediate) of ADDIU (Add Immediate Unsigned) are scanned for
possible addresses in the text segment. This combination of
instructions is often used to load a 32-bit word into a
register.
-\item The .data segment ? When GCC generates switch() statements it
+\item The .data segment - When GCC generates switch() statements it
often uses a jump table stored in the .data
- segment. Unfortunately gcc doesn?t identify these jump tables in
+ segment. Unfortunately gcc doesn't identify these jump tables in
any way. Therefore, the entire .data segment is conservatively
scanned for possible addresses in the .text segment.
-\item The symbol table ? This is mainly used as a backup. Scanning the
+\item The symbol table - This is mainly used as a backup. Scanning the
.text and .data segments should identify any possible jump
targets but adding every function in the symbol table in the ELF
- binary doesn?t hurt. This will also catch functions that are
+ binary doesn't hurt. This will also catch functions that are
never called directly from the MIPS binary (for example,
functions called with the call() method in the runtime).
pool. The constant pool in classfiles is limited to 65536
entries. Every Integer with a magnitude greater than 32767 requires an
entry in the constant pool. Every time the compiler emits a
-jump/branch instruction the PC field is set to the branch target. This
+jump or branch instruction the PC field is set to the branch target. This
means nearly every branch instruction requires an entry in the
constant pool. Large binaries hit this limit fairly quickly. One
workaround that was employed in the Java source compiler was to
\begin{itemize}
\item There are little tricks that can be done in JVM bytecode that
- can?t be done in Java source code.
+ can't be done in Java source code.
-\item Eliminates the time-consuming javac step ? Javac takes a long
+\item Eliminates the time-consuming javac step - Javac takes a long
time to parse and compile the output from the java source
compiler.
and in taking advantage of the JVM stack to eliminate unnecessary
LOADs and STOREs to local variables.
-The first obvious optimization that generating bytecode allows for is
-the use of GOTO. Despite the fact that java doesn?t have a GOTO
-keyword a GOTO bytecode does exist and is used heavily in the code
-generates by javac. Unfortunately the java language doesn?t provide
-any way to take advantage of this. As result of this jumps within a
-method were implemented by setting the PC field to the new address and
+The first obvious optimization that generating bytecode allows for is the
+use of GOTO. Despite the fact that java doesn't have a GOTO keyword a GOTO
+bytecode does exist and is used heavily in the code generates by javac.
+Unfortunately the java language doesn't provide any way to take advantage of
+this. As result of this, jumps within a method were implemented in the
+binary-to-source compiler by setting the PC field to the new address and
making a trip back to the initial switch statement. In the classfile
compiler these jumps are implemented as GOTOs directly to the target
instruction. This saves a costly trip back through the LOOKUPSWITCH
condition is true the JVM as to jump to the switch block. By
generating bytecode directly we can make the target of the JVM branch
statement the actual bytecode of the final destination. In the case
-where the branch isn?t taken the JVM doesn?t need to branch at all.
+where the branch isn't taken the JVM doesn't need to branch at all.
A side affect of the above two optimizations is a solution to the
excess constant pool entries problem. When jumps are implemented as
-GOTOs and direct branches to the target the PC field doesn?t need to
+GOTOs and direct branches to the target the PC field doesn't need to
be set. This eliminates many of the constant pool entries the java
source compiler requires. The limit is still there however, and given
a large enough binary it will still be reached.
Delay slots are another area where things are done somewhat
inefficiently in the Java source compiler. In order to take advantage
-of instructions already in the pipeline MIPS cpu have a ?delay
-slot?. That is, an instruction after a branch or jump instruction that
+of instructions already in the pipeline MIPS cpu have a ``delay
+slot''. That is, an instruction after a branch or jump instruction that
is executed regardless of whether the branch is taken. This is done
because by the time the branch or jump instruction is finished being
processes the next instruction is already ready to be executed and it
\begin{enumerate}
-\item r2 is set to ?1
+\item r2 is set to -1
\item r2 is loaded from the register file by the BLTEZ instruction
\item 10 is added to r2 by the ADDIU instruction
\item The branch is taken because at the time the BLTZ instruction was
- executed r2 was ?1, but r2 is now 9 (-1 + 10)
+ executed r2 was -1, but r2 is now 9 (-1 + 10)
\end{enumerate}
-There is a very element solution to this problem when using JVM
+There is a very elegent solution to this problem when using JVM
bytecode. When a branch instruction is encountered the registers
needed for the comparison are pushed onto the stack to prepare for the
JVM branch instruction. Then, AFTER the values are on the stack the
statement each case arm was reduced in size by one instruction. Similar
optimizations were also done in other parts of the compiler.
-
\section{Interfacing with Java Code}
-Java source code can create a copy of the translated binary by
-instantiating the corresponding class, which extends {\tt Runtime}.
-Invoking the {\tt main()} method on this class is equivalent to
-calling the {\tt main()} function within the binary; the {\tt String}
-arguments to this function are copied into the binary's memory space
-and made available as {\tt argv**} and {\tt argc}.
+NestedVM has two primary ways of executing code, the interpreter, and the binary translators. Both the interpreter and the output from the binary translators sit on top of a Runtime class. This class provides the public interface to both the interpreter and the translated binaries.
-The translated binary communicates with the rest of the VM by
-executing MIPS {\tt SYSCALL} instructions, which are translated into
-invocations of the {\tt syscall()} method. This calls back to the
-native Java world, which can manipulate the binary's environment by
-reading and writing to its memory space, checking its exit status,
-pausing the VM, and restarting the VM.
+\subsection{The Runtime Class}
+The Runtime class does the work that the operating system usually does. Conceptually the Runtime class can be though of as the operating system and itÕs subclasses (translated binaries and the interpreter) the CPU. The Runtime fulfills 5 primary goals:
-\subsection{Virtualization}
+\begin{itemize}
-The {\tt Runtime} class implements the majority of the standard {\tt
-libc} syscalls, providing a complete interface to the filesystem,
-network socket library, time of day, (Brian: what else goes here?).
+\item Provides a consistent external interface - Because only Runtime exposes a public interface the method of actually executing the code (currently only translated binaries and the interpreter) can be changed without any code changes.
-\begin{itemize}
+\item Provide an easy to use interface - The interpreter and the output from the binary translators only know how to execute code. The Runtime class provides an easy to use interface to the code. It contains methods to pass arguments to the main() function, read and write from memory, and call individual functions in the binary.
-\item ability to provide the same interface to CNI code and
- NestedVMified code
-
-\item security advantages (chroot the {\tt fork()}ed process)
+\item Manage the processÕs memory - The Runtime class contains large int[] arrays that represent the processÕs entire memory space. Subclasses read and write to these arrays as required by the instructions they are executing. Subclasses can expend their memory space using the sbrk syscall.
+
+\item Provide access to the file system and streams - Subclasses access the file system through standard UNIX syscalls (read, write, open, etc). The Runtime manages the file descriptor table that maps UNIX file descriptors to Java RandomAccessFiles, InputStreams, OutputStreams, and sockets.
+
+\item Miscellaneous other syscalls - In additions to those mentioned above the Runtime class implements a variety of other syscalls (sleep, gettimeofday, getpagesize, sysconf, fcntl, etc).
\end{itemize}
+\subsection{Interacting with the Binary}
+
+Java source code can create a copy of the translated binary by instantiating the class generated by the binary translator or instantiating the interpreter. It can then interact with the process through the many facilities provided by the Runtime interface. Invoking the run() method of the Runtime interface will load the given arguments into the processÕs memory as invoke the binaries entry point (typically \_start() in crt0.o). This will pass control on to the main() function which will have the arguments passed to run() loaded into argv and argc.
+
+As the binary executes it often passes control back to the Runtime class through the MIPS {\tt SYSCALL} instruction. The interpreter and translated binaries invoke the {\tt syscall()} method of the Runtime class when the {\tt SYSCALL} instruction is executed. The Runtime class then can manipulate the processÕs environment (read and write to memory, modify the file descriptor table, etc) and interact with the rest of the JVM on behalf of the process (read and write to a file or stream, etc). There is even a syscall to pause the VM and temporarily return control to the caller.
+
+In addition to the interfaces provided by NestedVM, users can create their own interfaces between the MIPS and Java world. The Runtime provides a method called call() that will call a function by name in the MIPS binary. The call() method looks up the function name in the binaryÕs ELF symbol table and manipulating the stack and registers accordingly to execute the given function. This allows Java code to seamlessly invoke functions in the binary.
+
+{\footnotesize\begin{verbatim}
+// Java
+private Runtime rt = new MyBinary();
+public void foo(int n) {
+ for(int i=0;i<10;i++) {
+ int result = rt.call("do_work",i);
+ System.err.println("do_work(i) = " + result);
+ }
+}
+// C
+void do_work(int n) {
+ int i;
+ int ret=0;
+ for(i=0;i<n;i++) ret += i;
+ return n;
+}
+\end{verbatim}}
+
+The MIPS binaries can also invoke a special method of Runtime called callJava().When the MIPS binary invokes the {\tt CALL\_JAVA} syscall (usually done through the {\tt \_call\_java()} function provided by the NestedVM support library) the callJava() method in Runtime is invoked with the arguments passes to the syscall.
+
+{\footnotesize\begin{verbatim}
+// Java
+private Runtime rt = new MyBinary() {
+ pubilc int callJava(int a, int b, int c, int d) { System.err.println("Got " + a + " " + b);
+};
+public void foo() { rt.run(); }
+// C
+void main(int argc, char **argv) {
+ \_call\_java(1,2);
+}
+\end{verbatim}}
+
+These two methods can even be combined. MIPS can call Java through the CALL\_JAVA syscall, which can in turn invoke a MIPS function in the binary with the call() method.\r\r
+Users preferring a simpler communication mechanism can also use Java StreamÕs and file descriptors. Runtime provides a simple interface for mapping a Java Input or OutputStream to a File Descriptor.
+
+%Java source code can create a copy of the translated binary by
+%instantiating the corresponding class, which extends {\tt Runtime}.
+%Invoking the {\tt main()} method on this class is equivalent to
+%calling the {\tt main()} function within the binary; the {\tt String}
+%arguments to this function are copied into the binary's memory space
+%and made available as {\tt **argv} and {\tt argc}.
+
+%The translated binary communicates with the rest of the VM by
+%executing MIPS {\tt SYSCALL} instructions, which are translated into
+%invocations of the {\tt syscall()} method. This calls back to the
+%native Java world, which can manipulate the binary's environment by
+%reading and writing to its memory space, checking its exit status,
+%pausing the VM, and restarting the VM.
+
+
+%\subsection{Virtualization}
+
+%The {\tt Runtime} class implements the majority of the standard {\tt
+%libc} syscalls, providing a complete interface to the filesystem,
+%network socket library, time of day, (Brian: what else goes here?).
+
+%\begin{itemize}
+
+%\item ability to provide the same interface to CNI code and
+% NestedVMified code
+
+%\item security advantages (chroot the {\tt fork()}ed process)
+%
+%\end{itemize}
+
\section{Quantitative Performance}
\subsection{Optimizations}
-Brian, can you write something to go here? Just mention which
-optimizations helped and which ones hurt.
+Although NestedVM perfectly emulates a MIPS R2000 CPU its performance characteristics aren't anything like an actual MIPS R2000 CPU. GCC makes several optimizations that increase performance on an actually MIPS CPU but actually decrease performance when run through the NestedVM binary translator. Fortunately, GCC provides many options to customize its code generations and eliminate these optimizations. GCC also has optimization options that aren't helpful on a real MIPS CPU but are very helpful under NestedVM
+
+Adam, we should cite "Using the GNU Compiler Collection" somewhere in here.
\begin{itemize}
-\item {\tt trampoline}
-\item {\tt optimal method size}
-\item {\tt -msingle-float}
-\item {\tt -mmemcpy}
-\item {\tt fastmem}
-\item {\tt local vars for registers (useless)}
+
+\item {\tt -falign-functions}
+Normally a function's location in memory has no effect on its execution speed. However, in the NestedVM binary translator the .text segment is split up on a power of two boundary. If a function is unlucky enough to start near the end of one of these boundaries a performance critical part of the function could end up spanning two methods. There is a significant amount of overhead in switching between two methods so this must be avoided at all costs. By telling GCC to align all functions to the boundary that the .text segment is split on the chances of a critical part of a function spanning two methods is significantly reduced.
+
\item {\tt -fno-rename-registers}
-\item {\tt -ffast-math}
-\item {\tt -fno-trapping-math}
-\item {\tt -fsingle-precision-constant}
-\item {\tt -mfused-madd}
-\item {\tt -freg-struct-return}
-\item {\tt -freduce-all-givs}
-\item {\tt -fno-peephole}
-\item {\tt -fno-peephole2}
-\item {\tt -fmove-all-movables}
-\item {\tt -fno-sched-spec-load}
-\item {\tt -fno-sched-spec}
-\item {\tt -fno-schedule-insns}
-\item {\tt -fno-schedule-insns2}
+Some processors can better schedule code when registers aren't reused for two different purposes. By default GCC will try to use as many registers as possibly when it can. This excess use of registers just confuses JIT's trying to compile the output from the binary translator. All the JIT compilers we tested do much better with a few frequently used registers.
+
\item {\tt -fno-delayed-branch}
-\item {\tt -fno-function-cse}
-\item {\tt -ffunction-sections}
-\item {\tt -fdata-sections}
-\item {\tt array bounds checking}
-\item {\tt -falign-functions=n}
-\item {\tt -falign-labels=n}
-\item {\tt -falign-loops=n}
-\item {\tt -falign-jumps=n}
-\item {\tt -fno-function-cse}
+The MIPS CPU has a delay slot (see above). Earlier versions of NestedVM didn't efficiently emulate delay slots. This option causes GCC to avoid using delay slots for anything (a NOP is simply placed in the delay slot). This had a small performance benefit. However, recent versions of NestedVM emulate delay slots with no performance overhead so this options has little effect. Nonetheless, these delay slots provide no benefit under NestedVM either so they are avoided with this option.
+
+\item {\tt -fno-schedule-insns}
+Load operations in the MIPS ISA also have a delay slot. The results of a load operation are not available for use until one instruction later. Several other instructions also have similar delay slots. GCC tries to do useful work wile waiting for the results of one of these operations by default. However, this, like register renaming, tends to confuse JIT compilers. This option prevents GCC from going out of its way to take advantage of these delay slots and makes the code generated by NestedVM easier for JIT compilers to handle.
+
+\item {\tt -mmemcpy}
+GCC sometimes has to copy somewhat large areas of memory. The most common example of this is assigning one struct to another. Memory copying can be done far more efficiently in Java than under NestedVM. Calls to the memcpy libc function are treated specially by the binary translator. They are turned into calls to a memcpy method in Runtime. The {\tt -mmemcpy} option causes GCC to invoke libc's memcpy() function when it needs to copy a region of memory rather than generating its own memcpy code. This call in then turned into a call to this Java memcpy function which is significantly faster than the MIPS implementation.
+
+\item {\tt -ffunction-sections -fdata-sections}
+These two options are used in conjunction with the {\tt --gc-section} linker option. These three options cause the linker to aggressively discard unused functions and data sections. In some cases this leads to significantly smaller binaries.
+
+%\item {\tt trampoline}
+%\item {\tt optimal method size}
+%\item {\tt -msingle-float}
+%\item {\tt -mmemcpy}
+%\item {\tt fastmem}
+%\item {\tt local vars for registers (useless)}
+%\item {\tt -fno-rename-registers}
+%\item {\tt -ffast-math}
+%\item {\tt -fno-trapping-math}
+%\item {\tt -fsingle-precision-constant}
+%\item {\tt -mfused-madd}
+%\item {\tt -freg-struct-return}
+%\item {\tt -freduce-all-givs}
+%\item {\tt -fno-peephole}
+%\item {\tt -fno-peephole2}
+%\item {\tt -fmove-all-movables}
+%\item {\tt -fno-sched-spec-load}
+%\item {\tt -fno-sched-spec}
+%\item {\tt -fno-schedule-insns}
+%\item {\tt -fno-schedule-insns2}
+%\item {\tt -fno-delayed-branch}
+%\item {\tt -fno-function-cse}
+%\item {\tt -ffunction-sections}
+%\item {\tt -fdata-sections}
+%\item {\tt array bounds checking}
+%\item {\tt -falign-functions=n}
+%\item {\tt -falign-labels=n}
+%\item {\tt -falign-loops=n}
+%\item {\tt -falign-jumps=n}
+%\item {\tt -fno-function-cse}
\end{itemize}
\section{Future Directions}
projects / nestedvm.git / blobdiff