more xwt -> ibex cleanup

[nestedvm.git] / doc / nestedvm.ivme04.tex

\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{alpha}

\title{\textbf{\textsf{
NestedVM: Total Translation of Native Code into Safe Bytecode
}}}
\date{}
\author{\begin{tabular}{@{}c@{}}
        {\em {Brian Alliet}} \\
        {Rochester Institute of Technology}\\
        {\tt brian@ibex.org}
   \end{tabular}\hskip 1in\begin{tabular}{@{}c@{}}
        {\em {Adam Megacz}} \\
        {UC Berkeley Statistical Computing Facility} \\
        {\tt adam@ibex.org}
\end{tabular}}
\begin{document}

\maketitle

\begin{abstract}

We present a new approach to utilizing unsafe legacy code
within safe virtual machines by compiling to MIPS machine code as an
intermediate language.  This approach carries N key benefits over
existing techniques:

\begin{itemize}
\item total coverage of all language features, unlike source translation
\item no build process modifications
\item no post-translation human intervention
\item efficient bytecode
\end{itemize}

We also present NestedVM, a complete system in production use which
implements this technique.  We conclude with quantitative performance
measurements and suggestions for VM acceleration of the resulting
bytecodes.


\end{abstract}

\section{Introduction}

The C programming language \cite{KR} has been in use for over 30
years.  Consequently, there is a huge library of software written in
this language.  Although Java offers substantial benefits \cite{} over
C (and C++), its comparatively young age means that it often lacks
equivalents of many C/C++ libraries.

The typical solution to this dilemma is to use JNI \cite{} or CNI
\cite{} to invoke C code from within a Java VM.  Unfortunately, there
are a number of situations in which this is not an acceptable
solution due to security concerns:

\begin{itemize}

\item Java Applets are not permitted to invoke {\tt
      Runtime.loadLibrary()}

\item Java Servlet containers with a {\tt SecurityManager} will not
      permit loading new JNI libraries.  This configuration is popular
      with {\it shared hosting} providers and corporate intranets
      where a number of different parties contribute individual web
      applications which are run together in a single container.

\item Unlike Java Bytecode, JNI code is susceptible to buffer overflow
      and heap corruption attacks.  This can be a major security
      vulnerability.

\end{itemize}

In addition to security concerns, JNI and CNI carry other
disadvantages:

\begin{itemize}

\item JNI requires the native library to be compiled ahead of time,
      separately, for every architecture on which it will be deployed.
      This is unworkable for situations in which the full set of
      target architectures is not known at deployment time.

\item The increasingly popular J2ME \cite{} platform does not support
      JNI or CNI.

\item JNI often introduces undesirable added complexity to an
      application.

\end{itemize}

The technique we present here is based on using a typical ANSI C
compiler to compile C/C++ code into a MIPS binary, and then using a
tool to translate that binary 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{}, Perl Parrot \cite{}, or Python bytecode \cite{}.

\section{Approaches to Translation}

Techniques for translating unsafe code into VM bytecode generally fall
into four categories:

\begin{itemize}
\item source-to-source translation
\item source-to-binary translation
\item binary-to-source translation
\item binary-to-binary translation
\end{itemize}

\begin{figure}[h]
\begin{pdfpic}
\newlength{\MyLength}
\settowidth{\MyLength}{machine code}
\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
\begin{psmatrix}[colsep=3,rowsep=3]
  [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source}   \\[0pt]
  [name=b0]\MyBox{machine code}  & [name=b1]\MyBox{safe bytecode} \\
  \psset{nodesep=5pt,arrows=->}
  \ncline{s0}{b0}<{\it gcc}
  \ncline{s0}{s1}\aput{:U}{\it c2java}
  \ncline{s0}{b1}\aput{:U}{\it gcc bytecode backend}
  \ncline{s1}{b1}>{\it javac}
\end{psmatrix}
\end{pdfpic}
\caption{\label{lattice} Conversion Lattice with examples of tools specific to a C/JVM scenario}
\end{figure}

\begin{figure}[h]
\begin{pdfpic}
\newlength{\MyLength}
\settowidth{\MyLength}{machine code}
\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
\begin{psmatrix}[colsep=3,rowsep=3,nrot=:U]
  [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source}   \\[0pt]
  [name=b0]\MyBox{machine code}  & [name=b1]\MyBox{safe bytecode} \\
  \psset{nodesep=5pt,arrows=->}
  \ncline{s0}{b0}<{\it gcc}
  \ncline{s1}{b1}>{\it javac}
  \ncline{b0}{s1}\naput{\it NestedVM}
  \ncline{b0}{s1}\nbput{\it binary-to-source}
