\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.}
\begin{abstract}
-FIXME: mention unsigned arithmetic, threading, memory model.
-
Existing techniques for using code written in an unsafe language
within a safe virtual machine generally involve transformations from
one source code language (such as C, Pascal, or Fortran) to another
-(such as Java) which is the compiled into virtual machine bytecodes.
+(such as Java) which is then compiled into virtual machine bytecodes.
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:
-
-\begin{itemize}
-\item Language-agnostic
-\item Bug-for-bug compiler compatability
-\item No post-translation human intervention
-\item No build process modifications
-\end{itemize}
+approach offers four key advantages over existing techniques: it is
+language agnostic, it offers bug-for-bug compiler compatability,
+requires no post-translation human intervention, and introduces no
+build process modifications.
We also present NestedVM, an implementation of this technique, and
-discuss six examples: LINPACK (Fortran), 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.
+discuss its application to six software packages: LINPACK (Fortran),
+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 \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
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.
+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
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
+Security is often a major concern when integrating native code. Using
+Java as an example, JNI and CNI are prohibited in a number of
+contexts, including applet 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.
+verified, bounds-checked 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.
+ahead of time for every architecture on which it will be deployed.
+This is unacceptable for scenarios 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}.
+other secure virtual machines such as Microsoft's .NET \cite{msil},
+Perl Parrot \cite{parrot}, or Python bytecode \cite{python}.
+
+The remainder of this paper is divided as follows: in the next section
+we review the relevant set of program representations (safe source,
+unsafe source, binary, and bytecode) and survey existing work for
+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
+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
+for future improvements.
+
-\section{Approaches to Translation}
+\section{Existing Work}
The four program representations of interest in this context, along
with their specific types in the C-to-JVM instantiation of the
\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}
+Existing techniques for translating unsafe code into VM bytecode
+generally fall into two categories, which we expand upon in the
+remainder of this section: source-to-source translation and
+source-to-binary translation.
\subsection{Source-to-Source Translation}
total translation but fail (yield an error) on a large class of input
programs.
-
-\subsubsection{Incomplete Translation}
+\subsubsection{Human-Assisted 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.
+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; indeed, Jazillian's
+documentation notes that {\it ``This is not your father's language
+translator... 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 {\tt c2j} \cite{c2j}, {\tt 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
\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 highly
-modular 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.
+An experimental ``JVM backend'' for the {\tt gcc} compiler, known as
+{\tt egcs-jvm} \cite{egcsjvm}, attempts this approach. Since {\tt
+gcc} employs a highly modular 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.
A Java backend for the {\tt lcc} [CITE] compiler, known as {\tt
-lcc-java} [CITE], but was not completed. {\tt lcc-java} also 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 sources. Finally, {\tt lcc-java}'s memory model is
-much more restricted; it uses a fixed-size array to represent all
-memory, and expands the array by allocating a new array and copying,
-which is extremely inefficient. No attempt is made to take advantage
-of {\tt NullPointerException} checking (which costs nothing if the
-exception is not thrown since most JVMs use the MMU to detect this).
-Finally, {\tt lcc-java} targets Java source code, which places the
-vast majority of NestedVM's optimizations beyond its reach, and
-severely restricts the maximum program size {\tt lcc-java} can handle.
-
-Finally, {\tt lcc-java} maintains a separate memory area for the
-stack, which appears to limit the exchange of stack pointers and heap
-pointers. It is unclear from the documentation how this is handled.
+lcc-java} [CITE], 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
+sources). The memory model employed by {\tt lcc-java} is also
+somewhat awkward; a separate {\tt int[]} is maintained for the stack
+and heap, leading to difficulties mingling pointers to these two
+memory regions. Additionally, the heap is a single {\tt int[]}, which
+means that it must be copied in order to be expanded, and prevents
+{\tt lcc-java} from taking advantage of {\tt NullPointerException}
+checking, which costs nothing in the ``common case'' since nearly all
+JVMs use the host CPU's MMU to detect this condition.
\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:
+NestedVM {\it does not} attempt to deal with source code as an input,
+instead opting for {\it binary-to-source} and {\it binary-to-binary}
+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
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,width=3in}
+
+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
\begin{multicols}{2}
{\footnotesize\begin{verbatim}
private final static int r0 = 0;
-private int r1, r2, r3,...,r30;
+private int r1, r2, r3, /* ... */ r30;
private int r31 = 0xdeadbeef;
private int pc = ENTRY_POINT;
public void run() {
- for(;;) {
+ while (true)
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 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);
- }
- }
-}
+ case 0xdeadbeef: 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;
- ...
- }
- }
-}
+ while (true) switch(pc) {
+ case 0x10000: ...
+ case 0x10004: ...
+ case 0x10010: r31 = 0x10018;
+ pc = 0x10210;
+ continue;
+....
pubic void run_0x10200() {
- for(;;) {
- switch(pc) {
- case 0x10200:
- ...
- case 0x10204:
- ...
- }
- }
-}
+ while (true) 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:
- ...
- }
- }
-}
+ while (true) switch(pc&0xfffffe00) {
+ case 0x10000: run_0x10000(); break;
+ case 0x10200: run_0x10200(); break;
+ case 0xdeadbe00: ...
+....
\end{verbatim}}
\end{multicols}
\end{minipage}
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 {\tt NestedVM} is invoked on the statically linked binary, and
+ emits a {\tt .java} file.
+
+\item The resulting {\tt .java} code is compiled into a {\tt .class}
+ file using {\tt jikes} \cite{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}
-\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.
+
+\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}}
+\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 Invoke {\tt NestedVM} on the statically linked binary.
+\item There are quite a few interesting bytecode sequences that cannot
+ be generated as a result of compiling Java source code.
-\item Compile the resulting {\tt .java} code using {\tt jikes}
- \cite{jikes} or {\tt javac}.
+\item Directly generating {\tt .class} files Eliminates the
+ time-consuming {\tt javac} step.
-\item From java code, invoke the {\tt run()} method on the generated
- class. This is equivalent to the {\tt main()} entry point.
+\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}
-\end{enumerate}
-\subsubsection{Optimizations}
+\section{The NestedVM Runtime}
+
+The NestedVM runtime fills the role typically assmed 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 other MIPS implementations.
+
+Two implemenations 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.
+
+\subsection{The ANSI C Runtime}
+
+The ANSI C runtime offers typical file I/O operations including {\tt
+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 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.
+
+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 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
+implemented by a Java class, which could, for example, offer access to
+the host filesystem (including {\tt state()}, {\tt lstat()}, {\tt
+mkdir}, and {\tt unlink()}, and {\tt getdents()}), the contents of a
+zip archive, or even a remote HTTP server.
+
+The {\tt fork()} call is implemented in an elegant manner by calling
+the Java {\tt clone()} method (deep copy) on the VM object itself.
+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 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 yet fully
+compatible with the standard Berkeley sockets API.
+
+
+\subsection{Security Concerns}
+
+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{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} 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 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}
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,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
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}
+\epsfig{file=charts/chart1,width=3in}
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 exraneous 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}
directly to {\tt .class} files (without the intermediate {\tt .java}
file) eliminates this problem entirely.
+\subsection{Binary-to-Binary Mode}
-\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.
+Compiling directly to bytecode offers a substantial performance gain:
-\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=charts/chart3,width=3in}
-\epsfig{file=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.
-\subsubsection{Compiler Flags}
+The net result is quite reasonably sized {\tt .class} files:
+
+\epsfig{file=charts/chart9,width=3in}
+
+
+\subsection{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:
+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.
+\subsection{Overall Performance}
-\epsfig{file=chart4,width=3in}
+\epsfig{file=charts/chart8,width=3in}
-\epsfig{file=chart3,width=3in}
+\epsfig{file=charts/chart7,width=3in}
-\section{Experiences}
+\epsfig{file=charts/chart6,width=3in}
+
+\section{Sample Applications}
\subsection{FreeType, {\tt libmspack}, and {\tt libjpeg}}
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
+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.
approximation.
+\section{Conclusion}
-\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}
+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.
-\section{Future Directions}
+\subsection{Future Directions}
Although we have only implemented it for the Java Virtual Machine, our
technique generalizes to other safe bytecode architectures. In
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.
-
-\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.
+\subsection{Availability}
NestedVM is available under an open source license, and can be
obtained from
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.
+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
projects / nestedvm.git / blobdiff