--- /dev/null
+\documentclass{acmconf}
+\usepackage{graphicx}
+\usepackage{multicol}
+\usepackage{amssymb,amsmath,epsfig,alltt}
+\sloppy
+\usepackage{palatino}
+\usepackage{pdftricks}
+\begin{psinputs}
+ \usepackage{pstricks}
+ \usepackage{pst-node}
+\end{psinputs}
+\usepackage{parskip}
+\usepackage{tabularx}
+\usepackage{alltt}
+\bibliographystyle{amsplain}
+
+\title{\textbf{\textsf{
+Complete Translation of Unsafe Native Code to Safe Bytecode
+}}}
+\date{}
+\author{\begin{tabular}{@{}c@{}}
+ {\em {Brian Alliet}} \\
+ {Rochester Institute of Technology}\\
+ {\tt bja8464@cs.rit.edu}
+ \end{tabular}\hskip 1in\begin{tabular}{@{}c@{}}
+ {\em {Adam Megacz}} \\
+ {University of California, Berkeley} \\
+ {\tt megacz@cs.berkeley.edu}
+\end{tabular}}
+\begin{document}
+
+\maketitle
+
+{\it This document was typeset using D. E. Knuth's original \TeX 89
+ Pascal source code, which was both compiled and executed entirely
+ within a Java Virtual Machine. No native code was utilized.}
+
+\begin{abstract}
+
+Most existing techniques for using code written in an unsafe language
+within a safe virtual machine involve transformations from one source
+code language (such as C, Pascal, or Fortran) to another (such as
+Java) and then to virtual machine bytecodes. We present an
+alternative approach which can translate MIPS binaries produced by any
+compiler into safe virtual machine bytecodes. This approach offers
+four key advantages over existing techniques:
+
+\begin{itemize}
+\item Language-agnostic
+\item Bug-for-bug compiler compatability
+\item No post-translation human intervention
+\item No build process modifications
+\end{itemize}
+
+We also present NestedVM, a complete implementation of this technique,
+which we have used to translate a number of programs. Six examples
+are discussed in this paper: LINPACK (Fortran source), which was used
+as one of our performance tests, \TeX (Pascal source), which was used
+to typeset this document, {\tt libjpeg}, {\tt libmspack}, and FreeType
+(all C source), which are currently in production use as part of the
+Ibex Project, and {\tt gcc}, which was used to compile all of the
+aforementioned.
+
+Performance measurements indicate a best case performance within 3x of
+native code and worst case typically within 10x, making it an
+attractive solution for code which is not performance-critical.
+
+\end{abstract}
+
+\section{Introduction}
+
+Unsafe languages such as C \cite{KR} and C++ \cite{soustroup} have
+been in use much longer than any of today's widely accepted safe
+languages such as Java \cite{java} and C\# \cite{csharp}. Consequently, there is
+a huge library of software written in these languages. Although safe
+languages offer substantial benefits, their comparatively young age
+often puts them at a disadvantage when breadth of existing support
+code is an important criterion.
+
+The typical solution to this dilemma is to use a native interface such
+as JNI \cite{jni} or CNI \cite{cni} to invoke unsafe code from within a
+virtual machine or otherwise safe environment. Unfortunately, there
+are a number of situations in which this is not an acceptable
+solution. These situations can be broadly classified into two
+categories: {\it security concerns} and {\it portability concerns}.
+
+Using Java as an example, JNI and CNI are prohibited in a number of
+contexts, including applets environments and servlet containers with a
+{\tt SecurityManager}. Additionally, even in the context of trusted
+code, {\tt native} methods invoked via JNI are susceptible to buffer
+overflow and heap corruption attacks which are not a concern for
+verified bytecode.
+
+The second class of disadvantages revolves around portability
+concerns; native interfaces require the native library to be compiled
+ahead of time, for every architecture on which they will be
+deployed. This is unworkable for situations in which the full set of
+target architectures is not known at deployment time. Additionally,
+some JVM platform variants such as J2ME \cite{j2me} simply do not offer
+support for native code.
+
+The technique we present here uses typical compiler to compile unsafe
+code into a MIPS binary, which is then translated on an
+instruction-by-instruction basis into Java bytecode. The technique
+presented here is general; we anticipate that it can be applied to
+other secure virtual machines such as Microsoft's .NET \cite{msil}, Perl
+Parrot \cite{parrot}, or Python bytecode \cite{python}.
+
+\section{Approaches to Translation}
+
+The four program representations of interest in this context, along
+with their specific types in the C-to-JVM instantiation of the
+problem are shown in the following diagram:
+
+\begin{pdfpic}
+\newlength{\MyLength}
+\settowidth{\MyLength}{machine code}
+\newcommand{\MyBox}[1]{\makebox[\MyLength][c]{#1}}
+\begin{psmatrix}[colsep=2,rowsep=0]
+ & \\[0pt]
+ [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
+ [name=s00]\MyBox{\tt (.c)} & [name=s11]\MyBox{\tt (.java)} \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\[0pt]
+ [name=b00]\MyBox{\tt (.o)} & [name=b11]\MyBox{\tt (.class)} \\
+ & \\[0pt]
+ \psset{nodesep=5pt,arrows=->}
+\end{psmatrix}
+\end{pdfpic}
+
+To illustrate the context of this diagram, the following arcs show the
+translations performed by a few familiar tools:
+
+\begin{pdfpic}
+\newlength{\MyLength}
+\settowidth{\MyLength}{xmachine codex}
+\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
+\psmatrix[colsep=2,rowsep=0,nrot=:D]
+ & \\[0pt]
+ [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\[0pt]
+ & \\[0pt]
+ \psset{nodesep=5pt,arrows=->}
+ \ncline{s0}{b0}\bput{:U}{\tt gcc}
+ \ncline{s1}{b0}\bput{:D}{\tt gcj}
+ \ncline{s1}{b1}\aput{:U}{\tt javac}
+ \ncline{b1}{b0}\aput{:D}{\tt gcj}\bput{:D}{JITs}
+\endpsmatrix
+\end{pdfpic}
+
+Techniques for translating unsafe code into VM bytecode generally fall
+into four categories, which we expand upon in the next two sections:
+
+\begin{itemize}
+\item source-to-source translation
+\item source-to-binary translation
+\item binary-to-source translation
+\item binary-to-binary translation
+\end{itemize}
+
+\section{Existing Work}
+
+\subsection{Source-to-Source Translation}
+
+The most common technique employed is partial translation from unsafe
+source code to safe source code:
+
+\begin{pdfpic}
+\newlength{\MyLength}
+\settowidth{\MyLength}{xmachine codex}
+\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
+\psmatrix[colsep=2,rowsep=0,nrot=:U]
+ & \\[0pt]
+ & \\[0pt]
+ [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\[0pt]
+ & \\[0pt]
+ \psset{nodesep=5pt,arrows=->}
+ \ncline{s0}{s1}\aput{:U}{source-to}\bput{:U}{source}
+ \ncline{s1}{b1}\aput{:U}{\tt javac}
+\endpsmatrix
+\end{pdfpic}
+
+A number of existing systems employ this technique; they can
+be divided into two categories: those which perform a partial
+translation which is completed by a human, and those which perform a
+total translation but fail (yield an error) on a large class of input
+programs.
+
+
+\subsubsection{Incomplete Translation}
+
+Jazillian \cite{jazillian} is a commercial solution which produces
+extremely readable Java source code from C source code, but ony
+translates a small portion of the C language. Jazillian is unique in
+that in addition to {\it language migration}, it also performs {\it
+API migration}; for example, Jazillian is intelligent enough
+to translate {\tt char*~s1~=~strcpy(s2)} into {\tt String~s1~=~s2}.
+
+Unfortunately such deep analysis is intractible for most of the C
+language and standard library; Jazillian's documentation notes that
+{\it ``This is not your father's language translator. It's not
+generating ugly code that's guaranteed to work out of the
+box... Jazillian does not always produce code that works correctly.''}
+
+MoHCA-Java \cite{mohca} is the other major tool in this category, and steps
+beyond Jazillian by providing tools for analysis of the source C++
+abstract syntax tree. Additionally, MoHCA-Java's analysis engine is
+extensible, making it a platform for constructing application-specific
+translators rather than a single translation tool. However,
+MoHCA-Java does not always generate complete Java code for all of the C++
+programs which it accepts.
+
+
+\subsubsection{Partial Domain Translation}
+
+The c2j \cite{c2j}, c2j++ \cite{c2jpp}, Cappucinno \cite{capp},
+and Ephedra \cite{ephedra} systems each provide support for complete
+translation of a {\it subset} of the source language (C or C++). Each
+of the four tools supports a progressively greater subset than the one
+preceding it; however none covers the entire input language.
+
+Ephedra, the most advanced of the four, supports most of the C++
+language, and claims to produce ``human readable'' Java code as
+output. Notable omissions from the input domain include support for
+fully general pointer arithmetic, casting between unrelated types, and
+reading from a {\tt union} via a different member than the one most
+recently written.
+
+Unfortunately, when the program being translated is large and complex,
+it is quite likely that it will use an unsupported feature in at least
+one place. In the absence of a programmer who understands the source
+program, a single anomoly is often enough to render the entire
+translation process useless. As a result, these tools are mainly
+useful as an {\it aid} to programmers who could normally perform the
+conversion themselves, but want to save time by automating most of the
+process.
+
+
+\subsection{Source-to-Binary Translation}
+
+Source-to-binary translation involves a compiler for the unsafe
+language which has been modified to emit safe bytecode.
+
+\begin{pdfpic}
+\newlength{\MyLength}
+\settowidth{\MyLength}{xmachine codex}
+\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
+\psmatrix[colsep=2,rowsep=0,nrot=:U]
+ & \\[0pt]
+ [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\[0pt]
+ & \\[0pt]
+ \psset{nodesep=5pt,arrows=->}
+ \ncline{s0}{b1}\bput{:U}{source-to-binary}
+\endpsmatrix
+\end{pdfpic}
+
+The primary occupant of this category is {\tt egcs-jvm}
+\cite{egcsjvm}, an experimental ``JVM backend'' for the GNU Compiler
+Collection ( {\tt gcc} ) \cite{gcc}. Since {\tt gcc} employs a highlym
+odular architecture, it {\it is} possible to add RTL code generators
+for nonstandard processors. However, {\tt gcc}'s parsing, RTL
+generation, and optimization layers make fundamental assumptions (such
+as the availability of pointer math) which cannot be directly
+supported; thus the compiler still fails for a substantial class of
+input programs.
+
+
+
+\section{NestedVM}
+
+The principal difference between NestedVM and other approaches is that
+NestedVM {\it does not} attempt to deal with source code as an input.
+This leads immediately to three advantages:
+
+\begin{itemize}
+\item {\bf Total coverage of all language features}
+
+ Because NestedVM does not attempt to implement the parsing and
+ code generation steps of compilation, it is freed from the
+ extremely complex task of faithfully implementing languages
+ which are often not fully or formally specified (such as C and
+ C++).
+
+\item {\bf No build process modifications}
+
+ NestedVM does not modify existing build processes, which can be
+ extremely complex and dependent on strange preprocessor usage as
+ well as the complex interplay between compiler switches and
+ header file locations.
+
+\item {\bf Bug-for-bug compiler compatability}
+
+ Since NestedVM uses the compiler's {\it output} as its own {\it
+ input}, it ensures that programs which are inadvertently
+ dependent on the vagaries of a particular compiler can still be
+ used.
+
+\end{itemize}
+
+NestedVM's approach carries a fourth benefit as well, arising from its
+totality:
+
+\begin{itemize}
+\item {\bf No post-translation human intervention}
+
+ NestedVM offers total support for all non-privileged
+ instructions, registers, and resources found on a MIPS {\tt
+ R2000} CPU, including the add/multiply unit and floating point
+ coprocessor. As such, it constitutes a total function mapping
+ from the entire domain of (non-kernel-mode) programs onto (a
+ subset of) the semantics of the Java Virtual Machine. This
+ ensures that the translation process is fully automated and
+ always succeeds for valid input binaries.
+\end{itemize}
+
+This is a much more important factor than is obvious at first glance.
+If post-translation human intervention is required, then the {\it
+human becomes part of the build process}. This means that if a third
+party library used in the project needs to be upgraded, {\it a human
+must intervene} in the rebuild process. In addition to slowing the
+process and introducing opportunities for error, this task often
+requires specialized knowledge which becomes tied to the particular
+individual performing this task, rather than being encoded in build
+scripts which persist throughout the lifetime of the project.
+
+\subsection{Why MIPS?}
+
+We chose MIPS as a source format for three reasons: the availability
+of tools to compile legacy code into MIPS binaries, the close
+similarity between the MIPS ISA and the Java Virtual Machine, and the
+relatively high degree of program structure that can be inferred from
+ABI-adherent binaries.
+
+The MIPS architecture has been around for quite some time, and is well
+supported by the GNU Compiler Collection, which is capable of
+compiling C, C++, Java, Fortran, Pascal, and Objective C
+into MIPS binaries.
+
+The MIPS R2000 ISA bears a striking similarity to the Java Virtual
+Machine:
+
+\begin{itemize}
+
+\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. The remaining non-aligned memory load
+ instructions are only rarely emitted by most compilers since
+ they carry a performance penalty on physical MIPS
+ implementations.
+
+\item Unlike its predecessor, the R2000 supports 32-bit by 32-bit
+ multiply and divide instructions as well as a single and double
+ precision floating point unit. These capabilities map nicely
+ onto Java's arithmetic instructions.
+
+\end{itemize}
+
+Finally, the MIPS ISA and ABI convey quite a bit of information about
+program structure. This information can be used for optimization
+purposes:
+
+\begin{itemize}
+
+\item The structure of MIPS branching and jump instructions make it
+ easy to infer the set of likely target instructions.
+
+\item The MIPS ABI specifies particular registers as caller-save and
+ callee-save, as well as designating a register for the return
+ address after a function call. This allows NestedVM to optimize
+ many operations for the common case of ABI-adherent binaries.
+
+\item All MIPS instructions are exactly 32 bits long.
+
+\end{itemize}
+
+
+
+\subsection{Binary-to-Source}
+
+The simplest operational mode for NestedVM is binary-to-source
+translation. In this mode, NestedVM translates MIPS binaries into
+Java source code, which is then fed to a Java compiler in order to
+produce bytecode files:
+
+\begin{pdfpic}
+\newlength{\MyLength}
+\settowidth{\MyLength}{xmachine codex}
+\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
+\psmatrix[colsep=2,rowsep=0,nrot=:U]
+ & \\[0pt]
+ & \\[0pt]
+ [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\[0pt]
+ \psset{nodesep=5pt,arrows=->}
+ \ncline{s0}{b0}\bput{:U}{\tt gcc}
+ \ncline{s1}{b1}\aput{:U}{\tt javac}
+ \ncline{b0}{s1}\naput{\tt NestedVM}
+\endpsmatrix
+\end{pdfpic}
+
+\begin{figure*}[t]
+\begin{minipage}[c]{7in}%
+\begin{multicols}{2}
+{\footnotesize\begin{verbatim}
+private final static int r0 = 0;
+private int r1, r2, r3,...,r30;
+private int r31 = 0xdeadbeef;
+private int pc = ENTRY_POINT;
+
+public void run() {
+ for(;;) {
+ switch(pc) {
+ case 0x10000:
+ r29 = r29 - 32;
+ case 0x10004:
+ r1 = r4 + r5;
+ case 0x10008:
+ if(r1 == r6) {
+ /* delay slot */
+ r1 = r1 + 1;
+ pc = 0x10018:
+ continue;
+ }
+ case 0x1000C:
+ r1 = r1 + 1;
+ case 0x10010:
+ r31 = 0x10018;
+ pc = 0x10210;
+ continue;
+ case 0x10014:
+ /* nop */
+ case 0x10018:
+ pc = r31;
+ continue;
+ ...
+ case 0xdeadbeef:
+ System.err.println(``Exited.'');
+ System.exit(1);
+ }
+ }
+}
+\end{verbatim}}
+\vspace{1in}
+{\footnotesize\begin{verbatim}
+public void run_0x10000() {
+ for(;;) {
+ switch(pc) {
+ case 0x10000:
+ ...
+ case 0x10004:
+ ...
+ ...
+ case 0x10010:
+ r31 = 0x10018;
+ pc = 0x10210;
+ return;
+ ...
+ }
+ }
+}
+
+pubic void run_0x10200() {
+ for(;;) {
+ switch(pc) {
+ case 0x10200:
+ ...
+ case 0x10204:
+ ...
+ }
+ }
+}
+
+public void trampoline() {
+ for(;;) {
+ switch(pc&0xfffffe00) {
+ case 0x10000: run_0x10000(); break;
+ case 0x10200: run_0x10200(); break;
+ case 0xdeadbe00:
+ ...
+ }
+ }
+}
+\end{verbatim}}
+\end{multicols}
+\end{minipage}
+\caption{\label{code1} Trampoline transformation necessitated by Java's 64kb method size limit}
+\end{figure*}
+
+Translating unsafe code for use within a JVM proceeds as follows:
+
+\begin{enumerate}
+
+\item Compile the source code to a statically linked binary, targeting
+ the MIPS R2000 ISA. Typically this will involve linking against
+ {\tt libc}, which translates system requests (such as {\tt
+ open()}, {\tt read()}, or {\tt write()}) into appropriate
+ invocations of the MIPS {\tt SYSCALL} instruction.
+
+\item Invoke {\tt NestedVM} on the statically linked binary.
+
+\item Compile the resulting {\tt .java} code using {\tt jikes}
+ \cite{jikes} or {\tt javac}.
+
+\item From java code, invoke the {\tt run()} method on the generated
+ class. This is equivalent to the {\tt main()} entry point.
+
+\end{enumerate}
+
+\subsubsection{Optimizations}
+
+Generating Java source code instead of bytecode frees NestedVM from
+having to perform simple constant propagation optimizations, as most
+Java compilers already do this. A recurring example is the treatment
+of the {\tt r0} register, which is fixed as {\tt 0} in the MIPS ISA.
+
+Lacking the ability to generate specially optimized bytecode
+sequences, a straightforward mapping of the general purpose hardware
+registers to 32 {\tt int} fields turned out to be optimal.
+
+
+\epsfig{file=charts/chart1,width=3in}
+
+Unfortunately, Java imposes a 64kb limit on the size of the bytecode
+for a single method. This presents a problem for NestedVM, and
+necessitates a {\it trampoline transformation}, as shown in
+Figure~\ref{code1}. With this trampoline in place, large binaries can
+be handled without much difficulty -- fortunately, there is no
+corresponding limit on the size of a classfile as a whole.
+
+One difficulty that arose as a result of using the trampoline
+transformation was the fact that {\tt javac} and {\tt jikes} are
+unable to properly optimize its switch statements. For example, the
+following code is compiled into a comparatively inefficient {\tt
+LOOKUPSWITCH}:
+
+{\footnotesize
+\begin{verbatim}
+ switch(pc&0xffffff00) {
+ case 0x00000100: run_100(); break;
+ case 0x00000200: run_200(); break;
+ case 0x00000300: run_300(); break;
+ }
+\end{verbatim}}
+
+Whereas the next block of code code optimized into a {\tt
+TABLESWITCH}:
+
+{\footnotesize
+\begin{verbatim}
+ switch(pc>>>8) {
+ case 0x1: run_100();
+ case 0x2: run_200();
+ case 0x3: run_300();
+ }
+\end{verbatim}}
+
+This problem was surmounted by switching on a denser set of {\tt case}
+values, which is more amenable to the {\tt TABLESWITCH} structure.
+This change alone nearly doubled the speed of the compiled binary.
+
+The next performance improvement came from tuning the size of the
+methods invoked from the trampoline. Trial and error led to the
+onclusion that HotSpot \cite{hotspot} -- the most widely deployed JVM
+-- performs best when 128 MIPS instructions are mapped to each method.
+
+\epsfig{file=chart5,width=3in}
+
+\epsfig{file=chart6,width=3in}
+
+This phenomenon is due to two factors:
+
+\begin{itemize}
+
+\item While the trampoline method's {\tt switch} statement can be
+ coded as a {\tt TABLESWITCH}, the {\tt switch} statement
+ within the individual methods is to sparse to encode this way.
+
+\item Hybrid Interpretive-JIT compilers such as HotSpot generally
+ favor smaller methods since they are easier to compile and are
+ better candidates for compilation in ``normal'' programs (unlike
+ NestedVM programs).
+
+\end{itemize}
+
+After tuning method sizes, our next performance boost came from
+eliminating exraneous case branches. Having case statements before
+each instruction prevents JIT compilers from being able to optimize
+across instruction boundaries, since control flow can enter the body
+of a {\tt switch} statement at any of the {\tt case}s. In order to
+eliminate unnecessary case statements we needed to identify all
+possible jump targets. Jump targets can come from three sources:
+
+\begin{itemize}
+
+\item {\bf The {\tt .text} segment}
+
+ Every instruction in the text segment is scanned, and every
+ branch instruction's destination is added to the list of
+ possible branch targets. In addition, any function that sets
+ the link register is added to the list \footnote{actually {\tt addr+8}}.
+ Finally, combinations of {\tt LUI} (Load Upper Immediate) and
+ {\tt ADDIU} (Add Immediate Unsigned) are scanned for possible
+ addresses in the {\tt .text} segment since this combination of
+ instructions is often used to load a 32-bit word into a
+ register.
+
+\item {\bf The {\tt .data} segment}
+
+ When compiling {\tt switch} statements, compilers often use a
+ jump table stored in the {\tt .data} segment. Unfortunately
+ they typically do not identify these jump tables in any way.
+ Therefore, the entire {\tt .data} segment is conservatively
+ scanned for possible addresses in the {\tt .text} segment.
+
+\item {\bf The symbol table}
+
+ This is mainly used as a backup. Scanning the {\tt .text} and
+ {\tt .data} segments should identify any possible jump targets;
+ however, adding all function symbols in the ELF symbol table
+ also catches functions that are never called directly from the
+ MIPS binary, such as those invoked only via the NestedVM
+ runtime's {\tt call()} method.
+
+\end{itemize}
+
+Eliminating unnecessary {\tt case} statements provided a 10-25\% speed
+increase.
+
+Despite all the above optimizations, one insurmountable obstacle
+remained: the Java {\tt .class} file format limits the constant pool
+to 65535 entries. Every integer literal greater than {\tt 32767}
+requires an entry in this pool, and each branch instruction generates
+one of these.
+
+One suboptimal solution was to express constants as offsets from a few
+central values; for example ``{\tt pc~=~N\_0x00010000~+~0x10}'' (where
+{\tt N\_0x000100000} is a non-final field to prevent {\tt javac} from
+inlining it). This was sufficient to get reasonably large binaries to
+compile, and caused only a small (approximately 5\%) performance
+degredation and a similarly small increase in the size of the {\tt
+.class} file. However, as we will see in the next section, compiling
+directly to {\tt .class} files (without the intermediate {\tt .java}
+file) eliminates this problem entirely.
+
+
+\subsection{Binary-to-Binary}
+
+After implementing the binary-to-source compiler, a binary-to-binary
+translation mode was added.
+
+\begin{pdfpic}
+\newlength{\MyLength}
+\settowidth{\MyLength}{xmachine codex}
+\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
+\psmatrix[colsep=2,rowsep=0,nrot=:U]
+ & \\[0pt]
+ [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source} \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ & \\[0pt]
+ [name=b0]\MyBox{machine code} & [name=b1]\MyBox{safe bytecode} \\[0pt]
+ & \\[0pt]
+ \psset{nodesep=5pt,arrows=->}
+ \ncline{s0}{b0}\bput{:U}{\tt gcc}
+ \ncline{b0}{b1}\naput{\tt NestedVM}
+\endpsmatrix
+\end{pdfpic}
+
+This mode has several advantages:
+
+\begin{itemize}
+
+\item There are quite a few interesting bytecode sequences that cannot
+ be generated as a result of compiling Java source code.
+
+\item Directly generating {\tt .class} files Eliminates the
+ time-consuming {\tt javac} step.
+
+\item Direct compilation to {\tt .class} files opens up the
+ interesting possibility of dynamically translating MIPS binaries
+ and loading them via {\tt ClassLoader.fromBytes()} {\it at
+ deployment time}, eliminating the need to compile binaries ahead
+ of time.
+
+\end{itemize}
+
+Most of the performance improvemen where made where in the handling of
+branch instructions and in taking advantage of the JVM stack to
+eliminate unnecessary {\tt LOAD}s and {\tt STORE}s to local variables.
+
+\epsfig{file=chart7,width=3in}
+
+The first optimization gained by direct bytecode generation came from
+the use of the JVM {\tt GOTO} instruction. Despite the fact that the
+Java {\it language} does not have a {\tt goto} keyword, the VM does in
+fact have a corresponding instruction which is used quite heavily by
+{\tt javac}. NestedVM's binary-to-binary mode exploits this
+instruction to avoid emitting inefficient {\tt switch..case}
+structures.
+
+Related to the {\tt GOTO} instruction is branch statement
+optimization. When emitting source code, NestedVM translates branches
+into Java source code like this:
+
+{\footnotesize\begin{verbatim}
+ if (condition) {
+ pc = TARGET;
+ continue;
+ }
+\end{verbatim}}
+
+This requires a branch in the JVM {\it regardless} of whether the MIPS
+branch is actually taken. If {\tt condition} is false the JVM has to
+jump over the code to set {\tt pc} and go back to the {\tt switch}
+statemenmt; if {\tt condition} is true the JVM has to jump to the {\tt
+switch} block. By generating bytecode directly, NestedVM is able to
+emit a JVM bytecode branching directly to the address corresponding to
+the target of the MIPS branch. In the case where the branch is not
+taken the JVM doesn't branch at all.
+
+A side effect of the previous two optimizations is a solution to the
+excess constant pool entries problem. When jumps are implemented as
+{\tt GOTO}s and branches are taken directly, the {\tt pc} field does
+not need to be set. This eliminates a huge number of constant pool
+entries. The {\tt .class} file constant pool size limit is still
+present, but it is less likely to be encountered.
+
+Implementation of the MIPS delay slot offers another opportunity for
+bytecode-level optimization. In order to take advantage of
+instructions already in the pipeline, the MIPS ISA specifies that the
+instruction after a jump or branch is always executed, even if the
+jump/branch is taken. This instruction is referred to as the ``delay
+slot\footnote{Newer MIPS CPUs have pipelines that are much larger than
+early MIPS CPUs, so they have to discard instructions anyways}.'' The
+instruction in the delay slot is actually executed {\it before} the
+branch is taken. To further complicate matters, values from the
+register file are loaded {\it before} the delay slot is executed.
+
+Fortunately there is a very elegent solution to this problem which can
+be expressed in 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, {\it
+after} the values are on the stack the delay slot instruction is
+emitted, followed by the actual JVM branch instruction. Because the
+values were pushed to the stack before the delay slot was executed, any
+changes the delay slot made to the registers are not visible to the
+branch bytecode.
+
+One final advantage that generating bytecode directly allows is a
+reduction in the size of the ultimate {\tt .class} file. All the
+optimizations above lead to more compact bytecode as a beneficial side
+effect; in addition, NestedVM performs a few additional optimizations.
+
+When encountering the following {\tt switch} block, both {\tt javac}
+and {\tt jikes} generate redundant bytecode.
+
+{\footnotesize\begin{verbatim}
+ switch(pc>>>8) {
+ case 0x1: run_1(); break;
+ case 0x2: run_2(); break
+ ...
+ case 0x100: run_100(); break;
+ }
+\end{verbatim}}
+
+The first bytecode in each case arm in the switch statement is {\tt
+ALOAD\_0} to prepare for a {\tt INVOKESPECIAL} call. By simply
+lifting this bytecode outside of the {\tt switch} statement, each {\tt
+case} arm shrinks by one instruction.
+
+\subsubsection{Compiler Flags}
+
+Although NestedVM perfectly emulates a MIPS R2000 CPU, its performance
+profile is nothing like that of actual silicon. In particular, {\tt
+gcc} makes several optimizations that increase performance on an
+actually MIPS CPU but actually decrease the performance of
+NestedVM-generated bytecode. We found the following compiler options
+could be used to improve performance:
+
+\begin{itemize}
+
+\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 {\tt .text} segment is split on power-of-two boundaries. If
+ a function starts near the end of one of these boundaries, a
+ performance critical part of the function winds up spanning two
+ Java methods. Telling {\tt gcc} to align all functions along
+ these boundaries decreases the chance of this sort of splitting.
+
+\item {\tt -fno-rename-registers}
+
+ On an actual silicon chip, using additional registers carries no
+ performance penalty (as long as none are spilled to the stack).
+ However, when generating bytecode, using {\it fewer}
+ ``registers'' helps the JVM optimize the machine code it
+ generates by simplifying the constraints it needs to deal with.
+ Disabling register renaming has this effect.
+
+\item {\tt -fno-schedule-insns}
+
+ Results of MIPS load operations are not available until {\it
+ two} instructions after the load. Without the {\tt
+ -fno-schedule-insns} instruction, {\tt gcc} will attempt to
+ reorder instructions to do other useful work during this period
+ of unavailability. NestedVM is under no such constraint, so
+ removing this reordering typically generates simpler machine
+ code.
+
+\item {\tt -mmemcpy}
+
+ Enabling this instruction causes {\tt gcc} to use the system
+ {\tt memcpy()} routine instead of generating loads and stores.
+ As explained in the next section, the NestedVM runtime
+ implements {\tt memcpy()} using {\tt System.arraycopy()}, which
+ is substantially more efficient.
+
+\item {\tt -ffunction-sections -fdata-sections}
+
+ These two options are used in conjunction with the {\tt
+ --gc-section} linker option, prompting the linker to more
+ aggressively prune dead code.
+
+\end{itemize}
+
+The effects of the various optimizations presented in this chapter are
+summarized in the table below.
+
+\epsfig{file=chart4,width=3in}
+
+\epsfig{file=chart3,width=3in}
+
+\section{The NestedVM Runtime}
+
+In addition to binary-to-source and binary-to-binary translation,
+NestedVM also includes a MIPS binary interpreter. All three
+translation approaches expose the same API to both the translated
+binary and the surrounding VM (including peer Java code).
+
+\subsection{The Runtime Class}
+
+The runtime fulfills four roles:
+
+\begin{itemize}
+
+\item It provides a simple, consistent external interface. The method
+ of actually executing the code (currently only translated
+ binaries and the interpreter) can be changed without any code
+ changes to the caller because only runtime exposes a public
+ interface. This includes methods to pass arguments to the
+ binary's {\tt main()} function, read and write from memory, and
+ call individual functions in the binary.
+
+\item It manages the process's memory. The runtime class contains
+ large {\tt 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, and can expand
+ their memory space using the {\tt sbrk} system call.
+
+\item The runtime provides access to the host file system and standard
+ I/O streams. Subclasses of {\tt runtime} can access the file
+ system through standard UNIX syscalls ({\tt read()}, {\tt
+ write()}, {\tt open()}, etc). The runtime manages the file
+ descriptor table that maps UNIX file descriptors to Java {\tt
+ RandomAccessFile}s, {\tt InputStream}s, {\tt OutputStream}s, and
+ {\tt Socket}s.
+
+\item It provides general OS services, including {\tt sleep()}, {\tt
+ gettimeofday()}, {\tt getpagesize()}, {\tt sysconf()}, {\tt
+ fcntl()}, and so on.
+
+\end{itemize}
+
+\section{Future Directions}
+
+Although we have only implemented it for the Java Virtual Machine, our
+technique generalizes to other safe bytecode architectures. In
+particular we would like to demonstrate this generality by retargeting
+the translator to the Microsoft Intermediate Language \cite{msil}.
+
+Additionally, we would like to explore other uses for dynamic loading
+of translated MIPS binaries by combining NestedVM (which itself is
+written in Java) and the {\tt ClassLoader.fromBytes()} mechanism.
+
+
+\section{Conclusion}
+
+We have presented a novel technique for using libraries written in
+unsafe languages within a safe virtual machine without resorting to
+native interfaces. We have implemented this technique in NestedVM,
+which is currently used by the Ibex project\footnote{{\tt
+http://www.ibex.org}} to perform font rasterization (via {\tt
+libfreetype}), JPEG decoding (via {\tt libjpeg}), and CAB archive
+extraction (via {\tt libmspack}), three libraries for which no
+equivalent Java classes exist.
+
+NestedVM is available under an open source license, and can be
+obtained from
+\begin{verbatim}
+ http://nestedvm.ibex.org
+\end{verbatim}
+
+
+\section{Appendix: Testing Methodology}
+
+All times are measured in seconds. These were all run on a dual 1Ghz
+Macintosh G4 running Apple's latest JVM (Sun HotSpot JDK 1.4.1). Each
+test was run 8 times within a single VM. The highest and lowest times
+were removed and the remaining 6 were averaged. In each case only the
+first run differed significantly from the rest.
+
+The {\tt libjpeg} test consisted of decoding a 1280x1024 jpeg and
+writing a tga. The {\tt mspack} test consisted of extracting all
+members from {\tt arial32.exe}, {\tt comic32.exe}, {\tt times32.exe},
+and {\tt verdan32.exe}. The {\tt libfreetype} test consisted of
+rendering ASCII characters 32-127 of {\tt Comic.TTF} at sizes from 8
+to 48 incrementing by 4 for a total of 950 glyphs.
+
+\bibliography{nestedvm}
+
+\end{document}
+
projects / nestedvm.git / blobdiff