\end{psmatrix}
\end{pdfpic}
\caption{\label{lattice2} Conversion Lattice including NestedVM in {\it source-output} mode}
\end{figure}

\begin{figure}[h]
\begin{pdfpic}
\newlength{\MyLength}
\settowidth{\MyLength}{machine code}
\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
\begin{psmatrix}[colsep=3,rowsep=3,nrot=:U]
  [name=s0]\MyBox{unsafe source} & [name=s1]\MyBox{safe source}   \\[0pt]
  [name=b0]\MyBox{machine code}  & [name=b1]\MyBox{safe bytecode} \\
  \psset{nodesep=5pt,arrows=->}
  \ncline{s0}{b0}<{\it gcc}
  \ncline{s1}{b1}>{\it javac}
  \ncline{b0}{b1}\naput{\it NestedVM}
  \ncline{b0}{b1}\nbput{\it binary-to-binary}
\end{psmatrix}
\end{pdfpic}
\caption{\label{lattice3} Conversion Lattice including NestedVM in {\it bytecode-output} mode}
\end{figure}

A diagram showing these four translation approaches in the context of
running C/C++ code within a Java VM is shown in Figure~\ref{lattice}.

\subsection{Existing Work}
\subsubsection{Source-to-Source Translation}

\begin{itemize}
\item c2java
\item commercial products
\end{itemize}

A number of commercial products and research projects attempt to
translate C++ code to Java code, preserving the mapping of C++ classes
to Java classes.  Unfortunately, this is problematic since there is no
way to do pointer arithmetic except within arrays, and even in that
case, arithmetic cannot be done in terms of fractional objects.

Mention gcc backend

Many of these products advise the user to tweak the code which results
from the translation.  Unfortunately, hand-modifying machine-generated
code is generally a bad idea, since this modification cannot be
automated.  This means that every time the origin code changes, the
code generator must be re-run, and the hand modifications must be
performed yet again.  This is an error-prone process.

Furthermore, NestedVM does not attempt to read C code directly.  This
frees it from the complex task of faithfully implementing the ANSI C
standard (or, in the case of non ANSI-C compliant code, some other
interface).  This also saves the user the chore of altering their
build process to accomodate NestedVM.

\section{NestedVM}

NestedVM takes a novel approach; it uses compiled machine code as a
starting point for the translation process.  NestedVM has gone through
two iterations:

\begin{itemize}
\item binary-to-source compilation  (Figure~\ref{lattice2})
\item binary-to-binary compilation  (Figure~\ref{lattice3})
\end{itemize}

\subsection{Translation Process}

Translating a legacy library 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.

\item Invoke {\tt NestedVM} on the statically linked binary.
      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 (If using binary-to-source translation) compile the resulting
      {\tt .java} code using {\tt jikes} or {\tt javac}.

\item (Optional) compile the resulting bytecode into a {\it safe}
      native binary using {\tt gcj}.

\item From java code, invoke the {\tt run()} method on the generated
      class.  This is equivalent to the {\tt main()} entry point.

\end{enumerate}


\subsection{Why MIPS?}

We chose MIPS as a source format for two primary reasons: the
availability of tools to translate legacy code into MIPS binaries, and
the close similarity between the MIPS ISA and the Java Virtual Machine.

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 (with p2c), and Objective C
into MIPS binaries.

The MIPS R2000 ISA bears a striking similarity to the Java Virtual
Machine:

\begin{itemize}

%\item The original MIPS ISA supports only 32-bit aligned memory loads
%      and stores.  This allows NestedVM to represent memory as a Java
%      {\tt int[]} without introducing additional overhead.
\item Most of the instructions in the original MIPS ISA operate only on
      32-bit aligned memory locations. This allows NestedVM to represent
      memory as a Java {\tt int[]} array without introducing additional 
      overhead.

\item Unlike its predecessor, the R2000 supports 32-bit by 32-bit
      multiply and divide instructions as well as a single and double
      precision floating point unit.  These capabilities map nicely
      onto Java's arithmetic instructions.

\end{itemize}


\subsection{Binary-to-Source Compilation}

