\maketitle
-{\it This document was typeset using D. E. Knuth's original \TeX 89
- Pascal source code, which was both compiled and executed entirely
- within a Java Virtual Machine. No native code was utilized.}
+{\it This document was typeset using D. E. Knuth's original \TeX 89,
+ which was both compiled and executed entirely within a Java
+ Virtual Machine without the use of native code.}
\begin{abstract}
-Most existing techniques for using code written in an unsafe language
-within a safe virtual machine involve transformations from one source
-code language (such as C, Pascal, or Fortran) to another (such as
-Java) and then to virtual machine bytecodes. We present an
-alternative approach which can translate MIPS binaries produced by any
-compiler into safe virtual machine bytecodes. This approach offers
-four key advantages over existing techniques:
+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.
+
+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 No build process modifications
\end{itemize}
-We also present NestedVM, a complete implementation of this technique,
-which we have used to translate a number of programs. Six examples
-are discussed in this paper: LINPACK (Fortran source), which was used
-as one of our performance tests, \TeX (Pascal source), which was used
-to typeset this document, {\tt libjpeg}, {\tt libmspack}, and FreeType
-(all C source), which are currently in production use as part of the
-Ibex Project, and {\tt gcc}, which was used to compile all of the
-aforementioned.
+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.
Performance measurements indicate a best case performance within 3x of
native code and worst case typically within 10x, making it an
The primary occupant of this category is {\tt egcs-jvm}
\cite{egcsjvm}, an experimental ``JVM backend'' for the GNU Compiler
-Collection ( {\tt gcc} ) \cite{gcc}. Since {\tt gcc} employs a highlym
-odular architecture, it {\it is} possible to add RTL code generators
+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.
+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.
\section{NestedVM}
This leads immediately to three advantages:
\begin{itemize}
-\item {\bf Total coverage of all language features}
+\item {\bf Language Agnostic}
Because NestedVM does not attempt to implement the parsing and
code generation steps of compilation, it is freed from the
extremely complex task of faithfully implementing languages
which are often not fully or formally specified (such as C and
- C++).
-
-\item {\bf No build process modifications}
-
- NestedVM does not modify existing build processes, which can be
- extremely complex and dependent on strange preprocessor usage as
- well as the complex interplay between compiler switches and
- header file locations.
+ C++), and is able to support any langage for which a
+ MIPS-targeted compiler exists.
\item {\bf Bug-for-bug compiler compatability}
dependent on the vagaries of a particular compiler can still be
used.
+\item {\bf No build process modifications}
+
+ NestedVM does not modify existing build processes, which can be
+ extremely complex and dependent on strange preprocessor usage as
+ well as the complex interplay between compiler switches and
+ header file locations.
+
\end{itemize}
NestedVM's approach carries a fourth benefit as well, arising from its
We chose MIPS as a source format for three reasons: the availability
of tools to compile legacy code into MIPS binaries, the close
-similarity between the MIPS ISA and the Java Virtual Machine, and the
-relatively high degree of program structure that can be inferred from
-ABI-adherent binaries.
+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.
The MIPS architecture has been around for quite some time, and is well
supported by the GNU Compiler Collection, which is capable of
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
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.
-
+ 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}
\epsfig{file=chart3,width=3in}
+\section{Experiences}
+
+\subsection{FreeType, {\tt libmspack}, and {\tt libjpeg}}
+
+The Ibex Project utilizes three libraries for which no Java-only
+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
+
+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
+them easy targets for initial development.
+
+\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.
+
+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.
+
+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
+trampoline which exceeds the maximum size of a single method. Future
+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
+(written in Pascal) and the Fortran source code for LINPACK into Java
+bytecodes.
+
+Although actually producing the initial MIPS binaries from the \TeX\
+source code turned out to be an exceptionally tedious and frustrating
+task, the resulting binary translated and executed perfectly on the
+first run, as did LINPACK. Our reward for this effort was typesetting
+our presentation of NestedVM using NestedVM itself. We have also had
+initial successes running \TeX\ in a Java Applet, and intend to
+produce a {\tt jar} for embedding \TeX\ code (``\TeX lets'') in web
+pages without the use of a post-processing tool.
+
+The LINPACK benchmark called our attention to Java's lack of an API
+for checking the ``cpu time'' of a process. Unfortunately we had to
+substitute wall-clock time on an otherwise-quiescent machine as an
+approximation.
+
+
+
\section{The NestedVM Runtime}
In addition to binary-to-source and binary-to-binary translation,
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:
+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
+{\tt SYSCALL} instruction, just as the {\tt libc}-kernel interface is
+on real 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 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.
+
+The {\tt exit()} call records the 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.
+
+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.
+
+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 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 {\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
+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.
+
+
+\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)
+
+
+\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.
+
+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.
+
+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
+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.
+
+Theoretical limitations: threads, reading from code, self-modifying
+code, COW?
-\begin{itemize}
-
-\item It provides a simple, consistent external interface. The method
- of actually executing the code (currently only translated
- binaries and the interpreter) can be changed without any code
- changes to the caller because only runtime exposes a public
- interface. This includes methods to pass arguments to the
- binary's {\tt main()} function, read and write from memory, and
- call individual functions in the binary.
-
-\item It manages the process's memory. The runtime class contains
- large {\tt int[]} arrays that represent the process`s entire
- memory space. Subclasses read and write to these arrays as
- required by the instructions they are executing, and can expand
- their memory space using the {\tt sbrk} system call.
-
-\item The runtime provides access to the host file system and standard
- I/O streams. Subclasses of {\tt runtime} can access the file
- system through standard UNIX syscalls ({\tt read()}, {\tt
- write()}, {\tt open()}, etc). The runtime manages the file
- descriptor table that maps UNIX file descriptors to Java {\tt
- RandomAccessFile}s, {\tt InputStream}s, {\tt OutputStream}s, and
- {\tt Socket}s.
-
-\item It provides general OS services, including {\tt sleep()}, {\tt
- gettimeofday()}, {\tt getpagesize()}, {\tt sysconf()}, {\tt
- fcntl()}, and so on.
-
-\end{itemize}
\section{Future Directions}
projects / nestedvm.git / blobdiff