Leading items

ABS: The guts of Android

In a fairly fast-paced talk, Karim Yaghmour presented the internals of Android systems at the Android Builders Summit. The talk focused on things like Android's application development model, the parts and pieces that make it up, and its startup sequence. It gave an overall picture of a system that is both familiar and not.

Yaghmour is the lead author of Building Embedded Linux Systems and has done Linux kernel development along the way. He developed the original Linux Trace Toolkit (LTT) in 1999, which has since been taken over by another École Polytechnique de Montréal graduate, Mathieu Desnoyers, as LTT next generation (LTTng). Desnoyers is "doing a much better job" with it than he did, he said with a chuckle. He also developed relayfs, which is an efficient way to relay large amounts of data from kernel to user space. He is now doing Android development and training.

Android internals

With a slide showing Kirk and Spock from the original Star Trek, and the line "it's Linux, Jim, but not as we know it", Yaghmour pointed out that Android is a "strange beast" that "looks weird, feels weird, and acts weird". That's because it doesn't have the traditional Linux user space, but instead has its own user space that sits atop a somewhat non-standard Linux kernel.

For example, there is no "entry point" to an application for Android. Developers create components that get bundled together as applications. An application consists of multiple components, some of which may be shared with other applications. Each application is hosted in a Linux process. Any of those components can disappear while the system is running because its application process goes away. That can be because the application is no longer needed or because of memory pressure from other applications being loaded. That means that components need to implement "lifecycle management". Essentially, components need to be able to come back again the way they were before being killed.

Android also uses messages called "intents" that are sent between components. Yaghmour said they are like "polymorphic Unix signals" that can be sent to a specific component or service, but can also be broadcast. Applications can register their interest in various intents by specifying Intent Filters in their manifest files.

Remote procedure calls (RPCs) (or inter-process communication aka IPC) are done using the "Binder" in Android because "System V IPC sucks", at least according to comments in the Android code. The Binder allows components to talk to services and for services to talk to each other. The Binder is not used directly, however, and instead interfaces are defined using an interface definition language (IDL). Those IDL definitions are fed to a tool that generates Java code to handle the communication.

The development environment for Android is "fantastic", Yaghmour said. The Android SDK provides everything that is needed to create applications. The problems come when trying to develop a device that runs Android, he said, because the "glue that allows all these APIs to talk to the kernel is not documented anywhere". For a "normal" embedded Linux system, you generally just need the kernel, a C library, and BusyBox, which is generally enough to allow you to build any custom applications, but for Android, the picture is much more complex.

It is still the Linux kernel at the bottom, but that's about it that is the same as a normal Linux system. The kernel has numerous patches applied to it for things like wakelocks and the Binder, but it is recognizably Linux. Above that, things start to change. There are a number of libraries available, some of which appear in other systems (Linux, BSD, etc.), like WebKit and SQLite, but some are Android-specific, like the libc replacement, Bionic.

Android has its own init, which is not based on either System V init, or on BusyBox's, partly because it doesn't use the latter. Instead of BusyBox, Android has something called Toolbox that fills the same role, but not as well. Yaghmour said that the first thing he does on an Android system is to replace Toolbox with BusyBox. It was a political decision not to use BusyBox, rather than a technical one, he said. There are also various libraries to support hardware like audio devices, cameras, GPS devices, and so on, all of which are implemented in C or C++.

Android uses Java Native Interface (JNI) to talk to any of that lower level code from the Java-based code that makes up (most of) the rest of user space. The Dalvik virtual machine uses JNI to call those libraries. The system classes (in the android.* namespace), as well as the Apache Harmony-based standard Java classes (in java.*) sit atop of Dalvik, as does the all-important System Server. Above those are the stock Android applications along with any other applications installed by the user (from the Market or elsewhere).

Android replaces the Java virtual machine with Dalvik, and the JDK with classes from Apache Harmony. To create .dex files for Dalvik, the Java is first processed by the Java tools to create .class files, which are then post-processed by dx to produce the files used by Dalvik. One interesting thing noted by Yaghmour is that .dex files are typically half the size of the equivalent .class files.