The first incarnation of NestedVM was a binary-to-source compiler.
This version reads in a MIPS binary and emits Java source code, which
can be compiled with {\tt javac}, {\tt jikes}, or {\tt gcj}.

This implementation was primarily a first step towards the
binary-to-binary compiler.  Conveniently, generating Java source code
frees NestedVM from having to perform simple constant propagation
optimizations, since 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 was optimal.

\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*}

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 somewhat large
binaries can be handled without much difficulty -- fortunately, there
is no corresponding limit on the size of a classfile as a whole.

Another interesting problem that was discovered while creating the
trampoline method was javac and Jikes' inability to properly optimize
switch statements.  The code in Figure~\ref{lookupswitch} is compiled
into a comparatively inefficient {\tt LOOKUPSWITCH}, while the code in
Figure~\ref{tableswitch} is optimized into a {\tt TABLESWITCH}.

\begin{figure}
{\footnotesize\begin{verbatim}
switch(pc&0xffffff00) {
    case 0x00000100: run_100(); break;
    case 0x00000200: run_200(); break;
    case 0x00000300: run_300(); break;
}
\end{verbatim}}
\caption{\label{lookupswitch} Code which {\it is not} optimized into a tableswitch}
\end{figure}

\begin{figure}
{\footnotesize\begin{verbatim}
switch(pc>>>8) {
    case 0x1: run_100(); break;
    case 0x2: run_200(); break;
    case 0x3: run_300(); break;
}
\end{verbatim}}
\caption{\label{tableswitch} Code which {\it is} optimized into a tableswitch}
\end{figure}

Javac is not smart enough to see the pattern in the case values and
generates very suboptimal bytecode. Manually doing the shifts
convinces javac to emit a tableswitch statement, which is
significantly faster. This change alone increased the speed of
the compiled binary by approximately 35\%.

Finding the optimal method size lead to the next big performance
increase.  It was determined through experimentation that the optimal
number of MIPS instructions per method is 64 or 128 (considering only 
powers of two). Going above or below that lead to performance
decreases. This is most likely due to a combination of two factors.

\begin{itemize}

\item The two levels of switch statements jumps have to pass though -
      The first switch statement jumps go through is the trampoline
      switch statement. This is implemented as a {\tt TABLESWITCH} in JVM
      bytecode so it is very fast. The second level switch statement
      in the individual run\_ methods is implemented as a
      {\tt LOOKUPSWITCH}, which is much slower. Using smaller methods puts
      more burden on the faster {\tt TABLESWITCH} and less on the slower
      {\tt LOOKUPSWITCH}.

\item JIT compilers probably favor smaller methods smaller methods are
      easier to compile and are probably better candidates for JIT
      compilation than larger methods.

\end{itemize}

Put a chart in here

Putting more than 256 instructions in each method lead to a severe
performance penalty. Apparently Hotspot does not handle very large methods
well. In some tests the simple moving from 256 to 512 instructions per
method decreased performance by a factor of 10.

Put chart here

The next big optimization was eliminating unnecessary case
statements. Having case statements before each instruction prevents
JIT compilers from being able to optimize across instruction
boundaries. In order to eliminate unnecessary case statements every
possible address that could be jumped to directly needed to be
identified. The sources for possible jump targets come from 3 places.

\begin{itemize}

\item The .text segment - Every instruction in the text segment is
      scanned for jump targets. Every branch instruction (BEQ, JAL,
      etc) has its destination added to the list of possible branch
      targets. In addition, functions that set the link register have
      theirpc+8 added to the list (the address that would have been put
      to the link register). Finally, combinations of LUI (Load Upper
      Immediate) of ADDIU (Add Immediate Unsigned) are scanned for
      possible addresses in the text segment. This combination of
      instructions is often used to load a 32-bit word into a
      register.

\item The .data segment - When GCC generates switch() statements it
      often uses a jump table stored in the .data
      segment. Unfortunately gcc does not identify these jump tables in
      any way. Therefore, the entire .data segment is conservatively
      scanned for possible addresses in the .text segment.
      
\item The symbol table - This is mainly used as a backup. Scanning the
      .text and .data segments should identify any possible jump
      targets but adding every function in the symbol table in the ELF
      binary does not hurt. This will also catch functions that are
      never called directly from the MIPS binary (for example,
      functions called with the call() method in the runtime).

\end{itemize}

