auto import from //depot/cupcake/@135843
diff --git a/docs/dexopt.html b/docs/dexopt.html
new file mode 100644
index 0000000..7f0b4bc
--- /dev/null
+++ b/docs/dexopt.html
@@ -0,0 +1,326 @@
+<html>
+<head>
+ <title>Dalvik Optimization and Verification</title>
+</head>
+
+<body>
+<h1>Dalvik Optimization and Verification With <i>dexopt</i></h1>
+
+<p>
+The Dalvik virtual machine was designed specifically for the Android
+mobile platform. The target systems have little RAM, store data on slow
+internal flash memory, and generally have the performance characteristics
+of decade-old desktop systems. They also run Linux, which provides
+virtual memory, processes and threads, and UID-based security mechanisms.
+<p>
+The features and limitations caused us to focus on certain goals:
+
+<ul>
+ <li>Class data, notably bytecode, must be shared between multiple
+ processes to minimize total system memory usage.
+ <li>The overhead in launching a new app must be minimized to keep
+ the device responsive.
+ <li>Storing class data in individual files results in a lot of
+ redundancy, especially with respect to strings. To conserve disk
+ space we need to factor this out.
+ <li>Parsing class data fields adds unnecessary overhead during
+ class loading. Accessing data values (e.g. integers and strings)
+ directly as C types is better.
+ <li>Bytecode verification is necessary, but slow, so we want to verify
+ as much as possible outside app execution.
+ <li>Bytecode optimization (quickened instructions, method pruning) is
+ important for speed and battery life.
+ <li>For security reasons, processes may not edit shared code.
+</ul>
+
+<p>
+The typical VM implementation uncompresses individual classes from a
+compressed archive and stores them on the heap. This implies a separate
+copy of each class in every process, and slows application startup because
+the code must be uncompressed (or at least read off disk in many small
+pieces). On the other hand, having the bytecode on the local heap makes
+it easy to rewrite instructions on first use, facilitating a number of
+different optimizations.
+<p>
+The goals led us to make some fundamental decisions:
+
+<ul>
+ <li>Multiple classes are aggregated into a single "DEX" file.
+ <li>DEX files are mapped read-only and shared between processes.
+ <li>Byte ordering and word alignment are adjusted to suit the local
+ system.
+ <li>Bytecode verification is mandatory for all classes, but we want
+ to "pre-verify" whatever we can.
+ <li>Optimizations that require rewriting bytecode must be done ahead
+ of time.
+</ul>
+
+<p>
+The consequences of these decisions are explained in the following sections.
+
+
+<h2>VM Operation</h2>
+
+<p>
+Application code is delivered to the system in a <code>.jar</code>
+or <code>.apk</code> file. These are really just <code>.zip</code>
+archives with some meta-data files added. The Dalvik DEX data file
+is always called <code>classes.dex</code>.
+<p>
+The bytecode cannot be memory-mapped and executed directly from the zip
+file, because the data is compressed and the start of the file is not
+guaranteed to be word-aligned. These problems could be addressed by
+storing <code>classes.dex</code> without compression and padding out the zip
+file, but that would increase the size of the package sent across the
+data network.
+<p>
+We need to extract <code>classes.dex</code> from the zip archive before
+we can use it. While we have the file available, we might as well perform
+some of the other actions (realignment, optimization, verification) described
+earlier. This raises a new question however: who is responsible for doing
+this, and where do we keep the output?
+
+<h3>Preparation</h3>
+
+<p>
+There are at least three different ways to create a "prepared" DEX file,
+sometimes known as "ODEX" (for Optimized DEX):
+<ol>
+ <li>The VM does it "just in time". The output goes into a special
+ <code>dalvik-cache</code> directory. This works on the desktop and
+ engineering-only device builds where the permissions on the
+ <code>dalvik-cache</code> directory are not restricted. On production
+ devices, this is not allowed.
+ <li>The system installer does it when an application is first added.
+ It has the privileges required to write to <code>dalvik-cache</code>.
+ <li>The build system does it ahead of time. The relevant <code>jar</code>
+ / <code>apk</code> files are present, but the <code>classes.dex</code>
+ is stripped out. The optimized DEX is stored next to the original
+ zip archive, not in <code>dalvik-cache</code>, and is part of the
+ system image.
+</ol>
+<p>
+The <code>dalvik-cache</code> directory is more accurately
+<code>$ANDROID_DATA/data/dalvik-cache</code>. The files inside it have
+names derived from the full path of the source DEX. On the device the
+directory is owned by <code>system</code> / <code>system</code>
+and has 0771 permissions, and the optimized DEX files stored there are
+owned by <code>system</code> and the
+application's group, with 0644 permissions. DRM-locked applications will
+use 640 permissions to prevent other user applications from examining them.
+The bottom line is that you can read your own DEX file and those of most
+other applications, but you cannot create, modify, or remove them.
+<p>
+Preparation of the DEX file for the "just in time" and "system installer"
+approaches proceeds in three steps:
+<p>
+First, the dalvik-cache file is created. This must be done in a process
+with appropriate privileges, so for the "system installer" case this is
+done within <code>installd</code>, which runs as root.
+<p>
+Second, the <code>classes.dex</code> entry is extracted from the the zip
+archive. A small amount of space is left at the start of the file for
+the ODEX header.
+<p>
+Third, the file is memory-mapped for easy access and tweaked for use on
+the current system. This includes byte-swapping and structure realigning,
+but no meaningful changes to the DEX file. We also do some basic
+structure checks, such as ensuring that file offsets and data indices
+fall within valid ranges.
+<p>
+The build system uses a hairy process that involves starting the
+emulator, forcing just-in-time optimization of all relevant DEX files,
+and then extracting the results from <code>dalvik-cache</code>. The
+reasons for doing this, rather than using a tool that runs on the desktop,
+will become more apparent when the optimizations are explained.
+<p>
+Once the code is byte-swapped and aligned, we're ready to go. We append
+some pre-computed data, fill in the ODEX header at the start of the file,
+and start executing. (The header is filled in last, so that we don't
+try to use a partial file.) If we're interested in verification and
+optimization, however, we need to insert a step after the initial prep.
+
+<h3>dexopt</h3>
+
+<p>
+We want to verify and optimize all of the classes in the DEX file. The
+easiest and safest way to do this is to load all of the classes into
+the VM and run through them. Anything that fails to load is simply not
+verified or optimized. Unfortunately, this can cause allocation of some
+resources that are difficult to release (e.g. loading of native shared
+libraries), so we don't want to do it in the same virtual machine that
+we're running applications in.
+<p>
+The solution is to invoke a program called <code>dexopt</code>, which
+is really just a back door into the VM. It performs an abbreviated VM
+initialization, loads zero or more DEX files from the bootstrap class
+path, and then sets about verifying and optimizing whatever it can from
+the target DEX. On completion, the process exits, freeing all resources.
+<p>
+It is possible for multiple VMs to want the same DEX file at the same
+time. File locking is used to ensure that dexopt is only run once.
+
+
+<h2>Verification</h2>
+
+<p>
+The bytecode verification process involves scanning through the instructions
+in every method in every class in a DEX file. The goal is to identify
+illegal instruction sequences so that we don't have to check for them at
+run time. Many of the computations involved are also necessary for "exact"
+garbage collection. See
+<a href="verifier.html">Dalvik Bytecode Verifier Notes</a> for more
+information.
+<p>
+For performance reasons, the optimizer (described in the next section)
+assumes that the verifier has run successfully, and makes some potentially
+unsafe assumptions. By default, Dalvik insists upon verifying all classes,
+and only optimizes classes that have been verified. If you want to
+disable the verifier, you can use command-line flags to do so. See also
+<a href="embedded-vm-control.html"> Controlling the Embedded VM</a>
+for instructions on controlling these
+features within the Android application framework.
+<p>
+Reporting of verification failures is a tricky issue. For example,
+calling a package-scope method on a class in a different package is
+illegal and will be caught by the verifier. We don't necessarily want
+to report it during verification though -- we actually want to throw
+an exception when the method call is attempted. Checking the access
+flags on every method call is expensive though. The
+<a href="verifier.html">Dalvik Bytecode Verifier Notes</a> document
+addresses this issue.
+<p>
+Classes that have been verified successfully have a flag set in the ODEX.
+They will not be re-verified when loaded. The Linux access permissions
+are expected to prevent tampering; if you can get around those, installing
+faulty bytecode is far from the easiest line of attack. The ODEX file has
+a 32-bit checksum, but that's chiefly present as a quick check for
+corrupted data.
+
+
+<h2>Optimization</h2>
+
+<p>
+Virtual machine interpreters typically perform certain optimizations the
+first time a piece of code is used. Constant pool references are replaced
+with pointers to internal data structures, operations that always succeed
+or always work a certain way are replaced with simpler forms. Some of
+these require information only available at runtime, others can be inferred
+statically when certain assumptions are made.
+<p>
+The Dalvik optimizer does the following:
+<ul>
+ <li>For virtual method calls, replace the method index with a
+ vtable index.
+ <li>For instance field get/put, replace the field index with
+ a byte offset. Also, merge the boolean / byte / char / short
+ variants into a single 32-bit form (less code in the interpreter
+ means more room in the CPU I-cache).
+ <li>Replace a handful of high-volume calls, like String.length(),
+ with "inline" replacements. This skips the usual method call
+ overhead, directly switching from the interpreter to a native
+ implementation.
+ <li>Prune empty methods. The simplest example is
+ <code>Object.<init></code>, which does nothing, but must be
+ called whenever any object is allocated. The instruction is
+ replaced with a new version that acts as a no-op unless a debugger
+ is attached.
+ <li>Append pre-computed data. For example, the VM wants to have a
+ hash table for lookups on class name. Instead of computing this
+ when the DEX file is loaded, we can compute it now, saving heap
+ space and computation time in every VM where the DEX is loaded.
+</ul>
+
+<p>
+All of the instruction modifications involve replacing the opcode with
+one not defined by the Dalvik specification. This allows us to freely
+mix optimized and unoptimized instructions. The set of optimized
+instructions, and their exact representation, is tied closely to the VM
+version.
+<p>
+Most of the optimizations are obvious "wins". The use of raw indices
+and offsets not only allows us to execute more quickly, we can also
+skip the initial symbolic resolution. Pre-computation eats up
+disk space, and so must be done in moderation.
+<p>
+There are a couple of potential sources of trouble with these
+optimizations. First, vtable indices and byte offsets are subject to
+change if the VM is updated. Second, if a superclass is in a different
+DEX, and that other DEX is updated, we need to ensure that our optimized
+indices and offsets are updated as well. A similar but more subtle
+problem emerges when user-defined class loaders are employed: the class
+we actually call may not be the one we expected to call.
+<p>These problems are addressed with dependency lists and some limitations
+on what can be optimized.
+
+
+<h2>Dependencies and Limitations</h2>
+
+<p>
+The optimized DEX file includes a list of dependencies on other DEX files,
+plus the CRC-32 and modification date from the originating
+<code>classes.dex</code> zip file entry. The dependency list includes the
+full path to the <code>dalvik-cache</code> file, and the file's SHA-1
+signature. The timestamps of files on the device are unreliable and
+not used. The dependency area also includes the VM version number.
+<p>
+An optimized DEX is dependent upon all of the DEX files in the bootstrap
+class path. DEX files that are part of the bootstrap class path depend
+upon the DEX files that appeared earlier. To ensure that nothing outside
+the dependent DEX files is available, <code>dexopt</code> only loads the
+bootstrap classes. References to classes in other DEX files fail, which
+causes class loading and/or verification to fail, and classes with
+external dependencies are simply not optimized.
+<p>
+This means that splitting code out into many separate DEX files has a
+disadvantage: virtual method calls and instance field lookups between
+non-boot DEX files can't be optimized. Because verification is pass/fail
+with class granularity, no method in a class that has any reliance on
+classes in external DEX files can be optimized. This may be a bit
+heavy-handed, but it's the only way to guarantee that nothing breaks
+when individual pieces are updated.
+<p>
+Another negative consequence: any change to a bootstrap DEX will result
+in rejection of all optimized DEX files. This makes it hard to keep
+system updates small.
+<p>
+Despite our caution, there is still a possibility that a class in a DEX
+file loaded by a user-defined class loader could ask for a bootstrap class
+(say, String) and be given a different class with the same name. If a
+class in the DEX file being processed has the same name as a class in the
+bootstrap DEX files, the class will be flagged as ambiguous and references
+to it will not be resolved during verification / optimization. The class
+linking code in the VM does additional checks to plug another hole;
+see the verbose description in the VM sources for details (vm/oo/Class.c).
+<p>
+If one of the dependencies is updated, we need to re-verify and
+re-optimize the DEX file. If we can do a just-in-time <code>dexopt</code>
+invocation, this is easy. If we have to rely on the installer daemon, or
+the DEX was shipped only in ODEX, then the VM has to reject the DEX.
+<p>
+The output of <code>dexopt</code> is byte-swapped and struct-aligned
+for the host, and contains indices and offsets that are highly VM-specific
+(both version-wise and platform-wise). For this reason it's tricky to
+write a version of <code>dexopt</code> that runs on the desktop but
+generates output suitable for a particular device. The safest way to
+invoke it is on the target device, or on an emulator for that device.
+
+
+<h2>Generated DEX</h2>
+
+<p>
+Some languages and frameworks rely on the ability to generate bytecode
+and execute it. The rather heavy <code>dexopt</code> verification and
+optimization model doesn't work well with that.
+<p>
+We intend to support this in a future release, but the exact method is
+to be determined. We may allow individual classes to be added or whole
+DEX files; may allow Java bytecode or Dalvik bytecode in instructions;
+may perform the usual set of optimizations, or use a separate interpreter
+that performs on-first-use optimizations directly on the bytecode (which
+won't be mapped read-only, since it's locally defined).
+
+<address>Copyright © 2008 The Android Open Source Project</address>
+
+</body>
+</html>