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}
412 Brian, we're missing the code here... can you put it in?
414 \caption{\label{tableswitch} Code which {\it is} optimized into a tableswitch}
417 Javac isn't smart enough to see the pattern in the case values and
418 generates very suboptimal bytecode. Manually doing the shifts
419 convinces javac to emit a tableswitch statement, which is
420 significantly faster. This change alone nearly doubled the speed of
423 Finding the optimal method size lead to the next big performance
424 increase. It was determined through experimentation that the optimal
425 number of MIPS instructions per method is 128 (considering only power
426 of two options). Going above or below that lead to performance
427 decreases. This is most likely due to a combination of two factors.
431 \item The two levels of switch statements jumps have to pass though -
432 The first switch statement jumps go through is the trampoline
433 switch statement. This is implemented as a {\tt TABLESWITCH} in JVM
434 bytecode so it is very fast. The second level switch statement
435 in the individual run\_ methods is implemented as a
436 {\tt LOOKUPSWITCH}, which is much slower. Using smaller methods puts
437 more burden on the faster {\tt TABLESWITCH} and less on the slower
440 \item JIT compilers probably favor smaller methods smaller methods are
441 easier to compile and are probably better candidates for JIT
442 compilation than larger methods.
448 The next big optimization was eliminating unnecessary case
449 statements. Having case statements before each instruction prevents
450 JIT compilers from being able to optimize across instruction
451 boundaries. In order to eliminate unnecessary case statements every
452 possible address that could be jumped to directly needed to be
453 identified. The sources for possible jump targets come from 3 places.
457 \item The .text segment - Every instruction in the text segment is
458 scanned for jump targets. Every branch instruction (BEQ, JAL,
459 etc) has its destination added to the list of possible branch
460 targets. In addition, functions that set the link register have
461 theirpc+8 added to the list (the address that would've been put
462 to the link register). Finally, combinations of LUI (Load Upper
463 Immediate) of ADDIU (Add Immediate Unsigned) are scanned for
464 possible addresses in the text segment. This combination of
465 instructions is often used to load a 32-bit word into a
468 \item The .data segment - When GCC generates switch() statements it
469 often uses a jump table stored in the .data
470 segment. Unfortunately gcc doesn't identify these jump tables in
471 any way. Therefore, the entire .data segment is conservatively
472 scanned for possible addresses in the .text segment.
474 \item The symbol table - This is mainly used as a backup. Scanning the
475 .text and .data segments should identify any possible jump
476 targets but adding every function in the symbol table in the ELF
477 binary doesn't hurt. This will also catch functions that are
478 never called directly from the MIPS binary (for example,
479 functions called with the call() method in the runtime).
483 Eliminating unnecessary case statements provided a 10-25\% speed
486 Despite all the above optimizations and workaround an impossible to
487 workaround hard classfile limit was eventually hit, the constant
488 pool. The constant pool in classfiles is limited to 65536
489 entries. Every Integer with a magnitude greater than 32767 requires an
490 entry in the constant pool. Every time the compiler emits a
491 jump or branch instruction the PC field is set to the branch target. This
492 means nearly every branch instruction requires an entry in the
493 constant pool. Large binaries hit this limit fairly quickly. One
494 workaround that was employed in the Java source compiler was to
495 express constants as offsets from a few central values. For example:
496 ``pc = N\_0x00010000 + 0x10'' where N\_0x000100000 is a non-final
497 field to prevent javac from inlining it. This was sufficient to get
498 reasonable large binaries to compile. It has a small (approximately
499 5\%) performance impact on the generated code. It also makes the
500 generated classfile somewhat larger. Fortunately, the classfile
501 compiler eliminates this problem.
504 \subsection{Binary-to-Binary Translation}
506 The next step in the evolution of NestedVM was to compile directly to
507 JVM bytecode eliminating the intermediate javac step. This had several
512 \item There are little tricks that can be done in JVM bytecode that
513 can't be done in Java source code.
515 \item Eliminates the time-consuming javac step - Javac takes a long
516 time to parse and compile the output from the java source
519 \item Allows for MIPS binaries to be compiled and loaded into a
520 running VM using a class loader. This eliminates the need to
521 compile the binaries ahead of time.
525 By generating code at the bytecode level there are many areas where
526 the compiler can be smarter than javac. Most of the areas where
527 improvements where made where in the handling of branch instructions
528 and in taking advantage of the JVM stack to eliminate unnecessary
529 LOADs and STOREs to local variables.
531 The first obvious optimization that generating bytecode allows for is the
532 use of GOTO. Despite the fact that java doesn't have a GOTO keyword a GOTO
533 bytecode does exist and is used heavily in the code generates by javac.
534 Unfortunately the java language doesn't provide any way to take advantage of
535 this. As result of this, jumps within a method were implemented in the
536 binary-to-source compiler by setting the PC field to the new address and
537 making a trip back to the initial switch statement. In the classfile
538 compiler these jumps are implemented as GOTOs directly to the target
539 instruction. This saves a costly trip back through the LOOKUPSWITCH
540 statement and is a huge win for small loops within a method.
542 Somewhat related to using GOTO is the ability to optimize branch
543 statements. In the Java source compiler branch statements are
544 implemented as follows (delay slots are ignored for the purpose of
547 {\footnotesize\begin{verbatim}
548 if(condition) { pc = TARGET; continue; }
551 This requires a branch in the JVM regardless of whether the MIPS
552 branch is actually taken. If condition is false the JVM has to jump
553 over the code to set the PC and go back to the switch block. If
554 condition is true the JVM as to jump to the switch block. By
555 generating bytecode directly we can make the target of the JVM branch
556 statement the actual bytecode of the final destination. In the case
557 where the branch isn't taken the JVM doesn't need to branch at all.
559 A side affect of the above two optimizations is a solution to the
560 excess constant pool entries problem. When jumps are implemented as
561 GOTOs and direct branches to the target the PC field doesn't need to
562 be set. This eliminates many of the constant pool entries the java
563 source compiler requires. The limit is still there however, and given
564 a large enough binary it will still be reached.
566 Delay slots are another area where things are done somewhat
567 inefficiently in the Java source compiler. In order to take advantage
568 of instructions already in the pipeline MIPS cpu have a ``delay
569 slot''. That is, an instruction after a branch or jump instruction that
570 is executed regardless of whether the branch is taken. This is done
571 because by the time the branch or jump instruction is finished being
572 processes the next instruction is already ready to be executed and it
573 is wasteful to discard it. (However, newer MIPS CPUs have pipelines
574 that are much larger than early MIPS CPUs so they have to discard many
575 instructions anyway.) As a result of this the instruction in the delay
576 slot is actually executed BEFORE the branch is taken. To make things
577 even more difficult, values from the register file are loaded BEFORE
578 the delay slot is executed. Here is a small piece of MIPS assembly:
580 {\footnotesize\begin{verbatim}
588 This piece of code is executed as follows
592 \item r2 is set to -1
594 \item r2 is loaded from the register file by the BLTEZ instruction
596 \item 10 is added to r2 by the ADDIU instruction
598 \item The branch is taken because at the time the BLTZ instruction was
599 executed r2 was -1, but r2 is now 9 (-1 + 10)
603 There is a very elegent solution to this problem when using JVM
604 bytecode. When a branch instruction is encountered the registers
605 needed for the comparison are pushed onto the stack to prepare for the
606 JVM branch instruction. Then, AFTER the values are on the stack the
607 delay slot is emitted, and then finally the actual JVM branch
608 instruction. Because the values were pushed to the stack before the
609 delay slot was executed any changes the delay slot made to the
610 registers are not visible to the branch bytecode. This allows delay
611 slots to be used with no performance penalty or size penalty.
613 One final advantage that generating bytecode directly allows is
614 smaller more compact bytecode. All the optimization above lead to
615 smaller bytecode as a side effect. There are also a few other areas
616 where the generated bytecode can be optimized for size with more
617 knowledge of the program as a whole.
619 When encountering the following switch block both javac and Jikes
620 generate redundant bytecode.
622 {\footnotesize\begin{verbatim}
624 case 0x1: run_1(); break;
625 case 0x2: run_2(); break
627 case 0x100: run_100(); break;
631 The first bytecode in each case arm in the switch statement is ALOAD\_0 to
632 prepare for a invoke special call. By simple moving this outside the switch
633 statement each case arm was reduced in size by one instruction. Similar
634 optimizations were also done in other parts of the compiler.
637 \section{Interfacing with Java Code}
639 Java source code can create a copy of the translated binary by
640 instantiating the corresponding class, which extends {\tt Runtime}.
641 Invoking the {\tt main()} method on this class is equivalent to
642 calling the {\tt main()} function within the binary; the {\tt String}
643 arguments to this function are copied into the binary's memory space
644 and made available as {\tt **argv} and {\tt argc}.
646 The translated binary communicates with the rest of the VM by
647 executing MIPS {\tt SYSCALL} instructions, which are translated into
648 invocations of the {\tt syscall()} method. This calls back to the
649 native Java world, which can manipulate the binary's environment by
650 reading and writing to its memory space, checking its exit status,
651 pausing the VM, and restarting the VM.
654 \subsection{Virtualization}
656 The {\tt Runtime} class implements the majority of the standard {\tt
657 libc} syscalls, providing a complete interface to the filesystem,
658 network socket library, time of day, (Brian: what else goes here?).
662 \item ability to provide the same interface to CNI code and
665 \item security advantages (chroot the {\tt fork()}ed process)
670 \section{Quantitative Performance}
674 (Note that none of these libraries have pure-Java equivalents.)
683 \subsection{Optimizations}
685 Brian, can you write something to go here? Just mention which
686 optimizations helped and which ones hurt.
689 \item {\tt trampoline}
690 \item {\tt optimal method size}
691 \item {\tt -msingle-float}
694 \item {\tt local vars for registers (useless)}
695 \item {\tt -fno-rename-registers}
696 \item {\tt -ffast-math}
697 \item {\tt -fno-trapping-math}
698 \item {\tt -fsingle-precision-constant}
699 \item {\tt -mfused-madd}
700 \item {\tt -freg-struct-return}
701 \item {\tt -freduce-all-givs}
702 \item {\tt -fno-peephole}
703 \item {\tt -fno-peephole2}
704 \item {\tt -fmove-all-movables}
705 \item {\tt -fno-sched-spec-load}
706 \item {\tt -fno-sched-spec}
707 \item {\tt -fno-schedule-insns}
708 \item {\tt -fno-schedule-insns2}
709 \item {\tt -fno-delayed-branch}
710 \item {\tt -fno-function-cse}
711 \item {\tt -ffunction-sections}
712 \item {\tt -fdata-sections}
713 \item {\tt array bounds checking}
714 \item {\tt -falign-functions=n}
715 \item {\tt -falign-labels=n}
716 \item {\tt -falign-loops=n}
717 \item {\tt -falign-jumps=n}
718 \item {\tt -fno-function-cse}
721 \section{Future Directions}
727 We rock the hizzouse.
735 {\footnotesize\begin{verbatim}
737 libjpeg (render thebride_1280.jpg)
742 freetype (rendering characters 32-127 of Comic.TTF at sizes from 8 to
743 48 incrementing by 4)
748 libjpeg libmspack libfreetype
749 Interpreted MIPS Binary 22.2 12.9 21.4
750 Compled MIPS Binary (fastest options) 3.39 2.23 4.31
751 Native -O3 0.235 0.084 0.201
753 Compled - with all case statements 3.50 2.30 4.99
754 Compiled - with pruned case statement 3.39 2.23 4.31
756 Compiled - 512 instructions/method 62.7 27.7 56.9
757 Compiled - 256 instructions/method 3.54 2.55 4.43
758 Compiled - 128 instructions/method 3.39 2.23 4.31
759 Compiled - 64 instructions/method 3.56 2.31 4.40
760 Compiled - 32 instruction/method 3.71 2.46 4.64
762 Compild MIPS Binary (Server VM) 3.21 2.00 4.54
763 Compiled MIPS Binary (Client VM) 3.39 2.23 4.31
765 All times are measured in seconds. These were all run on a dual 1ghz G4
766 running OS X 10.3.1 with Apple's latest VM (JDK 1.4.1_01-27). Each test
767 was run 8 times within a single VM. The highest and lowest times were
768 removed and the remaining 6 were averaged. In each case only the first
769 run differed significantly from the rest.
771 The libjpeg test consisted of decoding a 1280x1024 jpeg
772 (thebride_1280.jpg) and writing a tga. The mspack test consisted of
773 extracting all members from arial32.exe, comic32.exe, times32.exe, and
774 verdan32.exe. The freetype test consisted of rendering characters
775 32-127 of Comic.TTF at sizes from 8 to 48 incrementing by 4. (That is
776 about 950 individual glyphs).
778 I can provide you with the source for any of these test if you'd like.