Eliminating unnecessary case statements provided a 10-25\% speed
increase.

Despite all the above optimizations and workarounds an impossible to
workaround hard classfile limit was eventually hit, the constant
pool. The constant pool in classfiles is limited to 65536
entries. Every integer with a magnitude greater than 32767 requires an
entry in the constant pool. Every time the compiler emits a
jump or branch instruction the PC field is set to the branch target. This
means nearly every branch instruction requires an entry in the
constant pool. Large binaries hit this limit fairly quickly. One
workaround that was employed in the Java source compiler was to
express constants as offsets from a few central values. For example:
``pc = N\_0x00010000 + 0x10'' where N\_0x000100000 is a non-final
field to prevent javac from inlining it. This was sufficient to get
reasonable large binaries to compile. It has a small (approximately
5\%) performance impact on the generated code. It also makes the
generated classfile somewhat larger.  Fortunately, the classfile
compiler eliminates this problem.


\subsection{Binary-to-Binary Translation}

The next step in the evolution of NestedVM was to compile directly to
JVM bytecode eliminating the intermediate javac step. This had several
advantages:

\begin{itemize}
      
\item There are little tricks that can be done in JVM bytecode that
      cannot be done in Java source code.

\item Eliminates the time-consuming javac step - Javac takes a long
      time to parse and compile the output from the java source
      compiler.

\item Allows for MIPS binaries to be compiled and loaded into a
      running VM using a class loader. This eliminates the need to
      compile the binaries ahead of time.

\end{itemize}

By generating code at the bytecode level there are many areas where
the compiler can be smarter than javac. Most of the areas where
improvements where made where in the handling of branch instructions
and in taking advantage of the JVM stack to eliminate unnecessary
LOADs and STOREs to local variables.

The first obvious optimization that generating bytecode allows for is the
use of GOTO. Despite the fact that Java does not have a GOTO keyword a GOTO
bytecode does exist and is used heavily in the code generates by javac.
Unfortunately the java language does not provide any way to take advantage of
this. As result of this, jumps within a method were implemented in the
binary-to-source compiler by setting the PC field to the new address and
making a trip back to the initial switch statement.  In the classfile
compiler these jumps are implemented as GOTOs directly to the target
instruction. This saves a costly trip back through the LOOKUPSWITCH
statement and is a huge win for small loops within a method.

Somewhat related to using GOTO is the ability to optimize branch
statements. In the Java source compiler branch statements are
implemented as follows (delay slots are ignored for the purpose of
this example):

{\footnotesize\begin{verbatim}
if(condition) { pc = TARGET; continue; }
\end{verbatim}}

This requires a branch in the JVM regardless of whether the MIPS
branch is actually taken. If condition is false the JVM has to jump
over the code to set the PC and go back to the switch block. If
condition is true the JVM has to jump to the switch block. By
generating bytecode directly we can make the target of the JVM branch
statement the actual bytecode of the final destination. In the case
where the branch is not taken the JVM does not need to branch at all.

A side affect of the above two optimizations is a solution to the
excess constant pool entries problem. When jumps are implemented as
GOTOs and direct branches to the target the PC field does not need to
be set. This eliminates many of the constant pool entries the java
source compiler requires. The limit is still there however, and given
a large enough binary it will still be reached.

Delay slots are another area where things are done somewhat
inefficiently in the Java source compiler. In order to take advantage
of instructions already in the pipeline MIPS cpu have a ``delay
slot''. That is, an instruction after a branch or jump instruction that
is executed regardless of whether the branch is taken. This is done
because by the time the branch or jump instruction is finished being
processes the next instruction is already ready to be executed and it
is wasteful to discard it. (However, newer MIPS CPUs have pipelines
that are much larger than early MIPS CPUs so they have to discard many
instructions anyway.) As a result of this the instruction in the delay
slot is actually executed BEFORE the branch is taken. To make things
even more difficult, values from the register file are loaded BEFORE
the delay slot is executed.  Here is a small piece of MIPS assembly:

{\footnotesize\begin{verbatim}
ADDIU r2,r0,-1
BLTZ r2, target
ADDIU r2,r2,10
...
:target
\end{verbatim}}

This piece of code is executed as follows

\begin{enumerate}

\item r2 is set to -1

\item r2 is loaded from the register file by the BLTEZ instruction
      
\item 10 is added to r2 by the ADDIU instruction

