JAX London 2014: A retrospective
Technical, security and legal motivations behind its creation

Android Dalvik Virtual Machine

FrankMaker
Android-Dalvik-Virtual-Machine

Handy Codeworks’ Frank Maker takes us on a tour through Google’s VM.

The success of any modern smartphone platform is highly contingent on its ability to attract developers to the platform and drive sales of the corresponding hardware. Android has been widely successful in this respect in large part due to the use of Java as its primary language (The android-scripting project enables scripting languages to target Dalvik bytecode and recently full support has been added to the Native Development Toolkit (NDK) for C/C++.). Google chose Java because of the large community of developers (at the time of writing, Java is currently #1 in the TIOBE index) and relative ease of use compared to other mobile languages such as C++ (Symbian) and Objective-C (iPhone).

However, Dalvik is in fact not a true Java platform. Android uses the Java language and open source Apache Harmony libraries (in addition to their own) to generate standard classfiles in Java virtual machine (JVM) bytecode. These classfiles are then translated into Dalvik bytecode and stored in a single dex file. This means that not all Java code can be ported directly to Dalvik. Although, in practice much of it can be, since the majority of the J2SE standard libraries are available, with the notable exceptions of Swing and AWT. So you might be asking yourself, why reinvent the wheel? We already have J2SE and J2ME both of which seem adequate. Google’s motivation behind Dalvik is, in fact, based on multiple factors:

Limited Resources

Smartphone systems are very different from their desktop or laptop cousins. There are three main differences that drive design decisions: battery power, passive cooling and small form factor. Reliance on batteries means that energy is at a premium and must be conserved aggressively. Passive cooling limits the amount of power that can be used at any given time to avoid causing the device to become unacceptably hot. Lastly, the small form factor places price pressures on the component sizes of system components and limits the amount of feasible battery storage. To make matters worse, battery density growth, that is the amount of energy for a given volume, has not kept pace with advancements in mobile hardware technology.

This disparity leads to a system that can easily run out of memory or deplete the battery, if not managed appropriately. For example, a low-end Android phone (Table 1) has a relatively slow ARM processor with a clock speed in the range of 500 MHz, without floating point support, a small amount of RAM, often as low as 128MB, no operating system swap space and relatively limited external flash storage (usually NAND), and more importantly, a moderately slow read time. Clearly, we cannot simply use the same virtual machine as a desktop or laptop computer with vastly greater capability.

J2ME’s Problems

Given these limited resources, J2ME would seem to be the ideal choice for the platform. Unfortunately, J2ME is in fact dated with its own share of drawbacks. Many profiles and extensions that are optional for the platform cause key features of modern smartphone apps, such as Bluetooth, SIP and 3D graphics for example, to be available only on a subset of J2ME phones. This heterogeneity is unattractive to application developers in comparison to platforms such as iPhone and Android where most features are supported by all phones for a given version of the operating system. Even if this challenge could be overcome, the Java Specification Request (JSR) process is a lengthy and bureaucratic process required for new features to be included. In contrast, Google, just like Apple with iOS, has complete control and can drive adoption of new features in a faster and more streamlined manner. Lastly, a large part of the reason Java has had limited success in the past on mobile platforms is due to the speed of mobile Java platforms which are not designed to take advantage of today’s smartphone devices. Consequently, rather than using one of the existing Java Virtual Machines, Google instead opted to develop a custom clean-room virtual machine of their own.

Licensing Issues

Oracle’s J2SE virtual machine, OpenJDK, is licensed using the GNU Public License version 2 (GPLv2). However, there is a restriction in the license that shields applications running on the virtual machine from being “infected” by the GPL because of its copyleft provision. Copyleft would require applications to have the same license as the virtual machine itself. In contrast, this restriction is not included for the J2ME virtual machine.

Cell phone manufacturers would certainly balk at the possibility of releasing all their application source code, so instead Oracle makes a good deal of revenue offering their TCK license, for a fee, to avoid this obligation. Even Apache’s Harmony J2SE VM, which could be easily turned into a J2ME virtual machine, has a limited field of use restriction to force handset suppliers to purchase a J2ME license instead of rolling their own. Google asserts that Dalvik avoids this obligation but, Oracle disagrees and has filed litigation to defend its claim.

Open Source

Google’s business model for Android is to give it away as an open source and free platform. Instead of directly generating revenue, their goal is to maintain access to the growing smartphone market for their services and more importantly, advertising. With this goal in mind, Dalvik is licensed using the Apache License 2.0 which is very business friendly, because it does not require modifications and derivative works to be released under the same license. This allows companies to build and deploy proprietary products using the code for free. Additionally, it permits the code to be used for free and open source software by the community.

Security

Mobile devices contain a significant amount of sensitive information about the user: phone numbers, call records, physical location, etc. Hence, people expect a higher level of security for a smartphone than for a traditional feature phone to protect this data. In response to these concernts, Dalvik was designed to take advantage of the Linux kernel’s strong security model with each VM instance running in its own process. This sandboxes processes from each other to create a strong barrier between applications.

Implementation

Now that we understand the motivation behind creating Dalvik, we’ll discuss how Dalvik custom tailered their design for a mobile platform by optimizing bytecode filesize, interpreter speed and memory usage. Also, we will see how the security model impacted design of the garbage collector and process initializer, Zygote.

Dex Filesize

Dalvik’s dex binary files contain all the translated java classfiles combined into a single file. The reason each file is not kept separate is to reduce the total storage size. This is possible because each classfile contains constant pools, much of which is redundant to the application and are often the biggest part of a classfile. With all these classes together the redundant constant values that are shared between the files can be removed and only one copy is required. This approach allows the same code to be stored in about the same amount of space that a compressed jar of the same classfiles would require. Through consolidation Dalvik is able to increase performance by eliminating the need to decompress the file (Illustration 1).

Interpreter Speed

Last year at the Google I/O conference, the Dalvik team announced a just-in-time (JIT) compiler to Dalvik. This addition allows developers to increase the performance of Java code without having to resort to using the Native Development Toolkit (NDK) and rewriting their code in C/C++. In contrast to most JIT compilers, the Android team chose to implement code trace optimization instead of the more common method based optimization.

A trace is a sequence of instructions that are executed together usually through multiple methods. In an Android game for example, we might have a repaint thread which draws a list of updated objects onto a canvas periodically. This trace would traverse multiple class methods and should be very fast making it a good candidate for JIT optimization. As we discussed earlier, Android runs on a resource constrained system in terms of both memory and CPU power. Consequently the team chose to identify hot traces at runtime to be optimized instead of using more memory to optimize whole methods. These traces are compiled natively and then are placed in a translation cache for future use. As pieces of an application are translated, execution begins to jump back and forth from the translation cache to the interpreter. For hot traces that are executed back-to-back, execution jumps between the cache entries and does not return to the interpreter until no translation is available for the required code. Another design choice for security and simplicity reasons, requires that each individual process has its own translation cache.

Zygote

Zygote enables multiple Dalvik instances to share memory to limit the memory burden of each running concurrently. As the name implies, Zygote’s purpose is to provide a preloaded Android process ready for a new application, without incurring the delay of starting from scratch. During the initialization of the Zygote, core classes are preloaded into memory to allow even faster application startup. Since each Zygote uses copyon-write for shared memory space, much of the memory for each application is reused and thereby places a lighter burden on the limited resources of the device. This only works because these core classes are mostly read-only and will rarely require more than one version for all applications. Compared to a typical Java virtual machine, this is quite an improvement in performance and memory efficiency since they do not exhibit this type of memory sharing between instances. Once the classes are loaded, the Dalvik VM itself is then initialized and is ready to run Dalvik bytecode from a dex file. Once the Zygote has been inhabited by a new application, another Zygote is forked to wait on a socket for the next application to be launched.

Garbage Collection

In order to perform garbage collection the interpreter needs to save a bit that represents when an object can be collected, so called “mark bits”. These bits can be stored either next to the object in memory or together in a single table. Since memory is so limited, it is important to maintain as much shared memory between the processes as possible. This means Dalvik must avoid having private copies generated by changing mark bits for individual objects in separate processes that are in truth, the same object. Instead, the virtual machine uses a single table in each process which allows objects to remain shared in memory as a single copy, unless they are modified at which point they are duplicated. In comparison, using a single table for all processes could require objects to be retained longer than necessary and more importantly increases design complexity significantly.

Performance

Google claims that Dalvik is roughly twice as fast as the Oracle virtual machines due to its register based design and more expressive instructions. In contrast to the stack based Oracle virtual machine, Dalvik is register based instead. Additional improvements come from the native compilation of most of the core system libraries, allowing library operations to run at native speed. For applications that need additional performance the native development toolkit (NDK) offers a full toolchain to write code in C/C++ and compile to native instructions for faster execution.

Conclusion

In this article we have seen how the Dalvik virtual machine was custom designed to provide Java support to the Android platform. We discussed the technical, security and legal motivations behind its creation. With these concerns in mind, we also discussed the implementation decisions made by the designers to optimize the interpreter and its resulting performance. Overall Android is here to stay and to take full advantage of the platform any developer would be wise to be well informed about the bedrock of Java support on the platform, the Dalvik virtual machine.

Author
FrankMaker
Frank is a Ph.D. candidate at the University of California, Davis concentrating on Embedded Software and Systems. Since its introduction, he has been doing systems research with Android on automatic low power adaptation techniques. He also owns his own consulting firm, Handy Codeworks (www.handycodeworks.com), which offers training and technical services for Andoid devices. Professionally he enjoys embedded Linux/Android systems hacking and the occasional hardware project. In his spare time he enjoys spending time with his wonderful wife, baby daughter and dog. He can be reached at fmaker@handycodeworks.com
Comments
comments powered by Disqus