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
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.
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
being loaded. That means that components need
"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
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
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.
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
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
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.
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
many of their pockets.
Comments (26 posted)
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)
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:
A method for storing and retrieving information records using a
linked list to store and provide access to the records, at least
some of the records automatically expiring, the method comprising
the steps of:
- accessing the linked list of records,
- identifying at least some of the automatically expired ones of the records, and
- removing at least some of the automatically expired records from
the linked list when the linked list is accessed.
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.
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 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:
The accused instrumentalities - servers using versions of the Linux
kernel prior to 2.6.25 - do not meet all elements of the '120 patent
because: (1) removal of records does not occur "when the linked
list is accessed" ('120 patent claims 1, 3, 4, 5, 7, and 8); (2)
the removed records are not "expired" ('120 patent claims 1, 3, 5,
and 7); (3) there is no "dynamically determining maximum number" of
expired records to remove ('120 patent claims 2, 4, 6, and 8) (for
all accused versions); (4) the accused code does not remove an
expired record while using the record search means to search for a
record to delete (for all accused versions); and (5) there is no
evidence that the accused code has ever executed, as required by
all asserted claims.
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.
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.
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;
#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
Comments (92 posted)
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
Subscribers at this level have all the access given to "project
leader" subscribers; they are also credited as supporters in their
comment postings. LWN staff will happily buy supporters a beer
(or other beverage of their choice) at any conference where they
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
Thanks to all of you for supporting LWN at any level.
Comments (11 posted)
Page editor: Jonathan Corbet
Next page: Security>>