\usepackage{amssymb,amsmath,epsfig,alltt}
\sloppy
\usepackage{palatino}
-\usepackage{pdftricks}
-\begin{psinputs}
- \usepackage{pstricks}
- \usepackage{pst-node}
-\end{psinputs}
+\usepackage{url}
+%\usepackage{pdftricks}
+%\begin{psinputs}
+\usepackage{pstricks}
+\usepackage{pst-node}
+%\end{psinputs}
\usepackage{parskip}
\usepackage{tabularx}
\usepackage{alltt}
\maketitle
-{\it This document was typeset using D. E. Knuth's original \TeX 89,
+{\it This document was typeset using D. E. Knuth's original \TeX ,
which was both compiled and executed entirely within a Java
Virtual Machine without the use of native code.}
We present an alternative approach which translate MIPS binaries
produced by any compiler into safe virtual machine bytecodes. This
approach offers four key advantages over existing techniques: it is
-language agnostic, it offers bug-for-bug compiler compatability,
+language agnostic, it offers bug-for-bug compiler compatibility,
requires no post-translation human intervention, and introduces no
build process modifications.
which was used as one of our performance tests, \TeX\ (Pascal), 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.
+of the Ibex Project \cite{ibex}, 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
\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}.
+Unsafe languages such as C and C++ have been in use much longer than
+any of today's widely accepted safe languages such as Java and C\#
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
performing transformations between them. In the third section we
introduce NestedVM and cover its two primary translation modes in
detail. Section four describes the NestedVM runtime, which plays the
-role of the OS kernel. Section five adresses the optimizations we
+role of the OS kernel. Section five addresses the optimizations we
employ and quantifies NestedVM's performance. Section six reviews our
experiences in applying NestedVM to various popular software packages.
We conclude with an analysis of NestedVM's weaknesses and potential
with their specific types in the C-to-JVM instantiation of the
problem are shown in the following diagram:
-\begin{pdfpic}
+%\begin{pdfpic}
\newlength{\MyLength}
\settowidth{\MyLength}{machine code}
\newcommand{\MyBox}[1]{\makebox[\MyLength][c]{#1}}
& \\[0pt]
\psset{nodesep=5pt,arrows=->}
\end{psmatrix}
-\end{pdfpic}
+%\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}}
+%\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]
\ncline{s1}{b1}\aput{:U}{\tt javac}
\ncline{b1}{b0}\aput{:D}{\tt gcj}\bput{:D}{JITs}
\endpsmatrix
-\end{pdfpic}
+%\end{pdfpic}
Existing techniques for translating unsafe code into VM bytecode
generally fall into two categories, which we expand upon in the
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}}
+%\begin{pdfpic}
+%\newlength{\MyLength}
+%\settowidth{\MyLength}{xmachine codex}
+%\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
\psmatrix[colsep=2,rowsep=0,nrot=:U]
& \\[0pt]
& \\[0pt]
\ncline{s0}{s1}\aput{:U}{source-to}\bput{:U}{source}
\ncline{s1}{b1}\aput{:U}{\tt javac}
\endpsmatrix
-\end{pdfpic}
+%\end{pdfpic}
A number of existing systems employ this technique; they can
be divided into two categories: those which perform a partial
\subsubsection{Human-Assisted Translation}
Jazillian \cite{jazillian} is a commercial solution which produces
-extremely readable Java source code from C source code, but ony
+extremely readable Java source code from C source code, but only
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
+String~s1~=~s2}''. Unfortunately such deep analysis is intractable
for most of the C language and standard library; indeed, Jazillian's
documentation notes that {\it ``This is not your father's language
translator... Jazillian does not always produce code that works
\subsubsection{Partial-Domain Translation}
-The {\tt c2j} \cite{c2j}, {\tt c2j++} \cite{c2jpp}, Cappucinno
+The {\tt c2j} \cite{c2j}, {\tt c2j++}, 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
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
+program, a single anomaly 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
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}}
+%\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]
\psset{nodesep=5pt,arrows=->}
\ncline{s0}{b1}\bput{:U}{source-to-binary}
\endpsmatrix
-\end{pdfpic}
+%\end{pdfpic}
An experimental ``JVM backend'' for the {\tt gcc} compiler, known as
{\tt egcs-jvm} \cite{egcsjvm}, attempts this approach. Since {\tt
which cannot be directly supported; thus the compiler still fails for
a substantial class of input programs.
-A Java backend for the {\tt lcc} [CITE] compiler, known as {\tt
-lcc-java} [CITE], is also available. Although this system is quite
+A Java backend for the {\tt lcc} compiler \cite{lcc}, known as {\tt
+lcc-java}, is also available. Although this system is quite
clean and elegantly designed, it lacks any form of system library
({\tt libc}), so very few C programs will run without custom
modification (which would cause them to diverge from the upstream
translation. This offers three immediate advantages:
\begin{itemize}
-\item {\bf Language Agnostic}
+\item {\bf Language Agnosticism}
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++), and is able to support any langage for which a
+ C++), and is able to support any language for which a
MIPS-targeted compiler exists.
-\item {\bf Bug-for-bug compiler compatability}
+\item {\bf Bug-for-bug compiler compatibility}
Since NestedVM uses the compiler's {\it output} as its own {\it
input}, it ensures that programs which are inadvertently
always succeeds for valid input binaries.
\end{itemize}
-This is a much more important factor than is obvious at first glance.
+This last point has important software engineering implications.
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
individual performing this task, rather than being encoded in build
scripts which persist throughout the lifetime of the project.
-\subsection{Why MIPS?}
+\subsection{Mapping the R2000 onto the JVM}
We chose MIPS as a source format for three reasons: the availability
-of tools to compile legacy code into MIPS binaries, the close
-similarity (FIXME: explain) 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.
+of tools to compile legacy code into MIPS binaries, the many
+similarities 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.
-
-\item Although MIPS offers unsigned arithmetic and Java does not, few
- MIPS instructions actually depend on non-two's-complement
- handling of integer math. Furthermore, since most high-level
- languages such as C do not expose access to arithmetic-overflow
- exceptions, these instructions are rarely found except in
- hand-coded assembler. In the few situations where these
- instructions {\it are} encountered, the {\tt unsigned int} is
- cast (bitwise) to a Java {\tt long}, the operation is performed,
- and the result is cast back. On architectures offering 64-bit
- integer math this conversion carries no overhead.
-
-\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:
+The MIPS R2000 ISA bears many similarities to the Java Virtual
+Machine. 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 indexed by page (the
+top $n$ bits of the address) and offset (the remaining bits) without
+introducing additional overhead. MIPS's non-aligned memory load
+instructions are only rarely emitted by most compilers since they
+carry a performance penalty on physical MIPS implementations.
+
+Our choice of a paged representation for memory carries only a small
+performance disadvantage:
+
+\epsfig{file=charts/chart5,height=2.7in,angle=-90}
+
+Additionally, this representation lets us to take advantage of the
+fact that on most JVM's, checking for a {\tt NullPointerException}
+carries no performance penalty unless the exception is thrown (the
+host CPU's MMU is generally used to detect this condition). This
+allows us to lazily expand the MIPS memory space as it is used.
+Additionally, we maintain two page arrays, one which is used for read
+operations and another for writes. Most of the time these page arrays
+will have identical entries; however, we can simulate a portion of the
+MIPS MMU functionality by setting the appropriate entry in the write
+page table to {\tt null}, thereby write protecting the page while
+still allowing reads.
+
+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 and {\tt int}, {\tt long}, {\tt float}, and
+{\tt double} types.
+
+Although MIPS offers unsigned arithmetic and Java does not, few MIPS
+instructions actually depend on non-two's-complement handling of
+integer math. In the few situations where these instructions {\it
+are} encountered, the {\tt unsigned int} is cast (bitwise) to a Java
+{\tt long}, the operation is performed, and the result is cast back.
+On host architectures offering 64-bit arithmetic this operation
+carries no performance penalty.
+
+In addition to its similarities to the JVM, the MIPS ISA and ABI
+convey quite a bit of information about program structure. This
+information can be used for optimization purposes:
\begin{itemize}
-\subsection{Binary-to-Source}
+\subsection{Binary-to-Source Mode}
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}}
+%\begin{pdfpic}
+%\newlength{\MyLength}
+%\settowidth{\MyLength}{xmachine codex}
+%\newcommand{\MyBox}[1]{\makebox[\MyLength]{#1}}
\psmatrix[colsep=2,rowsep=0,nrot=:U]
& \\[0pt]
& \\[0pt]
\ncline{s1}{b1}\aput{:U}{\tt javac}
\ncline{b0}{s1}\naput{\tt NestedVM}
\endpsmatrix
-\end{pdfpic}
+%\end{pdfpic}
\begin{figure*}[t]
\begin{minipage}[c]{7in}%
Translating unsafe code for use within a JVM proceeds as follows:
\begin{enumerate}
+\item The unsafe source code is compiled to a statically linked
+ binary, including any libraries (including {\tt libc}) it needs.
-\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. Any other
- libraries which are not tied to a particular OS kernel can be
- linked in (even in binary form) using standard linker commands.
-
-\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 {\tt NestedVM} is invoked on the statically linked binary, and
+ emits a {\tt .java} file.
-\item From java code, invoke the {\tt run()} method on the generated
- class. This is equivalent to the {\tt main()} entry point.
+\item The resulting {\tt .java} code is compiled into a {\tt .class}
+ file using {\tt jikes} or {\tt javac}.
+\item At runtime, the host Java code invokes the {\tt run()} method on
+ the generated class. This is equivalent to the {\tt main()}
+ entry point.
\end{enumerate}
-\subsection{Binary-to-Binary}
+\subsection{Binary-to-Binary Mode}
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}}
+%\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]
\ncline{s0}{b0}\bput{:U}{\tt gcc}
\ncline{b0}{b1}\naput{\tt NestedVM}
\endpsmatrix
-\end{pdfpic}
+%\end{pdfpic}
This mode has several advantages:
\end{itemize}
-\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).
+\section{The NestedVM Runtime}
-The NestedVM Runtime (various subclasses of {\tt
-org.ibex.nestedvm.Runtime}) fill the role of an OS Kernel.
-Communication between MIPS code and the outside world is via the MIPS
+The NestedVM runtime fills the role typically assumed by an OS Kernel.
+Communication between MIPS code and the runtime is mediated by the
{\tt SYSCALL} instruction, just as the {\tt libc}-kernel interface is
-on real MIPS implementations.
+on other MIPS implementations.
-Two implemenations of the runtime are offered; a simple runtime with
+Two implementations of the runtime are offered; a simple runtime with
the minimum support required to comply with ANSI C, and a more
sophisticated runtime which emulates a large portion of the POSIX API.
open()}, {\tt close()}, {\tt read()}, {\tt write()}, and {\tt seek()}.
File descriptors are implemented much as they are in OS kernels; a
table of open files is maintained and descriptors act as an index into
-that table. Each file is represented as a Java {\tt RandomAccessFile}
-in order to match the semantics of {\tt seek()}.
+that table. Each file descriptor is represented as a Java {\tt
+RandomAccessFile} in order to match the semantics of {\tt seek()}.
Process-level memory management is done through the {\tt sbrk()}
system call, which extends the process heap by adding more pages to
the memory page table. Fast memory clear and copy operations can be
performed with {\tt memset()} and {\tt memcpy()}, which invoke the
-Java {\tt System.arraycopy()} method, which is generally much faster
-than a {\tt for()} loop.
+Java {\tt System.arraycopy()} method.
-The {\tt exit()} call records the exit status, marks the VM instance
-as terminated and halts execution. The {\tt pause()} syscall
+The {\tt exit()} call records the process' exit status, marks the VM
+instance as terminated and halts execution. The {\tt pause()} syscall
implements a crude form of Java-MIPS communication by returning
control to the Java code which spawned the MIPS process.
+
\subsection{The Unix Runtime}
-The Unix runtime extends the simple ANSI file I/O model to include a
-single-root filesystem, and device nodes, as well as {\tt fcntl()}
-APIs to manipulate these. Device nodes are generally simulated by
-mapping reads, writes, and {\tt fcntl()}s on the device to the
-appropriate Java API.
+The Unix runtime extends the simple ANSI C file I/O model to include a
+unified-root filesystem, device nodes, and {\tt fcntl()} APIs. Device
+nodes are generally simulated by mapping reads, writes, and {\tt
+fcntl()}s on the device to the appropriate Java API.
MIPS processes can ``mount'' other filesystems within the virtual
filesystem made visible to the MIPS process. Each filesystem is
mkdir}, and {\tt unlink()}, and {\tt getdents()}), the contents of a
zip archive, or even a remote HTTP server.
-MIPS processes can also spawn subprocesses using the {\tt fork()} and
-{\tt exec()} calls, which create new Java threads to run the process.
-The {\tt fork()} call -- which is supposed to duplicate the memory
-image of a process -- is implemented in an elegant manner by calling
+The {\tt fork()} call is implemented in an elegant manner by calling
the Java {\tt clone()} method (deep copy) on the VM object itself.
-Copy-on-write is not currently implemented. The new instance is added
-to a static process table to facilitate interprocess communication.
-
-The {\tt waitpid()} API allows a parent process to block pending the
-completion of a child process, which is done quite easily with the
-Java {\tt wait()} method.
+The new instance is then added to a static process table to facilitate
+interprocess communication.
The {\tt exec()} method actually loads a MIPS binary image from the
filesystem, feeds it to the MIPS-to-bytecode translator, and then
loads the resulting bytecode on the fly using {\tt
-ClassLoader.loadBytes()}. The {\tt pipe()} system call permits
+ClassLoader.loadBytes()}.
+
+The {\tt waitpid()} API allows a parent process to block pending the
+completion of a child process, which is modeled quite easily with the
+Java {\tt wait()} method. The {\tt pipe()} system call permits
parent-to-child IPC just as on a normal Unix system.
Simple networking support is provided by the {\tt opensocket()}, {\tt
-listensocket()}, and {\tt accept()} methods, which are not currently
-compatible with the usual Berkeley sockets API.
+listensocket()}, and {\tt accept()} methods, which are not yet fully
+compatible with the standard Berkeley sockets API.
\subsection{Security Concerns}
-RuntimeExceptions don't escape, they care caught and turned into
-checked exceptions filesystem access does though security manager
-(NestedVM Runtime.SecurityManager, and the JVM's)
+NestedVM processes are completely isolated from the outside world
+except for the {\tt SYSCALL} instruction. As previously mentioned,
+the programmer can choose from various runtime implementations which
+translate these invocations into operations in the outside world. By
+default, none of these implementations allows file or network I/O;
+this must be explicitly enabled, typically on a per-file basis.
+
+Wild writes within the MIPS VM have no effect on the larger JVM or the
+host OS; they can only cause the {\tt SYSCALL} instruction to be
+invoked. A judicious choice of which system calls to enable offers
+extremely strong security; for example, the {\tt libjpeg} library does
+not need any host services whatsoever -- its sole task is to
+decompress one image (which is pre-written into memory before it
+starts up), write the decompressed image to another part of memory,
+and exit. With all system calls disabled, {\tt libjpeg} will function
+correctly, and even if it is compromised (for example by a
+maliciously-constructed invalid image), the only effect it can have on
+the host is to generate an incorrect decompressed image.
\subsection{Threading}
The NestedVM runtime currently does not support threading. Providing
robust support for ``true threads'', whereby each MIPS thread maps to
a Java thread is probably not possible as the Java Memory Model
-[CITE], since all MIPS memory is stored in a set of {\tt int[]}'s and
-the Java Memory Model does not permit varying treatment or coherency
-policies at the granularity of a single array element.
+\cite{jmm}, since all MIPS memory is stored in a set of {\tt
+int[]}'s and the Java Memory Model does not permit varying treatment
+or coherency policies at the granularity of a single array element.
While this presents a major barrier for applications that use
-sophisticated locking schemes (such as {\it hash synchronization})
-which depend on atomic memory operations, it is probably possible to
-apply this threading model to ``well behaved'' multithreaded
-applications which depend only on OS-provided semaphores and mutexes
-for synchronization.
+sophisticated locking schemes such as {\it hash synchronization} and
+depend on atomic memory operations, it is probably possible to apply
+this threading model to ``well behaved'' multithreaded applications
+which make no concurrency assumptions other than those explicitly
+offered by OS-provided semaphores and mutexes.
Complex synchronization and incorrectly synchronized applications can
be supported by implementing a variant of {\it user threads} within a
single Java thread by providing a timer interrupt (via a Java
asynchronous exception). Unfortunately this requires that the
-compiled binary be able to restart from any arbitrary instruction
+compiled binary be able to restart at any arbitrary instruction
address, which would require a {\tt case} statement for every
instruction (rather than every jump target), which would degrade
performance and increase the size of the resulting class file.
\section{Optimization and Performance}
-\subsection{Binary-to-Source mode}
+\subsection{Binary-to-Source Mode}
Generating Java source code instead of bytecode frees NestedVM from
having to perform simple constant propagation optimizations, as most
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.
-
+registers to 32 {\tt int} fields turned out to be optimal. Using
+local variables for registers did not offer much of a performance
+advantage, presumably since the JVM's JIT is intelligent enough to
+register-allocate temporaries for fields.
-\epsfig{file=charts/chart1,width=3in}
+\epsfig{file=charts/chart4,height=2.7in,angle=-90}
Unfortunately, Java imposes a 64kb limit on the size of the bytecode
for a single method. This presents a problem for NestedVM, and
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
+conclusion that HotSpot \cite{hotspot} -- the most widely deployed JVM
-- performs best when 128 MIPS instructions are mapped to each method.
-\epsfig{file=charts/chart5,width=3in}
-
-\epsfig{file=charts/chart6,width=3in}
+\epsfig{file=charts/chart1,height=2.7in,angle=-90}
This phenomenon is due to two factors:
\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
+eliminating extraneous case branches, which yielded approximately a
+10\%-25\% performance improvement. 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:
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.
+ possible branch targets. In addition, the
+ address\footnote{actually {\tt addr+8}} of any function that
+ sets the link register is added to the list. 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}
\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.
+ The symbol table is used primarily as a backup source of jump
+ targets. 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}
{\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
+degradation 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 mode}
+\subsection{Binary-to-Binary Mode}
+
+Compiling directly to bytecode offers a substantial performance gain:
-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=charts/chart3,height=2.7in,angle=-90}
-\epsfig{file=charts/chart7,width=3in}
+Most of this improvement comes from the handling of branch
+instructions and from taking advantage of the JVM stack to eliminate
+unnecessary {\tt LOAD}s and {\tt STORE}s to local variables.
The first optimization gained by direct bytecode generation came from
the use of the JVM {\tt GOTO} instruction. Despite the fact that the
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
+statement; 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
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.
+Fortunately there is a very elegant solution to this problem when
+directly emitting 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 instruction makes to the registers are not visible to the branch
+bytecode.
+
+One final advantage of emitting bytecode 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 size optimizations.
When encountering the following {\tt switch} block, both {\tt javac}
and {\tt jikes} generate redundant bytecode.
lifting this bytecode outside of the {\tt switch} statement, each {\tt
case} arm shrinks by one instruction.
+The net result is quite reasonably sized {\tt .class} files:
+
+\epsfig{file=charts/chart9,height=2.7in,angle=-90}
+
+
\subsection{Compiler Flags}
Although NestedVM perfectly emulates a MIPS R2000 CPU, its performance
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:
+generally improve performance when using {\tt gcc} as the
+source-to-MIPS compiler:
\begin{itemize}
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.
+ the {\tt .text} segment is split on power-of-two boundaries due
+ to the trampoline. 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}
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.
+ of unavailability. NestedVM is under no such constraint, and
+ removing this reordering typically results in simpler bytecode.
\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
+ As explained in the previous 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
+ --gc-sections} 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.
+The following chart quantifies the performance gain conferred by each
+of the major optimizations outlined in this section:
+
+\epsfig{file=charts/chart10,height=2.7in,angle=-90}
+
+
+
+\subsection{Overall Performance}
-\epsfig{file=charts/chart4,width=3in}
+All times are measured in seconds. All tests were performed 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.
-\epsfig{file=charts/chart3,width=3in}
+\epsfig{file=charts/chart8,height=2.7in,angle=-90}
-\epsfig{file=charts/chart8,width=3in}
+\epsfig{file=charts/chart7,height=2.7in,angle=-90}
-\epsfig{file=charts/chart9,width=3in}
+\epsfig{file=charts/chart6,height=2.7in,angle=-90}
\section{Sample Applications}
equivalent exists. The first is the FreeType font library, which
parses, hints, and rasterizes TrueType and Postscript fonts with
exceptional quality. The project also needed an open source JPEG
-decompressor; surprisingly, none exist for Java. While encoders are
-plentiful
+decompresser; surprisingly, none exist for Java. While encoders are
+plentiful, decoders are rare, since Sun's J2SE VM includes a native
+method to invoke {\tt libjpeg}.
These three libraries make minimal use of the standard library and OS
services, and are all written in very portable ANSI C code, which made
\subsection{The GNU Compiler Collection}
-Our next target, {\tt gcc}, was chosen in order to relieve developers
-from the time-consuming and complex task of building a compiler
-themselves. The Ibex Project requires a specially configured and
-patched version of {\tt gcc} and its ahead-of-time Java compiler ({\tt
-gcj}) which is not distributed in binary form.
+Our next target, {\tt gcc}, was initially chosen in order to relieve
+developers from the time-consuming and complex task of building a
+compiler themselves; The Ibex Project requires a specially configured
+and patched version of {\tt gcc} and its ahead-of-time Java compiler
+({\tt gcj}) which is cumbersome to build.
-GCC was the first ``major'' application NestedVM was used on, and
-drove the development of most of the system library interface
+{\tt Gcc} was the first ``major'' application NestedVM was used on,
+and drove the development of most of the system library interface
development; particularly support for {\tt fork()} and {\tt exec()},
which require the NestedVM Runtime to perform binary-to-bytecode
translation on the fly.
-GCC also makes extensive use of 64-bit integers ({\tt long long}),
-which -- for performance reasons -- are typically manipulated using
-nonobvious instruction sequences on the 32-bit MIPS architecture.
-Dealing with these operations uncovered a number of bugs in the
-translator.
+{\tt Gcc} also makes extensive use of 64-bit integers ({\tt long
+long}), which -- for performance reasons -- are typically manipulated
+using nonobvious instruction sequences on the 32-bit MIPS
+architecture. Dealing with these operations uncovered a number of
+bugs in the translator.
Despite our original goal, we have not yet been able to translate the
{\tt C++} or Java front-ends, as the resulting binary produces a
work will explore a multi-level trampoline to address this issue.
-
\subsection{\TeX and LINPACK}
In order to distinguish NestedVM from other single-language
-translators for the JVM, we undertook the task of translating \TeX 89
+translators for the JVM, we undertook the task of translating \TeX\
(written in Pascal) and the Fortran source code for LINPACK into Java
bytecodes.
substitute wall-clock time on an otherwise-quiescent machine as an
approximation.
-
+\epsfig{file=charts/chart11,height=2.7in,angle=-90}
\section{Conclusion}
-\subsection{Theoretical Limitations}
-
-Theoretical limitations: threads, reading from code, self-modifying
-code, COW?
+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 and
+demonstrated its utility by translating six popular software
+applications.
\subsection{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
+particular we would like to demonstrate this generality by re-targeting
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.
+written in Java) and the {\tt ClassLoader.defineClass()} mechanism.
\subsection{Availability}
http://nestedvm.ibex.org
\end{verbatim}
-\appendix
-\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}
+\bibliography{ivme04}
\end{document}
projects / nestedvm.git / blobdiff