You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
326 lines
15 KiB
326 lines
15 KiB
<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>
|
|
|