1 \documentclass{acmconf}
4 \usepackage{amssymb,amsmath,epsfig,alltt}
15 \bibliographystyle{alpha}
17 \title{\textbf{\textsf{
18 NestedVM: Total Translation of Native Code into Safe Bytecode
21 \author{\begin{tabular}{@{}c@{}}
22 {\em {Brian Alliet}} \\
23 {Rochester Institute of Technology}\\
25 \end{tabular}\hskip 1in\begin{tabular}{@{}c@{}}
26 {\em {Adam Megacz}} \\
27 {UC Berkeley Statistical Computing Facility} \\
36 We present a new approach to utilizing unsafe legacy code
37 within safe virtual machines by compiling to MIPS machine code as an
38 intermediate language. This approach carries N key benefits over
42 \item total coverage of all language features, unlike source translation
43 \item no build process modifications
44 \item no post-translation human intervention
45 \item efficient bytecode
48 We also present NestedVM, a complete system in production use which
49 implements this technique. We conclude with quantitative performance
50 measurements and suggestions for VM acceleration of the resulting
56 \section{Introduction}
58 The C programming language \cite{KR} has been in use for over 30
59 years. Consequently, there is a huge library of software written in
60 this language. Although Java offers substantial benefits \cite{} over
61 C (and C++), its comparatively young age means that it often lacks
62 equivalents of many C/C++ libraries.
64 The typical solution to this dilemma is to use JNI \cite{} or CNI
65 \cite{} to invoke C code from within a Java VM. Unfortunately, there
66 are a number of situations in which this is not an acceptable
67 solution due to security concerns:
71 \item Java Applets are not permitted to invoke {\tt
72 Runtime.loadLibrary()}
74 \item Java Servlet containers with a {\tt SecurityManager} will not
75 permit loading new JNI libraries. This configuration is popular
76 with {\it shared hosting} providers and corporate intranets
77 where a number of different parties contribute individual web
78 applications which are run together in a single container.
80 \item Unlike Java Bytecode, JNI code is susceptible to buffer overflow
81 and heap corruption attacks. This can be a major security
86 In addition to security concerns, JNI and CNI carry other
91 \item JNI requires the native library to be compiled ahead of time,
92 separately, for every architecture on which it will be deployed.
93 This is unworkable for situations in which the full set of
94 target architectures is not known at deployment time.
96 \item The increasingly popular J2ME \cite{} platform does not support
99 \item JNI often introduces undesirable added complexity to an
104 The technique we present here is based on using a typical ANSI C
105 compiler to compile C/C++ code into a MIPS binary, and then using a
106 tool to translate that binary on an instruction-by-instruction basis
109 The technique presented here is general; we anticipate that it can be
110 applied to other secure virtual machines such as Microsoft's .NET
111 \cite{}, Perl Parrot \cite{}, or Python bytecode \cite{}.
113 \section{Approaches to Translation}
115 Techniques for translating unsafe code into VM bytecode generally fall
116 into four categories:
119 \item source-to-source translation
120 \item source-to-binary translation
121 \item binary-to-source translation
122 \item binary-to-binary translation
127 \newlength{\MyLength}
128 \settowidth{\MyLength}{machine code}
129 \newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
130 \begin{psmatrix}[colsep=3,rowsep=3]
131 [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
132 [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\
133 \psset{nodesep=5pt,arrows=->}
134 \ncline{s0}{b0}<{\it gcc}
135 \ncline{s0}{s1}\aput{:U}{\it c2java}
136 \ncline{s0}{b1}\aput{:U}{\it gcc bytecode backend}
137 \ncline{s1}{b1}>{\it javac}
140 \caption{\label{lattice} Conversion Lattice with examples of tools specific to a C/JVM scenario}
145 \newlength{\MyLength}
146 \settowidth{\MyLength}{machine code}
147 \newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
148 \begin{psmatrix}[colsep=3,rowsep=3,nrot=:U]
149 [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
150 [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\
151 \psset{nodesep=5pt,arrows=->}
152 \ncline{s0}{b0}<{\it gcc}
153 \ncline{s1}{b1}>{\it javac}
154 \ncline{b0}{s1}\naput{\it NestedVM}
155 \ncline{b0}{s1}\nbput{\it binary-to-source}
158 \caption{\label{lattice2} Conversion Lattice including NestedVM in {\it source-output} mode}
163 \newlength{\MyLength}
164 \settowidth{\MyLength}{machine code}
165 \newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
166 \begin{psmatrix}[colsep=3,rowsep=3,nrot=:U]
167 [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
168 [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\
169 \psset{nodesep=5pt,arrows=->}
170 \ncline{s0}{b0}<{\it gcc}
171 \ncline{s1}{b1}>{\it javac}
172 \ncline{b0}{b1}\naput{\it NestedVM}
173 \ncline{b0}{b1}\nbput{\it binary-to-binary}
176 \caption{\label{lattice3} Conversion Lattice including NestedVM in {\it bytecode-output} mode}
179 A diagram showing these four translation approaches in the context of
180 running C/C++ code within a Java VM is shown in Figure~\ref{lattice}.
182 \subsection{Existing Work}
183 \subsubsection{Source-to-Source Translation}
187 \item commercial products
190 A number of commercial products and research projects attempt to
191 translate C++ code to Java code, preserving the mapping of C++ classes
192 to Java classes. Unfortunately, this is problematic since there is no
193 way to do pointer arithmetic except within arrays, and even in that
194 case, arithmetic cannot be done in terms of fractional objects.
198 Many of these products advise the user to tweak the code which results
199 from the translation. Unfortunately, hand-modifying machine-generated
200 code is generally a bad idea, since this modification cannot be
201 automated. This means that every time the origin code changes, the
202 code generator must be re-run, and the hand modifications must be
203 performed yet again. This is an error-prone process.
205 Furthermore, NestedVM does not attempt to read C code directly. This
206 frees it from the complex task of faithfully implementing the ANSI C
207 standard (or, in the case of non ANSI-C compliant code, some other
208 interface). This also saves the user the chore of altering their
209 build process to accomodate NestedVM.
213 NestedVM takes a novel approach; it uses compiled machine code as a
214 starting point for the translation process. NestedVM has gone through
218 \item binary-to-source compilation (Figure~\ref{lattice2})
219 \item binary-to-binary compilation (Figure~\ref{lattice3})
222 \subsection{Translation Process}
224 Translating a legacy library for use within a JVM proceeds as follows:
228 \item Compile the source code to a statically linked binary, targeting
231 \item Invoke {\tt NestedVM} on the statically linked binary.
232 Typically this will involve linking against {\tt libc}, which
233 translates system requests (such as {\tt open()}, {\tt read()},
234 or {\tt write()}) into appropriate invocations of the MIPS
235 {\tt SYSCALL} instruction.
237 \item (If using binary-to-source translation) compile the resulting
238 {\tt .java} code using {\tt jikes} or {\tt javac}.
240 \item (Optional) compile the resulting bytecode into a {\it safe}
241 native binary using {\tt gcj}.
243 \item From java code, invoke the {\tt run()} method on the generated
244 class. This is equivalent to the {\tt main()} entry point.
249 \subsection{Why MIPS?}
251 We chose MIPS as a source format for two primary reasons: the
252 availability of tools to translate legacy code into MIPS binaries, and
253 the close similarity between the MIPS ISA and the Java Virtual Machine.
255 The MIPS architecture has been around for quite some time, and is well
256 supported by the GNU Compiler Collection, which is capable of
257 compiling C, C++, Java, Fortran, Pascal (with p2c), and Objective C
260 The MIPS R2000 ISA bears a striking similarity to the Java Virtual
265 %\item The original MIPS ISA supports only 32-bit aligned memory loads
266 % and stores. This allows NestedVM to represent memory as a Java
267 % {\tt int[]} without introducing additional overhead.
268 \item Most of the instructions in the original MIPS ISA operate only on
269 32-bit aligned memory locations. This allows NestedVM to represent
270 memory as a Java {\tt int[]} array without introducing additional
273 \item Unlike its predecessor, the R2000 supports 32-bit by 32-bit
274 multiply and divide instructions as well as a single and double
275 precision floating point unit. These capabilities map nicely
276 onto Java's arithmetic instructions.
281 \subsection{Binary-to-Source Compilation}
283 The first incarnation of NestedVM was a binary-to-source compiler.
284 This version reads in a MIPS binary and emits Java source code, which
285 can be compiled with {\tt javac}, {\tt jikes}, or {\tt gcj}.
287 This implementation was primarily a first step towards the
288 binary-to-binary compiler. Conveniently, generating Java source code
289 frees NestedVM from having to perform simple constant propagation
290 optimizations, since most Java compilers already do this. A recurring
291 example is the treatment of the {\tt r0} register, which is fixed as
292 {\tt 0} in the MIPS ISA.
294 Lacking the ability to generate specially optimized bytecode
295 sequences, a straightforward mapping of the general purpose hardware
296 registers to 32 {\tt int} fields was optimal.
299 \begin{minipage}[c]{7in}%
301 {\footnotesize\begin{verbatim}
302 private final static int r0 = 0;
303 private int r1, r2, r3,...,r30;
304 private int r31 = 0xdeadbeef;
305 private int pc = ENTRY_POINT;
334 System.err.println(``Exited.'');
341 {\footnotesize\begin{verbatim}
342 public void run_0x10000() {
359 pubic void run_0x10200() {
370 public void trampoline() {
372 switch(pc&0xfffffe00) {
373 case 0x10000: run_0x10000(); break;
374 case 0x10200: run_0x10200(); break;
383 \caption{\label{code1} Trampoline transformation necessitated by Java's 64kb method size limit}
386 Unfortunately, Java imposes a 64kb limit on the size of the bytecode
387 for a single method. This presents a problem for NestedVM, and
388 necessitates a {\it trampoline transformation}, as shown in
389 Figure~\ref{code1}. With this trampoline in place somewhat large
390 binaries can be handled without much difficulty -- fortunately, there
391 is no corresponding limit on the size of a classfile as a whole.
393 Another interesting problem that was discovered while creating the
394 trampoline method was javac and Jikes' inability to properly optimize
395 switch statements. The code in Figure~\ref{lookupswitch} is compiled
396 into a comparatively inefficient {\tt LOOKUPSWITCH}, while the code in
397 Figure~\ref{tableswitch} is optimized into a {\tt TABLESWITCH}.
400 {\footnotesize\begin{verbatim}
401 switch(pc&0xffffff00) {
402 case 0x00000100: run_100(); break;
403 case 0x00000200: run_200(); break;
404 case 0x00000300: run_300(); break;
407 \caption{\label{lookupswitch} Code which {\it is not} optimized into a tableswitch}
411 {\footnotesize\begin{verbatim}
413 case 0x1: run_100(); break;
414 case 0x2: run_200(); break;
415 case 0x3: run_300(); break;
418 \caption{\label{tableswitch} Code which {\it is} optimized into a tableswitch}
421 Javac is not smart enough to see the pattern in the case values and
422 generates very suboptimal bytecode. Manually doing the shifts
423 convinces javac to emit a tableswitch statement, which is
424 significantly faster. This change alone increased the speed of
425 the compiled binary by approximately 35\%.
427 Finding the optimal method size lead to the next big performance
428 increase. It was determined through experimentation that the optimal
429 number of MIPS instructions per method is 64 or 128 (considering only
430 powers of two). Going above or below that lead to performance
431 decreases. This is most likely due to a combination of two factors.
435 \item The two levels of switch statements jumps have to pass though -
436 The first switch statement jumps go through is the trampoline
437 switch statement. This is implemented as a {\tt TABLESWITCH} in JVM
438 bytecode so it is very fast. The second level switch statement
439 in the individual run\_ methods is implemented as a
440 {\tt LOOKUPSWITCH}, which is much slower. Using smaller methods puts
441 more burden on the faster {\tt TABLESWITCH} and less on the slower
444 \item JIT compilers probably favor smaller methods smaller methods are
445 easier to compile and are probably better candidates for JIT
446 compilation than larger methods.
452 Putting more than 256 instructions in each method lead to a severe
453 performance penalty. Apparently Hotspot does not handle very large methods
454 well. In some tests the simple moving from 256 to 512 instructions per
455 method decreased performance by a factor of 10.
459 The next big optimization was eliminating unnecessary case
460 statements. Having case statements before each instruction prevents
461 JIT compilers from being able to optimize across instruction
462 boundaries. In order to eliminate unnecessary case statements every
463 possible address that could be jumped to directly needed to be
464 identified. The sources for possible jump targets come from 3 places.
468 \item The .text segment - Every instruction in the text segment is
469 scanned for jump targets. Every branch instruction (BEQ, JAL,
470 etc) has its destination added to the list of possible branch
471 targets. In addition, functions that set the link register have
472 theirpc+8 added to the list (the address that would have been put
473 to the link register). Finally, combinations of LUI (Load Upper
474 Immediate) of ADDIU (Add Immediate Unsigned) are scanned for
475 possible addresses in the text segment. This combination of
476 instructions is often used to load a 32-bit word into a
479 \item The .data segment - When GCC generates switch() statements it
480 often uses a jump table stored in the .data
481 segment. Unfortunately gcc does not identify these jump tables in
482 any way. Therefore, the entire .data segment is conservatively
483 scanned for possible addresses in the .text segment.
485 \item The symbol table - This is mainly used as a backup. Scanning the
486 .text and .data segments should identify any possible jump
487 targets but adding every function in the symbol table in the ELF
488 binary does not hurt. This will also catch functions that are
489 never called directly from the MIPS binary (for example,
490 functions called with the call() method in the runtime).
494 Eliminating unnecessary case statements provided a 10-25\% speed
497 Despite all the above optimizations and workarounds an impossible to
498 workaround hard classfile limit was eventually hit, the constant
499 pool. The constant pool in classfiles is limited to 65536
500 entries. Every integer with a magnitude greater than 32767 requires an
501 entry in the constant pool. Every time the compiler emits a
502 jump or branch instruction the PC field is set to the branch target. This
503 means nearly every branch instruction requires an entry in the
504 constant pool. Large binaries hit this limit fairly quickly. One
505 workaround that was employed in the Java source compiler was to
506 express constants as offsets from a few central values. For example:
507 ``pc = N\_0x00010000 + 0x10'' where N\_0x000100000 is a non-final
508 field to prevent javac from inlining it. This was sufficient to get
509 reasonable large binaries to compile. It has a small (approximately
510 5\%) performance impact on the generated code. It also makes the
511 generated classfile somewhat larger. Fortunately, the classfile
512 compiler eliminates this problem.
515 \subsection{Binary-to-Binary Translation}
517 The next step in the evolution of NestedVM was to compile directly to
518 JVM bytecode eliminating the intermediate javac step. This had several
523 \item There are little tricks that can be done in JVM bytecode that
524 cannot be done in Java source code.
526 \item Eliminates the time-consuming javac step - Javac takes a long
527 time to parse and compile the output from the java source
530 \item Allows for MIPS binaries to be compiled and loaded into a
531 running VM using a class loader. This eliminates the need to
532 compile the binaries ahead of time.
536 By generating code at the bytecode level there are many areas where
537 the compiler can be smarter than javac. Most of the areas where
538 improvements where made where in the handling of branch instructions
539 and in taking advantage of the JVM stack to eliminate unnecessary
540 LOADs and STOREs to local variables.
542 The first obvious optimization that generating bytecode allows for is the
543 use of GOTO. Despite the fact that Java does not have a GOTO keyword a GOTO
544 bytecode does exist and is used heavily in the code generates by javac.
545 Unfortunately the java language does not provide any way to take advantage of
546 this. As result of this, jumps within a method were implemented in the
547 binary-to-source compiler by setting the PC field to the new address and
548 making a trip back to the initial switch statement. In the classfile
549 compiler these jumps are implemented as GOTOs directly to the target
550 instruction. This saves a costly trip back through the LOOKUPSWITCH
551 statement and is a huge win for small loops within a method.
553 Somewhat related to using GOTO is the ability to optimize branch
554 statements. In the Java source compiler branch statements are
555 implemented as follows (delay slots are ignored for the purpose of
558 {\footnotesize\begin{verbatim}
559 if(condition) { pc = TARGET; continue; }
562 This requires a branch in the JVM regardless of whether the MIPS
563 branch is actually taken. If condition is false the JVM has to jump
564 over the code to set the PC and go back to the switch block. If
565 condition is true the JVM has to jump to the switch block. By
566 generating bytecode directly we can make the target of the JVM branch
567 statement the actual bytecode of the final destination. In the case
568 where the branch is not taken the JVM does not need to branch at all.
570 A side affect of the above two optimizations is a solution to the
571 excess constant pool entries problem. When jumps are implemented as
572 GOTOs and direct branches to the target the PC field does not need to
573 be set. This eliminates many of the constant pool entries the java
574 source compiler requires. The limit is still there however, and given
575 a large enough binary it will still be reached.
577 Delay slots are another area where things are done somewhat
578 inefficiently in the Java source compiler. In order to take advantage
579 of instructions already in the pipeline MIPS cpu have a ``delay
580 slot''. That is, an instruction after a branch or jump instruction that
581 is executed regardless of whether the branch is taken. This is done
582 because by the time the branch or jump instruction is finished being
583 processes the next instruction is already ready to be executed and it
584 is wasteful to discard it. (However, newer MIPS CPUs have pipelines
585 that are much larger than early MIPS CPUs so they have to discard many
586 instructions anyway.) As a result of this the instruction in the delay
587 slot is actually executed BEFORE the branch is taken. To make things
588 even more difficult, values from the register file are loaded BEFORE
589 the delay slot is executed. Here is a small piece of MIPS assembly:
591 {\footnotesize\begin{verbatim}
599 This piece of code is executed as follows
603 \item r2 is set to -1
605 \item r2 is loaded from the register file by the BLTEZ instruction
607 \item 10 is added to r2 by the ADDIU instruction
609 \item The branch is taken because at the time the BLTZ instruction was
610 executed r2 was -1, but r2 is now 9 (-1 + 10)
614 There is a very elegent solution to this problem when using JVM
615 bytecode. When a branch instruction is encountered the registers
616 needed for the comparison are pushed onto the stack to prepare for the
617 JVM branch instruction. Then, AFTER the values are on the stack the
618 delay slot is emitted, and then finally the actual JVM branch
619 instruction. Because the values were pushed to the stack before the
620 delay slot was executed any changes the delay slot made to the
621 registers are not visible to the branch bytecode. This allows delay
622 slots to be used with no performance penalty or size penalty.
624 One final advantage that generating bytecode directly allows is
625 smaller more compact bytecode. All the optimizations above lead to
626 smaller bytecode as a side effect. There are also a few other areas
627 where the generated bytecode can be optimized for size with more
628 knowledge of the program as a whole.
630 When encountering the following switch block both javac and Jikes
631 generate redundant bytecode.
633 {\footnotesize\begin{verbatim}
635 case 0x1: run_1(); break;
636 case 0x2: run_2(); break
638 case 0x100: run_100(); break;
642 The first bytecode in each case arm in the switch statement is ALOAD\_0 to
643 prepare for a invoke special call. By simple moving this outside the switch
644 statement each case arm was reduced in size by one instruction. Similar
645 optimizations were also done in other parts of the compiler.
647 \section{Interfacing with Java Code}
649 NestedVM has two primary ways of executing code, the interpreter, and the
650 binary translators. Both the interpreter and the output from the binary
651 translators sit on top of a Runtime class. This class provides the public
652 interface to both the interpreter and the translated binaries.
654 \subsection{The Runtime Class}
656 The Runtime class does the work that the operating system usually does.
657 Conceptually the Runtime class can be thought of as the operating system and
658 its subclasses (translated binaries and the interpreter) the CPU. The
659 Runtime fulfills 5 primary goals:
663 \item Provides a consistent external interface - The method of actually
664 executing the code (currently only translated binaries and the interpreter)
665 can be changed without any code changes to the caller because only Runtime
666 exposes a public interface.
668 \item Provide an easy to use interface - The interpreter and the output from
669 the binary translators only know how to execute code. The Runtime class
670 provides an easy to use interface to the code. It contains methods to pass
671 arguments to the main() function, read and write from memory, and call
672 individual functions in the binary.
674 \item Manage the process's memory - The Runtime class contains large int[]
675 arrays that represent the process`s entire memory space. Subclasses read
676 and write to these arrays as required by the instructions they are
677 executing. Subclasses can expend their memory space using the sbrk
680 \item Provide access to the file system and streams - Subclasses access the
681 file system through standard UNIX syscalls (read, write, open, etc). The
682 Runtime manages the file descriptor table that maps UNIX file descriptors
683 to Java RandomAccessFiles, InputStreams, OutputStreams, and sockets.
685 \item Miscellaneous other syscalls - In additions to those mentioned above
686 the Runtime class implements a variety of other syscalls (sleep,
687 gettimeofday, getpagesize, sysconf, fcntl, etc).
691 \subsection{Interacting with the Binary}
693 Java source code can create a copy of the translated binary by instantiating
694 the class generated by the binary translator or instantiating the
695 interpreter. It can then interact with the process through the many
696 facilities provided by the Runtime interface. Invoking the run() method of
697 the Runtime interface will load the given arguments into the process's
698 memory as invoke the binaries entry point (typically \_start() in crt0.o).
699 This will pass control on to the main() function which will have the
700 arguments passed to run() loaded into argv and argc.
702 As the binary executes it often passes control back to the Runtime class
703 through the MIPS {\tt SYSCALL} instruction. The interpreter and translated
704 binaries invoke the {\tt syscall()} method of the Runtime class when the
705 {\tt SYSCALL} instruction is executed. The Runtime class then can manipulate
706 the process's environment (read and write to memory, modify the file
707 descriptor table, etc) and interact with the rest of the JVM on behalf of
708 the process (read and write to a file or stream, etc). There is even a
709 syscall to pause the VM and temporarily return control to the caller.
711 In addition to the interfaces provided by NestedVM, users can create their
712 own interfaces between the MIPS and Java world. The Runtime provides a
713 method called call() that will call a function by name in the MIPS binary.
714 The call() method looks up the function name in the binary's ELF symbol
715 table and manipulating the stack and registers accordingly to execute the
716 given function. This allows Java code to seamlessly invoke functions in the
719 {\footnotesize\begin{verbatim}
721 private Runtime rt = new MyBinary();
722 public void foo(int n) {
723 for(int i=0;i<10;i++) {
724 int result = rt.call("do_work",i);
725 System.err.println("do_work(i) = " + result);
729 void do_work(int n) {
732 for(i=0;i<n;i++) ret += i;
737 The MIPS binaries can also invoke a special method of Runtime called
738 callJava().When the MIPS binary invokes the {\tt CALL\_JAVA} syscall
739 (usually done through the {\tt \_call\_java()} function provided by the
740 NestedVM support library) the callJava() method in Runtime is invoked with
741 the arguments passes to the syscall.
743 {\footnotesize\begin{verbatim}
745 private Runtime rt = new MyBinary() {
746 pubilc int callJava(int a, int b, int c, int d) { System.err.println("Got " + a + " " + b);
748 public void foo() { rt.run(); }
750 void main(int argc, char **argv) {
755 These two methods can even be combined. MIPS can call Java through the
756 CALL\_JAVA syscall, which can in turn invoke a MIPS function in the binary
757 with the call() method.
759 Users preferring a simpler communication mechanism can also use Java
760 Stream's and file descriptors. Runtime provides a simple interface for
761 mapping a Java Input or OutputStream to a File Descriptor.
763 %Java source code can create a copy of the translated binary by
764 %instantiating the corresponding class, which extends {\tt Runtime}.
765 %Invoking the {\tt main()} method on this class is equivalent to
766 %calling the {\tt main()} function within the binary; the {\tt String}
767 %arguments to this function are copied into the binary's memory space
768 %and made available as {\tt **argv} and {\tt argc}.
770 %The translated binary communicates with the rest of the VM by
771 %executing MIPS {\tt SYSCALL} instructions, which are translated into
772 %invocations of the {\tt syscall()} method. This calls back to the
773 %native Java world, which can manipulate the binary's environment by
774 %reading and writing to its memory space, checking its exit status,
775 %pausing the VM, and restarting the VM.
778 %\subsection{Virtualization}
780 %The {\tt Runtime} class implements the majority of the standard {\tt
781 %libc} syscalls, providing a complete interface to the filesystem,
782 %network socket library, time of day, (Brian: what else goes here?).
786 %\item ability to provide the same interface to CNI code and
789 %\item security advantages (chroot the {\tt fork()}ed process)
794 \section{Quantitative Performance}
798 (Note that none of these libraries have pure-Java equivalents.)
807 \subsection{Optimizations}
809 Although NestedVM perfectly emulates a MIPS R2000 CPU its performance
810 characteristics are not anything like an actual MIPS R2000 CPU. GCC makes
811 several optimizations that increase performance on an actually MIPS CPU but
812 actually decrease performance when run through the NestedVM binary
813 translator. Fortunately, GCC provides many options to customize its code
814 generations and eliminate these optimizations. GCC also has optimization
815 options that are not helpful on a real MIPS CPU but are very helpful under
818 Adam, we should cite "Using the GNU Compiler Collection" somewhere in here.
822 \item {\tt -falign-functions}
823 Normally a function's location in memory has no effect on its execution
824 speed. However, in the NestedVM binary translator, the .text segment is
825 split up on power of two boundaries. If a function is unlucky enough to
826 start near the end of one of these boundaries a performance critical part of
827 the function could end up spanning two methods. There is a significant
828 amount of overhead in switching between two methods so this must be avoided
829 at all costs. By telling GCC to align all functions to the boundary that the
830 .text segment is split on the chances of a critical part of a function
831 spanning two methods is significantly reduced.
833 \item {\tt -fno-rename-registers}
834 Some processors can better schedule code when registers are not reused for
835 two different purposes. By default GCC will try to use as many registers as
836 possibly when it can. This excess use of registers just confuses JIT's
837 trying to compile the output from the binary translator. All the JIT
838 compilers we tested do much better with a few frequently used registers.
840 \item {\tt -fno-delayed-branch}
841 The MIPS CPU has a delay slot (see above). Earlier versions of NestedVM did
842 not efficiently emulate delay slots. This option causes GCC to avoid using
843 delay slots for anything (a NOP is simply placed in the delay slot). This
844 had a small performance benefit. However, recent versions of NestedVM
845 emulate delay slots with no performance overhead so this options has little
846 effect. Nonetheless, these delay slots provide no benefit under NestedVM
847 either so they are avoided with this option.
849 \item {\tt -fno-schedule-insns}
850 Load operations in the MIPS ISA also have a delay slot. The results of a
851 load operation are not available for use until one instruction later.
852 Several other instructions also have similar delay slots. GCC tries to do
853 useful work wile waiting for the results of one of these operations by
854 default. However, this, like register renaming, tends to confuse JIT
855 compilers. This option prevents GCC from going out of its way to take
856 advantage of these delay slots and makes the code generated by NestedVM
857 easier for JIT compilers to handle.
860 GCC sometimes has to copy somewhat large areas of memory. The most common
861 example of this is assigning one struct to another. Memory copying can be
862 done far more efficiently in Java than under NestedVM. Calls to the memcpy
863 libc function are treated specially by the binary translator. They are
864 turned into calls to a memcpy method in Runtime. The {\tt -mmemcpy} option
865 causes GCC to invoke libc's memcpy() function when it needs to copy a region
866 of memory rather than generating its own memcpy code. This call in then
867 turned into a call to this Java memcpy function which is significantly
868 faster than the MIPS implementation.
870 \item {\tt -ffunction-sections -fdata-sections}
871 These two options are used in conjunction with the {\tt --gc-section} linker
872 option. These three options cause the linker to aggressively discard unused
873 functions and data sections. In some cases this leads to significantly
876 %\item {\tt trampoline}
877 %\item {\tt optimal method size}
878 %\item {\tt -msingle-float}
879 %\item {\tt -mmemcpy}
881 %\item {\tt local vars for registers (useless)}
882 %\item {\tt -fno-rename-registers}
883 %\item {\tt -ffast-math}
884 %\item {\tt -fno-trapping-math}
885 %\item {\tt -fsingle-precision-constant}
886 %\item {\tt -mfused-madd}
887 %\item {\tt -freg-struct-return}
888 %\item {\tt -freduce-all-givs}
889 %\item {\tt -fno-peephole}
890 %\item {\tt -fno-peephole2}
891 %\item {\tt -fmove-all-movables}
892 %\item {\tt -fno-sched-spec-load}
893 %\item {\tt -fno-sched-spec}
894 %\item {\tt -fno-schedule-insns}
895 %\item {\tt -fno-schedule-insns2}
896 %\item {\tt -fno-delayed-branch}
897 %\item {\tt -fno-function-cse}
898 %\item {\tt -ffunction-sections}
899 %\item {\tt -fdata-sections}
900 %\item {\tt array bounds checking}
901 %\item {\tt -falign-functions=n}
902 %\item {\tt -falign-labels=n}
903 %\item {\tt -falign-loops=n}
904 %\item {\tt -falign-jumps=n}
905 %\item {\tt -fno-function-cse}
908 \section{Future Directions}
912 \item Better use of local variables in binary-to-binary compiler -- need to
913 do data flow analysis to find how how and when registers are used and avoid
914 the costly load/restore when it isn't necessary.
916 \item More advanced Runtime support -- support more syscalls. This will
917 allow running large applications such as GCC under NestedVM.
919 \item World domination
925 We rock the hizzouse.
933 {\footnotesize\begin{verbatim}
935 libjpeg (render thebride_1280.jpg)
940 freetype (rendering characters 32-127 of Comic.TTF at sizes from 8 to
941 48 incrementing by 4)
946 libjpeg libmspack libfreetype
947 Interpreted MIPS Binary 22.2 12.9 21.4
948 Compled MIPS Binary (fastest options) 3.39 2.23 4.31
949 Native -O3 0.235 0.084 0.201
951 Compled - with all case statements 3.50 2.30 4.99
952 Compiled - with pruned case statement 3.39 2.23 4.31
954 Compiled - 512 instructions/method 62.7 27.7 56.9
955 Compiled - 256 instructions/method 3.54 2.55 4.43
956 Compiled - 128 instructions/method 3.39 2.23 4.31
957 Compiled - 64 instructions/method 3.56 2.31 4.40
958 Compiled - 32 instruction/method 3.71 2.46 4.64
960 Compild MIPS Binary (Server VM) 3.21 2.00 4.54
961 Compiled MIPS Binary (Client VM) 3.39 2.23 4.31
963 All times are measured in seconds. These were all run on a dual 1ghz G4
964 running OS X 10.3.1 with Apple's latest VM (JDK 1.4.1_01-27). Each test
965 was run 8 times within a single VM. The highest and lowest times were
966 removed and the remaining 6 were averaged. In each case only the first
967 run differed significantly from the rest.
969 The libjpeg test consisted of decoding a 1280x1024 jpeg
970 (thebride_1280.jpg) and writing a tga. The mspack test consisted of
971 extracting all members from arial32.exe, comic32.exe, times32.exe, and
972 verdan32.exe. The freetype test consisted of rendering characters
973 32-127 of Comic.TTF at sizes from 8 to 48 incrementing by 4. (That is
974 about 950 individual glyphs).
976 I can provide you with the source for any of these test if you'd like.