3 <title>Dalvik Optimization and Verification</title>
7 <h1>Dalvik Optimization and Verification With <i>dexopt</i></h1>
10 The Dalvik virtual machine was designed specifically for the Android
11 mobile platform. The target systems have little RAM, store data on slow
12 internal flash memory, and generally have the performance characteristics
13 of decade-old desktop systems. They also run Linux, which provides
14 virtual memory, processes and threads, and UID-based security mechanisms.
16 The features and limitations caused us to focus on certain goals:
19 <li>Class data, notably bytecode, must be shared between multiple
20 processes to minimize total system memory usage.
21 <li>The overhead in launching a new app must be minimized to keep
22 the device responsive.
23 <li>Storing class data in individual files results in a lot of
24 redundancy, especially with respect to strings. To conserve disk
25 space we need to factor this out.
26 <li>Parsing class data fields adds unnecessary overhead during
27 class loading. Accessing data values (e.g. integers and strings)
28 directly as C types is better.
29 <li>Bytecode verification is necessary, but slow, so we want to verify
30 as much as possible outside app execution.
31 <li>Bytecode optimization (quickened instructions, method pruning) is
32 important for speed and battery life.
33 <li>For security reasons, processes may not edit shared code.
37 The typical VM implementation uncompresses individual classes from a
38 compressed archive and stores them on the heap. This implies a separate
39 copy of each class in every process, and slows application startup because
40 the code must be uncompressed (or at least read off disk in many small
41 pieces). On the other hand, having the bytecode on the local heap makes
42 it easy to rewrite instructions on first use, facilitating a number of
43 different optimizations.
45 The goals led us to make some fundamental decisions:
48 <li>Multiple classes are aggregated into a single "DEX" file.
49 <li>DEX files are mapped read-only and shared between processes.
50 <li>Byte ordering and word alignment are adjusted to suit the local
52 <li>Bytecode verification is mandatory for all classes, but we want
53 to "pre-verify" whatever we can.
54 <li>Optimizations that require rewriting bytecode must be done ahead
59 The consequences of these decisions are explained in the following sections.
65 Application code is delivered to the system in a <code>.jar</code>
66 or <code>.apk</code> file. These are really just <code>.zip</code>
67 archives with some meta-data files added. The Dalvik DEX data file
68 is always called <code>classes.dex</code>.
70 The bytecode cannot be memory-mapped and executed directly from the zip
71 file, because the data is compressed and the start of the file is not
72 guaranteed to be word-aligned. These problems could be addressed by
73 storing <code>classes.dex</code> without compression and padding out the zip
74 file, but that would increase the size of the package sent across the
77 We need to extract <code>classes.dex</code> from the zip archive before
78 we can use it. While we have the file available, we might as well perform
79 some of the other actions (realignment, optimization, verification) described
80 earlier. This raises a new question however: who is responsible for doing
81 this, and where do we keep the output?
86 There are at least three different ways to create a "prepared" DEX file,
87 sometimes known as "ODEX" (for Optimized DEX):
89 <li>The VM does it "just in time". The output goes into a special
90 <code>dalvik-cache</code> directory. This works on the desktop and
91 engineering-only device builds where the permissions on the
92 <code>dalvik-cache</code> directory are not restricted. On production
93 devices, this is not allowed.
94 <li>The system installer does it when an application is first added.
95 It has the privileges required to write to <code>dalvik-cache</code>.
96 <li>The build system does it ahead of time. The relevant <code>jar</code>
97 / <code>apk</code> files are present, but the <code>classes.dex</code>
98 is stripped out. The optimized DEX is stored next to the original
99 zip archive, not in <code>dalvik-cache</code>, and is part of the
103 The <code>dalvik-cache</code> directory is more accurately
104 <code>$ANDROID_DATA/data/dalvik-cache</code>. The files inside it have
105 names derived from the full path of the source DEX. On the device the
106 directory is owned by <code>system</code> / <code>system</code>
107 and has 0771 permissions, and the optimized DEX files stored there are
108 owned by <code>system</code> and the
109 application's group, with 0644 permissions. DRM-locked applications will
110 use 640 permissions to prevent other user applications from examining them.
111 The bottom line is that you can read your own DEX file and those of most
112 other applications, but you cannot create, modify, or remove them.
114 Preparation of the DEX file for the "just in time" and "system installer"
115 approaches proceeds in three steps:
117 First, the dalvik-cache file is created. This must be done in a process
118 with appropriate privileges, so for the "system installer" case this is
119 done within <code>installd</code>, which runs as root.
121 Second, the <code>classes.dex</code> entry is extracted from the the zip
122 archive. A small amount of space is left at the start of the file for
125 Third, the file is memory-mapped for easy access and tweaked for use on
126 the current system. This includes byte-swapping and structure realigning,
127 but no meaningful changes to the DEX file. We also do some basic
128 structure checks, such as ensuring that file offsets and data indices
129 fall within valid ranges.
131 The build system uses a hairy process that involves starting the
132 emulator, forcing just-in-time optimization of all relevant DEX files,
133 and then extracting the results from <code>dalvik-cache</code>. The
134 reasons for doing this, rather than using a tool that runs on the desktop,
135 will become more apparent when the optimizations are explained.
137 Once the code is byte-swapped and aligned, we're ready to go. We append
138 some pre-computed data, fill in the ODEX header at the start of the file,
139 and start executing. (The header is filled in last, so that we don't
140 try to use a partial file.) If we're interested in verification and
141 optimization, however, we need to insert a step after the initial prep.
146 We want to verify and optimize all of the classes in the DEX file. The
147 easiest and safest way to do this is to load all of the classes into
148 the VM and run through them. Anything that fails to load is simply not
149 verified or optimized. Unfortunately, this can cause allocation of some
150 resources that are difficult to release (e.g. loading of native shared
151 libraries), so we don't want to do it in the same virtual machine that
152 we're running applications in.
154 The solution is to invoke a program called <code>dexopt</code>, which
155 is really just a back door into the VM. It performs an abbreviated VM
156 initialization, loads zero or more DEX files from the bootstrap class
157 path, and then sets about verifying and optimizing whatever it can from
158 the target DEX. On completion, the process exits, freeing all resources.
160 It is possible for multiple VMs to want the same DEX file at the same
161 time. File locking is used to ensure that dexopt is only run once.
164 <h2>Verification</h2>
167 The bytecode verification process involves scanning through the instructions
168 in every method in every class in a DEX file. The goal is to identify
169 illegal instruction sequences so that we don't have to check for them at
170 run time. Many of the computations involved are also necessary for "exact"
171 garbage collection. See
172 <a href="verifier.html">Dalvik Bytecode Verifier Notes</a> for more
175 For performance reasons, the optimizer (described in the next section)
176 assumes that the verifier has run successfully, and makes some potentially
177 unsafe assumptions. By default, Dalvik insists upon verifying all classes,
178 and only optimizes classes that have been verified. If you want to
179 disable the verifier, you can use command-line flags to do so. See also
180 <a href="embedded-vm-control.html"> Controlling the Embedded VM</a>
181 for instructions on controlling these
182 features within the Android application framework.
184 Reporting of verification failures is a tricky issue. For example,
185 calling a package-scope method on a class in a different package is
186 illegal and will be caught by the verifier. We don't necessarily want
187 to report it during verification though -- we actually want to throw
188 an exception when the method call is attempted. Checking the access
189 flags on every method call is expensive though. The
190 <a href="verifier.html">Dalvik Bytecode Verifier Notes</a> document
191 addresses this issue.
193 Classes that have been verified successfully have a flag set in the ODEX.
194 They will not be re-verified when loaded. The Linux access permissions
195 are expected to prevent tampering; if you can get around those, installing
196 faulty bytecode is far from the easiest line of attack. The ODEX file has
197 a 32-bit checksum, but that's chiefly present as a quick check for
201 <h2>Optimization</h2>
204 Virtual machine interpreters typically perform certain optimizations the
205 first time a piece of code is used. Constant pool references are replaced
206 with pointers to internal data structures, operations that always succeed
207 or always work a certain way are replaced with simpler forms. Some of
208 these require information only available at runtime, others can be inferred
209 statically when certain assumptions are made.
211 The Dalvik optimizer does the following:
213 <li>For virtual method calls, replace the method index with a
215 <li>For instance field get/put, replace the field index with
216 a byte offset. Also, merge the boolean / byte / char / short
217 variants into a single 32-bit form (less code in the interpreter
218 means more room in the CPU I-cache).
219 <li>Replace a handful of high-volume calls, like String.length(),
220 with "inline" replacements. This skips the usual method call
221 overhead, directly switching from the interpreter to a native
223 <li>Prune empty methods. The simplest example is
224 <code>Object.<init></code>, which does nothing, but must be
225 called whenever any object is allocated. The instruction is
226 replaced with a new version that acts as a no-op unless a debugger
228 <li>Append pre-computed data. For example, the VM wants to have a
229 hash table for lookups on class name. Instead of computing this
230 when the DEX file is loaded, we can compute it now, saving heap
231 space and computation time in every VM where the DEX is loaded.
235 All of the instruction modifications involve replacing the opcode with
236 one not defined by the Dalvik specification. This allows us to freely
237 mix optimized and unoptimized instructions. The set of optimized
238 instructions, and their exact representation, is tied closely to the VM
241 Most of the optimizations are obvious "wins". The use of raw indices
242 and offsets not only allows us to execute more quickly, we can also
243 skip the initial symbolic resolution. Pre-computation eats up
244 disk space, and so must be done in moderation.
246 There are a couple of potential sources of trouble with these
247 optimizations. First, vtable indices and byte offsets are subject to
248 change if the VM is updated. Second, if a superclass is in a different
249 DEX, and that other DEX is updated, we need to ensure that our optimized
250 indices and offsets are updated as well. A similar but more subtle
251 problem emerges when user-defined class loaders are employed: the class
252 we actually call may not be the one we expected to call.
253 <p>These problems are addressed with dependency lists and some limitations
254 on what can be optimized.
257 <h2>Dependencies and Limitations</h2>
260 The optimized DEX file includes a list of dependencies on other DEX files,
261 plus the CRC-32 and modification date from the originating
262 <code>classes.dex</code> zip file entry. The dependency list includes the
263 full path to the <code>dalvik-cache</code> file, and the file's SHA-1
264 signature. The timestamps of files on the device are unreliable and
265 not used. The dependency area also includes the VM version number.
267 An optimized DEX is dependent upon all of the DEX files in the bootstrap
268 class path. DEX files that are part of the bootstrap class path depend
269 upon the DEX files that appeared earlier. To ensure that nothing outside
270 the dependent DEX files is available, <code>dexopt</code> only loads the
271 bootstrap classes. References to classes in other DEX files fail, which
272 causes class loading and/or verification to fail, and classes with
273 external dependencies are simply not optimized.
275 This means that splitting code out into many separate DEX files has a
276 disadvantage: virtual method calls and instance field lookups between
277 non-boot DEX files can't be optimized. Because verification is pass/fail
278 with class granularity, no method in a class that has any reliance on
279 classes in external DEX files can be optimized. This may be a bit
280 heavy-handed, but it's the only way to guarantee that nothing breaks
281 when individual pieces are updated.
283 Another negative consequence: any change to a bootstrap DEX will result
284 in rejection of all optimized DEX files. This makes it hard to keep
285 system updates small.
287 Despite our caution, there is still a possibility that a class in a DEX
288 file loaded by a user-defined class loader could ask for a bootstrap class
289 (say, String) and be given a different class with the same name. If a
290 class in the DEX file being processed has the same name as a class in the
291 bootstrap DEX files, the class will be flagged as ambiguous and references
292 to it will not be resolved during verification / optimization. The class
293 linking code in the VM does additional checks to plug another hole;
294 see the verbose description in the VM sources for details (vm/oo/Class.c).
296 If one of the dependencies is updated, we need to re-verify and
297 re-optimize the DEX file. If we can do a just-in-time <code>dexopt</code>
298 invocation, this is easy. If we have to rely on the installer daemon, or
299 the DEX was shipped only in ODEX, then the VM has to reject the DEX.
301 The output of <code>dexopt</code> is byte-swapped and struct-aligned
302 for the host, and contains indices and offsets that are highly VM-specific
303 (both version-wise and platform-wise). For this reason it's tricky to
304 write a version of <code>dexopt</code> that runs on the desktop but
305 generates output suitable for a particular device. The safest way to
306 invoke it is on the target device, or on an emulator for that device.
309 <h2>Generated DEX</h2>
312 Some languages and frameworks rely on the ability to generate bytecode
313 and execute it. The rather heavy <code>dexopt</code> verification and
314 optimization model doesn't work well with that.
316 We intend to support this in a future release, but the exact method is
317 to be determined. We may allow individual classes to be added or whole
318 DEX files; may allow Java bytecode or Dalvik bytecode in instructions;
319 may perform the usual set of optimizations, or use a separate interpreter
320 that performs on-first-use optimizations directly on the bytecode (which
321 won't be mapped read-only, since it's locally defined).
323 <address>Copyright © 2008 The Android Open Source Project</address>
OSDN Git Service
