| <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> |