\item The branch is taken because at the time the BLTZ instruction was
      executed r2 was -1, but r2 is now 9 (-1 + 10)

\end{enumerate}

There is a very elegent solution to this problem when using JVM
bytecode. When a branch instruction is encountered the registers
needed for the comparison are pushed onto the stack to prepare for the
JVM branch instruction. Then, AFTER the values are on the stack the
delay slot is emitted, and then finally 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. This allows delay
slots to be used with no performance penalty or size penalty.

One final advantage that generating bytecode directly allows is
smaller more compact bytecode. All the optimizations above lead to
smaller bytecode as a side effect. There are also a few other areas
where the generated bytecode can be optimized for size with more
knowledge of the program as a whole.

When encountering the following switch block both javac and 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 ALOAD\_0 to
prepare for a invoke special call. By simple moving this outside the switch
statement each case arm was reduced in size by one instruction. Similar
optimizations were also done in other parts of the compiler.

\section{Interfacing with Java Code}

NestedVM has two primary ways of executing code, the interpreter, and the
binary translators. Both the interpreter and the output from the binary
translators sit on top of a Runtime class. This class provides the public
interface to both the interpreter and the translated binaries.

\subsection{The Runtime Class}

The Runtime class does the work that the operating system usually does.
Conceptually the Runtime class can be thought of as the operating system and
its subclasses (translated binaries and the interpreter) the CPU. The
Runtime fulfills 5 primary goals:

\begin{itemize}

\item Provides a 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.

\item Provide an easy to use interface - The interpreter and the output from
the binary translators only know how to execute code. The Runtime class
provides an easy to use interface to the code. It contains methods to pass
arguments to the main() function, read and write from memory, and call
individual functions in the binary.