The layout of the native Android user space is very different than standard Linux as well. There is no /bin or /etc, which nearly every standard Linux tool expects to find. The two main directories in Android are /data (for user data) and /system (for the core system components). But some of the expected directories are present, like /dev and /proc.

Android startup

After that relatively high-level overview of the Android system, Yaghmour looked at the Android startup sequence, starting with the bootloader. That bootloader implements a protocol called "fastboot" that is used to control the boot process over USB using a tool of the same name on a host system. The bootloader contains code to copy various portions of the code around on the flash (for returning to a stock image for example), and allows users to boot from a special partition that contains a recovery program (via a magic key sequence at boot time). Some of these are features that might make their way into U-Boot or other bootloaders, he said.

The flash layout of a typical device has multiple partitions to support Android, including "boot" (which is where the kernel resides), "system", "userdata", and "cache" (the latter three corresponding the mounted /system, /data, and /cache filesystems on a running Android system). Yaghmour noted that Android does not follow the Filesystem Hierarchy Standard (FHS) with its filesystems, but it also doesn't conflict with that standard, which allows folks to install FHS filesystems alongside Android's.

Newer Android releases are using the ext4 filesystem, rather than the yaffs2 filesystems used on earlier devices. That's because the latest devices are not using a classic NAND flash chip, and instead are using something that looks like an SD card to the processor. The kernel treats it like a block device. Because the newer devices have multicore processors, Google wanted a filesystem that is optimized for SMP, he said, thus the move from yaffs2 to ext4.

Once the kernel has booted, it "starts one thing and one thing only" and that is the init process. Init parses /init.rc and runs what it finds there. Typically that means it creates mount points and mounts filesystems, starts a low-memory handler that is specific to Android (and runs before the kernel's out-of-memory (OOM) killer), starts a bunch of services (including the servicemanager which manages Binder contexts), and starts the "root" of the Java process tree, Zygote (aka app_process).

Zygote is the parent process of all application processes in the system. It "warms up the cache of classes" so that applications start quickly, and starts the System Service. The System Service is a key part of the Android system, but one that is not very well documented. "Anything that is important that is running in the system is housed inside the System Service", Yaghmour said. That includes services for various hardware devices (battery, lights, vibrator, audio, sensors, etc.), as well as managers for things like alarms, notifications, activities, and windows (i.e. the window manager).

The System Service starts the ActivityManager to do what its name implies, manage activities. It is "one of the most important services" in Android, he said. It handles starting activities, broadcasting events, and more. He likened it to the kernel's scheduler. When an activity needs to be started, for example, the ActivityManager asks Zygote over a socket to do so.

The hardware devices are generally accessed via their services, which call into an underlying library that is typically provided by a vendor. For things like LEDs, Android provides a .h file that describes the interface and vendors create a C program that implements it. It is similar for other devices like GPS, audio, camera, and so on. For WiFi, wpasupplicant is used, while Bluetooth support comes from BlueZ.

Because of GPL concerns, Android talks to BlueZ via D-Bus, which may be controversial in some quarters, Yaghmour said. In answer to a question from an audience member, he noted that Google wanted to avoid having its partners have to explain licensing to their engineers. So, it chose not to use GPL-covered software other than the kernel to keep user space "free" of licensing concerns. That gets a little blurrier with the inclusion of BlueZ, but the "theory" is that the GPL does not apply to code that talks to it via D-Bus. Some may disagree with that theory, he said.

It must have been hard to pull together a reasonable look at Android's guts that would fit into a 50-minute slot, but Yaghmour largely succeeded in doing so. There were undoubtedly lots of details passed over, but attendees definitely got a good feel for what goes on inside the phone that resides in many of their pockets.

Comments (26 posted)

Exploring the globe with Marble 1.1

Marble, as part of the KDE Software Collection (KSC), typically sees releases in-line with major KDE releases. However, thanks to the efforts of students working with the KDE Project for the Google Code-in, Marble picked up enough new features that it was worth releasing 1.1 mid-cycle and getting its new features out early. With 1.1 the 3D mapping application picks up plugin configuration, map editing, and voice navigation if you happen to be using Marble on the Nokia N900.

Marble is 3D virtual globe, part of the KDE application set — but also available in a Qt-only version for Linux users who prefer not to include KDE-only dependencies or for Mac and Windows users. Since LWN last looked in on Marble, it's come a long way. The basic interface is still the same — but Marble has picked up quite a few features since the 0.5 days.

Since 1.1 is out of step with KDE SC releases, it may not turn up as a package for any of the major distributions right away. To test it out, I decided to compile it from source on openSUSE 11.4. As mentioned, you have the choice of compiling the Qt-only version of Marble or the full KDE version — I opted for the full KDE version. The 1.1 release library is meant to be ABI compatible with the 1.0 release, which means that other KDE applications that depend on it should work as expected.

One word of warning if you do opt to compile Marble on your own — make sure to uninstall the prior Marble package as well. Forgetting this simple and obvious step could lead to some odd behavior, or so we've heard.

Using Marble 1.1

After compiling Marble 1.1, I set about exploring the Marble interface and checking out some of the new features. For exploring the globe and generally poking around, Marble is fantastic. The interface is easy to use, it offers a variety of map views (flat, Mercator projection, and your standard globe), and quite a few themes. The themes are things like a satellite view of Earth, OpenStreetMap (OSM) data, Earth at night (which shows city lights from space), and so on.

Marble is a good tool for students, hence its position in the KDE Educational software project. You can click on a city and see two tabs. One contains the Wikipedia entry for the city and the other contains a basic data sheet provided with Marble itself — though I found no description in any of the data sheets for any of the cities that I checked. Each had coordinates, country, time zone, etc., but Marble seems to rely on Wikipedia for any actual description.

One of the interesting new features in Marble 1.1 is an online service that displays earthquakes that have happened in a given spot with their magnitude. It's worth noting that this feature was completed during the Code-in and is not related to or inspired by the earthquakes that caused so much damage in Japan. It was surprising to see just how many earthquakes that have been recorded in the US Midwest, though of minor magnitude, since 2006. Unfortunately, Marble doesn't provide a link to any additional information about the events online — the data is simply provided as a colored circle with the magnitude. The color and size of the circle is determined by the magnitude of the earthquake, with larger quakes being a darker red and having a larger diameter. Hovering the mouse over the circle will display the date and depth — but that's all.

For users who have a Nokia N900, Marble should provide voice navigation. Unfortunately, I don't have a Nokia N900 handy, and wasn't able to test this feature. Users who are interested in voice navigation will need to convert a TomTom voice for use with Marble, as it doesn't ship with any at the moment. The Marble folks would welcome contributions, so if you're a non-developer with a pleasant voice this may be an opportunity to contribute.

Marble will open maps or map data in GPS Exchange Format (GPX) and Keyhole Markup Language (KML). I didn't do a lot with importing GPX or KML map data, but did grab a few GPX files online and viewed them in conjunction with OpenStreetMap data. This seemed to work very well.

Where Marble falls down a bit is with routing. Marble allows you to search maps for street addresses and create routes between addresses, but tends to be hit or miss when it comes to actually creating a route or finding some street addresses. For example, I tried creating a route between my home in St. Louis and Bradenton, Florida or between my home in St. Louis and my parents' old home less than 100 miles from St. Louis. Between St. Louis and Florida, Marble was unable to generate a route at all. Marble was also unable to find my old home address, though I could create a route from my current address to my old hometown that was mostly sane.

At home cartography

One of the major new features for 1.1 is the ability to edit maps or create your own. Users can import map data from a server that provides data via Web Map Service (WMS), via a bitmap stored locally, or from a static service like OSM.

The process is laid out in a tutorial on the KDE UserBase, but is not terribly intuitive as of yet. It does work, it's just a bit clunky and certainly will be non-obvious to most users. The tutorial also provides a few pointers for WMS servers and other resources, which will be useful to anyone who wants to learn how to make a map without already having a free map service in mind. According to Dennis Nienhüser, one of the Marble developers, an updated (and more intuitive) wizard is on its way for Marble 1.2.

When using OSM maps, users can actually right-click on the map and open it in an external editor to edit the map. Marble supports a Flash-based editor called Potlatch, along with Merkaartor, or JOSM for editing maps.

Up the Marble road

Though the 1.1 release was pushed out so the world could have the new features early, one shouldn't worry that Marble 1.2 won't hit on schedule. The 1.2 release will be back in sync with the KSC release, so it's expected with the KDE 4.7 release scheduled for July. One of the things that is on the drawing board is an OpenGL mode for Marble. This doesn't mean that Marble would leave 2D systems behind — but it would add OpenGL support for platforms that have it enabled.

Nienhüser also says that more mobile platforms are in the future for Marble, as well as making Marble one of the "Plasma Active" enabled applications. Which mobile platforms? Nienhüser says he's looking at MeeGo first, and "if MeeGo does not kick off, I guess Android is the next target."

Marble also has a couple of Google Summer of Code projects in the works, according to Nienhüser. One is vector rendering of OSM data (it's currently using bitmapped data — which requires quite a hefty download), the other is a QML version of Marble that would target MeeGo.

Though it's still rough around a few of the edges, Marble has come a very long way since its early days — and looks to be headed for uncharted territory as one of the most usable free software mapping tools.

Comments (3 posted)

A victory for the trolls

For many years we have heard warnings that software patents pose a threat to the free software community. Repeated warnings have a tendency to fade into the noise if they are not followed by real problems; to many, the patent threat may have seemed like one of those problems we often hear about but never experience. The recent ruling in the US that Google is guilty of infringing a software patent held by a patent troll named "Bedrock Computer Technologies" serves as a reminder that the threat is real, and that solutions will not be easy to come by.

The patent in question is #5,893,120 - "Methods and apparatus for information storage and retrieval using a hashing technique with external chaining and on-the-fly removal of expired data." The independent claims from the patent are short and simple; #3 reads like this:

Needless to say, numerous people who are "skilled in the art" have concluded that there is little that is original or non-obvious in this claim. In its defense, Google argued that the technique is, indeed, obvious (to the point that it should be invalidated under the Bilski ruling), that the patent is invalid due to prior art, and that Linux did not infringe upon the patent in any case. All of those arguments were pushed aside by the jury, which found Google guilty and granted an award of $5 million, a small fraction of the $183 million requested by Bedrock.

The full set of docket entries - almost 800 of them - are listed on the net. Many of the interesting ones are sealed, though, and unavailable to the public. We are all affected by this ruling, but we are unable to read most of testimony that led up to it. Instead, the bulk of the publicly-available information has to do with the various bits of legal jousting which set timetables and which control the evidence that can be presented. Thus, for example, we learn that a late attempt to bring in Alan Cox to testify on his early routing table work was pushed back and eventually abandoned. Still, there are some interesting things to be learned by plowing through these documents.

The code

The code in question is that which maintains the networking stack's routing cache - some of the oldest code in the kernel; it can be found in .../net/ipv4/route.c. This code maintains a hash table of linked lists containing routing entries; as the world changes, entries must be added or deleted. Bedrock claims that its patent is infringed by this code, though even Bedrock has, more or less, admitted [PDF] that any infringement will have been done inadvertently, with no knowledge that the patent existed. The various defendants (Google is only one of the companies targeted) have made various arguments, starting with the claim that the code does not use the algorithm described in the patent at all; see this brief [PDF] for a summary of that argument:

What one learns early on is that how terms like "when the linked list is accessed" are defined is crucial in a decision regarding infringement. That is where the "claim construction" process comes into play; for the full, gory details of how it was done in this case, see docket #369 [PDF]. There was a big fight, for example, over whether "removing from the linked list" required deallocation of the entry that was removed; Bedrock won that one and got a ruling that deallocation is a separate operation. The biggest fight seemed to be over whether removal "when the linked list is accessed" meant that the structure needed to be removed during the traversal of the list; Bedrock seemed to think that removal at some later time qualified, but the court disagreed. That should have been a decisive victory for the defense, but it appears to not have been enough.

Invalidation attempts

There was also a determined effort to have the patent ruled invalid due to prior art. It is interesting to note that, in early 2010, a separate challenge to this patent was raised at the US Patent and Trade Office, citing four other patents as prior art; the patent was, in fact, invalidated by the PTO last July. But Bedrock was then allowed to tweak the wording of the claims until the PTO agreed that the modified patent was, once again, valid. This history shows why attempts to kill patents so rarely achieve the desired results: patents can never truly be killed this way. Instead, the owner is allowed to make changes, resulting in zombie patents that return from the dead to terrorize again and again. A second challenge to the patent was filed in January of this year; it cites two more patents as prior art; a ruling has not yet been made in this case.

The defendants' attempt to invalidate the patent does not depend on that prior art at all, interestingly; instead, this challenge [PDF] is based on the Linux code itself. They claim that the code in route.c has not changed materially since the 1.3.x days and that, in particular, the 2.0.1 version was quite close to what we have now. These prior versions, it is claimed, include all of the claims of Bedrock's patents, and thus serve as prior art invalidating the patent. One might find some amusing irony in the claim that older code implemented the patented technique while current code - said to be about the same - does not. The point is, of course, that if the current code is said to infringe, the older code should be said to implement the patent in the same way. Either both versions implement the patented algorithm (in which case it's invalid due to prior art) or neither does.

The argument seems strong enough. We cannot know how Bedrock argued against this reasoning, though - its response is sealed and inaccessible. It is also worth noting that the US PTO has not considered older Linux releases as prior art when reevaluating this patent; it would appear that the challengers have not asked it to.

In the midst of all this, Red Hat has filed a suit of its own against Bedrock. It seems that some Red Hat customers have been getting nervous about Bedrock's activity and asked for help; Red Hat responded by filing a preemptive suit asking that the patent be ruled invalid and that Red Hat's products be deemed to be non-infringing. That case is still in the works; Red Hat also tried to jump into the Google et al. case [PDF], but that attempt was denied by the judge. In reading the filings, one also learns the Match.com (another defendant in the suit) made a deal with Bedrock and was allowed to drop out.

Now what?

This verdict has been widely publicized as a big defeat for Linux. Perhaps it is, but not for the reasons being cited - this particular patent is not a huge problem, but the fact that patent trolls can win judgments against Linux is problematic indeed. If need be, the kernel's routing table code can be tweaked to avoid infringing Bedrock's patent; indeed, Docket #445 [PDF] lets slip the fact that Google has already changed its kernels to that effect. There could be a case for past infringement, but there need be no real fear that Bedrock will be out there collecting rents from Linux users in the future, even if the ruling stands.

We can hope that the ruling will, in fact, not stand. If Red Hat prevails in its separate case, the verdict against Google will have to be reevaluated. Even in the absence of a victory there, Google's defense was strong enough to warrant an appeal. Google is just one of a number of companies which cannot let it be thought that Linux is an easy target for shakedowns by patent trolls; there is a strong incentive for the company to keep on fighting, even if that fight is likely to cost more than the (relatively small) $5 million it has been told to pay Bedrock. For all of our sake, we must hope that all of the companies involved in this case find it worth their while to get the ruling reversed.

If Bedrock loses in the end, other potential trolls will hopefully be deterred from jumping in with suits of their own. But there can be no doubt that more of these cases will come along; that is really just the nature of the software patent system. Until we can get some sort of high-level reform, we will always have to fear trolls wielding patents on elementary techniques.

Comments (92 posted)

"Maniacal supporter" subscription level now available

For a while now, certain LWN subscribers have been asking us to add a more expensive subscription level. We are happy to announce that, at long last, we have done it; the new "maniacal supporter" level is now available for those of you who are feeling sufficiently maniacal to pay $50/month for LWN. The additional benefits of this level are small in number, but we assure you that they can be had nowhere else; from the LWN FAQ:

In the end, this option is the result of a rule of thumb which has never steered us wrong: always do what Rusty says. We are most curious to see how many of our supporters are willing to take this next step to help keep LWN going.

Thanks to all of you for supporting LWN at any level.

Comments (11 posted)

Page editor: Jonathan Corbet
Next page: Security>>