\item Manage the process's memory - The Runtime class contains large int[]
arrays that represent the process`s entire memory space.  Subclasses read
and write to these arrays as required by the instructions they are
executing.  Subclasses can expend their memory space using the sbrk
syscall.

\item Provide access to the file system and streams - Subclasses access the
file system through standard UNIX syscalls (read, write, open, etc). The
Runtime manages the file descriptor table that maps UNIX file descriptors
to Java RandomAccessFiles, InputStreams, OutputStreams, and sockets.

\item Miscellaneous other syscalls - In additions to those mentioned above
the Runtime class implements a variety of other syscalls (sleep,
gettimeofday, getpagesize, sysconf, fcntl, etc).

\end{itemize}

\subsection{Interacting with the Binary}

Java source code can create a copy of the translated binary by instantiating
the class generated by the binary translator or instantiating the
interpreter. It can then interact with the process through the many
facilities provided by the Runtime interface.  Invoking the run() method of
the Runtime interface will load the given arguments into the process's
memory as invoke the binaries entry point (typically \_start() in crt0.o).
This will pass control on to the main() function which will have the
arguments passed to run() loaded into argv and argc.

As the binary executes it often passes control back to the Runtime class
through the MIPS {\tt SYSCALL} instruction. The interpreter and translated
binaries invoke the {\tt syscall()} method of the Runtime class when the
{\tt SYSCALL} instruction is executed. The Runtime class then can manipulate
the process's environment (read and write to memory, modify the file
descriptor table, etc) and interact with the rest of the JVM on behalf of
the process (read and write to a file or stream, etc). There is even a
syscall to pause the VM and temporarily return control to the caller.

In addition to the interfaces provided by NestedVM, users can create their
own interfaces between the MIPS and Java world. The Runtime provides a
method called call() that will call a function by name in the MIPS binary.
The call() method looks up the function name in the binary's ELF symbol
table and manipulating the stack and registers accordingly to execute the
given function. This allows Java code to seamlessly invoke functions in the
binary.

{\footnotesize\begin{verbatim}
// Java
private Runtime rt = new MyBinary();
public void foo(int n) {
    for(int i=0;i<10;i++) {
        int result = rt.call("do_work",i);
        System.err.println("do_work(i) = " + result);
    }
}
// C
void do_work(int n) {
    int i;
    int ret=0;
    for(i=0;i<n;i++) ret += i;
    return n;
}
\end{verbatim}}

The MIPS binaries can also invoke a special method of Runtime called
callJava().When the MIPS binary invokes the {\tt CALL\_JAVA} syscall
(usually done through the {\tt \_call\_java()} function provided by the
NestedVM support library) the callJava() method in Runtime is invoked with
the arguments passes to the syscall.

{\footnotesize\begin{verbatim}
// Java
private Runtime rt = new MyBinary() {
    pubilc int callJava(int a, int b, int c, int d) { System.err.println("Got " + a + " " + b);
};
public void foo() { rt.run(); }
// C
void main(int argc, char **argv) {
    _call_java(1,2);
}
\end{verbatim}}

These two methods can even be combined. MIPS can call Java through the
CALL\_JAVA syscall, which can in turn invoke a MIPS function in the binary
with the call() method.

Users preferring a simpler communication mechanism can also use Java
Stream's and file descriptors. Runtime provides a simple interface for
mapping a Java Input or OutputStream to a File Descriptor.

%Java source code can create a copy of the translated binary by
%instantiating the corresponding class, which extends {\tt Runtime}.
%Invoking the {\tt main()} method on this class is equivalent to
%calling the {\tt main()} function within the binary; the {\tt String}
%arguments to this function are copied into the binary's memory space
%and made available as {\tt **argv} and {\tt argc}.

%The translated binary communicates with the rest of the VM by
%executing MIPS {\tt SYSCALL} instructions, which are translated into
%invocations of the {\tt syscall()} method.  This calls back to the
%native Java world, which can manipulate the binary's environment by
%reading and writing to its memory space, checking its exit status,
%pausing the VM, and restarting the VM.


%\subsection{Virtualization}

%The {\tt Runtime} class implements the majority of the standard {\tt
%libc} syscalls, providing a complete interface to the filesystem,
%network socket library, time of day, (Brian: what else goes here?).

%\begin{itemize}

%\item ability to provide the same interface to CNI code and
%      NestedVMified code
      
%\item security advantages (chroot the {\tt fork()}ed process)
%
%\end{itemize}


\section{Quantitative Performance}

\subsection{Charts}

(Note that none of these libraries have pure-Java equivalents.)

\begin{itemize}
\item libjpeg
\item libfreetype
\item libmspack
\end{itemize}


\subsection{Optimizations}

Although NestedVM perfectly emulates a MIPS R2000 CPU its performance
characteristics are not anything like an actual MIPS R2000 CPU. GCC makes
several optimizations that increase performance on an actually MIPS CPU but
actually decrease performance when run through the NestedVM binary
translator. Fortunately, GCC provides many options to customize its code
generations and eliminate these optimizations. GCC also has optimization
options that are not helpful on a real MIPS CPU but are very helpful under
NestedVM

Adam, we should cite "Using the GNU Compiler Collection" somewhere in here.

\begin{itemize}

\item {\tt -falign-functions}
Normally a function's location in memory has no effect on its execution
speed. However, in the NestedVM binary translator, the .text segment is
split up on power of two boundaries. If a function is unlucky enough to
start near the end of one of these boundaries a performance critical part of
the function could end up spanning two methods. There is a significant
amount of overhead in switching between two methods so this must be avoided
at all costs. By telling GCC to align all functions to the boundary that the
.text segment is split on the chances of a critical part of a function
spanning two methods is significantly reduced.

\item {\tt -fno-rename-registers}
Some processors can better schedule code when registers are not reused for
two different purposes. By default GCC will try to use as many registers as
possibly when it can. This excess use of registers just confuses JIT's
trying to compile the output from the binary translator. All the JIT
compilers we tested do much better with a few frequently used registers.

\item {\tt -fno-delayed-branch}
The MIPS CPU has a delay slot (see above). Earlier versions of NestedVM did
not efficiently emulate delay slots. This option causes GCC to avoid using
delay slots for anything (a NOP is simply placed in the delay slot). This
had a small performance benefit. However, recent versions of NestedVM
emulate delay slots with no performance overhead so this options has little
effect. Nonetheless, these delay slots provide no benefit under NestedVM
either so they are avoided with this option.

\item {\tt -fno-schedule-insns}
Load operations in the MIPS ISA also have a delay slot. The results of a
load operation are not available for use until one instruction later.
Several other instructions also have similar delay slots. GCC tries to do
useful work wile waiting for the results of one of these operations by
default. However, this, like register renaming, tends to confuse JIT
compilers. This option prevents GCC from going out of its way to take
advantage of these delay slots and makes the code generated by NestedVM
easier for JIT compilers to handle.

\item {\tt -mmemcpy}
GCC sometimes has to copy somewhat large areas of memory. The most common
example of this is assigning one struct to another. Memory copying can be
done far more efficiently in Java than under NestedVM. Calls to the memcpy
libc function are treated specially by the binary translator. They are
turned into calls to a memcpy method in Runtime. The {\tt -mmemcpy} option
causes GCC to invoke libc's memcpy() function when it needs to copy a region
of memory rather than generating its own memcpy code. This call in then
turned into a call to this Java memcpy function which is significantly
faster than the MIPS implementation.

\item {\tt -ffunction-sections -fdata-sections}
These two options are used in conjunction with the {\tt --gc-section} linker
option. These three options cause the linker to aggressively discard unused
functions and data sections. In some cases this leads to significantly
smaller binaries.

%\item {\tt trampoline}
%\item {\tt optimal method size}
%\item {\tt -msingle-float}
%\item {\tt -mmemcpy}
%\item {\tt fastmem}
%\item {\tt local vars for registers (useless)}
%\item {\tt -fno-rename-registers}
%\item {\tt -ffast-math}
%\item {\tt -fno-trapping-math}
%\item {\tt -fsingle-precision-constant}
%\item {\tt -mfused-madd}
%\item {\tt -freg-struct-return}
%\item {\tt -freduce-all-givs}
%\item {\tt -fno-peephole}
%\item {\tt -fno-peephole2}
%\item {\tt -fmove-all-movables}
%\item {\tt -fno-sched-spec-load}
%\item {\tt -fno-sched-spec}
%\item {\tt -fno-schedule-insns}
%\item {\tt -fno-schedule-insns2}
%\item {\tt -fno-delayed-branch}
%\item {\tt -fno-function-cse}
%\item {\tt -ffunction-sections}
%\item {\tt -fdata-sections}
%\item {\tt array bounds checking}
%\item {\tt -falign-functions=n}
%\item {\tt -falign-labels=n}
%\item {\tt -falign-loops=n}
%\item {\tt -falign-jumps=n}
%\item {\tt -fno-function-cse}
\end{itemize}

\section{Future Directions}

\begin{itemize}

\item Better use of local variables in binary-to-binary compiler -- need to
do data flow analysis to find how how and when registers are used and avoid
the costly load/restore when it isn't necessary.

\item More advanced Runtime support -- support more syscalls. This will
allow running large applications such as GCC under NestedVM.

\item World domination

\end{itemize}

\section{Conclusion}

We rock the hizzouse.

\section{References}

Yer mom.

\section{stuff}
\begin{onecolumn}
{\footnotesize\begin{verbatim}

libjpeg (render thebride_1280.jpg)
Native -  0.235s
JavaSource - 1.86s
ClassFile - 1.37s

freetype (rendering characters 32-127 of Comic.TTF at sizes from 8 to
48 incrementing by 4)
Native - 0.201s
JavaSource - 2.02s
ClassFile - 1.46s

                                          libjpeg  libmspack libfreetype
Interpreted MIPS Binary                   22.2      12.9      21.4
Compled MIPS Binary (fastest options)     3.39      2.23      4.31
Native -O3                                0.235    0.084     0.201

Compled - with all case statements        3.50      2.30      4.99
Compiled - with pruned case statement     3.39      2.23      4.31

Compiled - 512 instructions/method        62.7      27.7      56.9
Compiled - 256 instructions/method        3.54      2.55      4.43
Compiled - 128 instructions/method        3.39      2.23      4.31
Compiled - 64 instructions/method         3.56      2.31      4.40
Compiled - 32 instruction/method          3.71      2.46      4.64

Compild MIPS Binary (Server VM)           3.21      2.00      4.54
Compiled MIPS Binary (Client VM)          3.39      2.23      4.31

All times are measured in seconds. These were all run on a dual 1ghz G4
running OS X 10.3.1 with Apple's latest VM (JDK 1.4.1_01-27). 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 libjpeg test consisted of decoding a 1280x1024 jpeg
(thebride_1280.jpg) and writing a tga. The mspack test consisted of
extracting all members from arial32.exe, comic32.exe, times32.exe, and
verdan32.exe. The freetype test consisted of rendering characters
32-127 of Comic.TTF at sizes from 8 to 48 incrementing by 4. (That is
about 950 individual glyphs).

I can provide you with the source for any of these test if you'd like.

-Brian
\end{verbatim}}
\end{onecolumn}
\end{document}