Leading items

LinuxCon: Kernel roundtable covers more than just bloat

If you have already heard about the kernel roundtable at LinuxCon, it is likely due to Linus Torvalds's statement that the kernel is "huge and bloated". While much of the media focused on that soundbite, there was quite a bit more to the panel session. For one thing, Torvalds definitely validated the impression that the development process is working better than it ever has, which has made his job an "absolute pleasure" over the last few months. In addition, many other topics were discussed, from Torvalds's motivations to the lessons learned in the 2.6 development series—as well as a bit about bloat.

The panel consisted of five kernel developers: Torvalds, Greg Kroah-Hartman of Novell, Chris Wright of Red Hat, Jonathan Corbet of LWN, and Ted Ts'o of IBM (and CTO of the Linux Foundation) sitting in for Arjan van de Ven who got held up in the Netherlands due to visa problems. James Bottomley of Novell moderated the panel and set out to establish the ground rules by noting that he wanted to "do as little work as possible", so he wanted questions from the audience, in particular those that would require answers from Torvalds as "he is sitting up here hoping to answer as little as possible". Bottomley was reasonably successful in getting audience questions, but moderating the panel probably took a bit more effort than he claimed to be looking for.

Innovative features

Bottomley began with a question about the "most innovative feature" that went into the kernel in the last year. Wright noted that he had a "virtualization slant", so he pointed to the work done to improve "Linux as a hypervisor", including memory management improvements that will allow running more virtual machines more efficiently under Linux. Corbet and Ts'o both pointed to the ftrace and performance counters facilities that have been recently added. Tracing and performance monitoring have both been attacked in various ways over the years, without getting into the mainline, but it is interesting to see someone approach "the problem from a different direction, and then things take off", Corbet said.

Bottomley altered the question somewhat for Kroah-Hartman, enquiring about the best thing that had come out of the staging tree that Kroah-Hartman maintains. That seemed to stump him momentarily, so he mentioned the USB 3.0 drivers as an innovative feature added to the kernel recently, noting that Linux is the first OS to have a driver for that bus, when hardware using it is still not available to buy: "It's pretty impressive". After a moment's thought, though, Kroah-Hartman pointed out that he had gotten Torvalds's laptop to work by using a wireless driver from the staging tree, which completely justified that tree's existence.

Ts'o also noted the kernel mode switching support for graphics devices as another innovative feature, pointing out that "it means that the X server no longer has to run as root—what a concept". He also suggested that it made things easier for users who could potentially get kernel error messages in the event of a system hang, without having to hook up a serial console.

Making it easy for Linus

Torvalds took a "different tack" on the question, noting that he was quite pleased with "how much easier my job has been getting in the last few months". He said that it is a feature that is not visible to users but it is the feature that is most important to him, and that, in the end, "it improves, hopefully, the kernel in every area".

Because subsystem maintainers have focused on making it "easy for Linus" by keeping their trees in a more mergeable state, Torvalds has had more time to get involved in other areas. He can participate in more threads on linux-kernel and "sometimes fix bugs too". He clearly is enjoying that, especially because "I don't spend all my time just hating people that are sending merge requests that are hard to merge".

Over the last two merge windows (including the just completed 2.6.32 window), things have been going much more smoothly. Smooth merges mean that Torvalds gets a "happy feeling inside that I know what I am merging — whether it works or not [is a] different issue". In order to know what he is merging, Torvalds depends on documentation and commit messages in the trees that outline what the feature is, as well as why people want it. In order to feel comfortable that the code will actually work, he bases that on his trust of the person whose tree he is merging to "fix up his problems afterwards".

Motivation

The first question from the audience was directed at Torvalds's motivation, both in the past and in the future. According to Torvalds, his motivation for working on the kernel has changed a lot over the years. It started with an interest in low-level programming that interacted directly with the hardware, but has slowly morphed into working with the community, though "I shouldn't say 'the community', because when anyone else says 'the community', my hackles rise [...] there's no one community". It is the social aspect of working with other people on the kernel project that is his main motivation today, part of which is that "I really enjoy arguing".

Torvalds's technical itch has already been scratched, so other things keep him going now: "All of my technical problems were solved so long ago that I don't even care [...] I do it because it's interesting and I feel like I am doing something worthwhile". He doesn't see that changing over the next 5-10 years, so, while he wouldn't predict the future, there is a clear sense that things will continue as they are—at least in that time frame.

Malicious code

Another question from the audience was about the increasing rate of kernel contributions and whether that made it harder to keep out malicious code from people with bad intentions. Kroah-Hartman said that it is hard to say what is malicious code versus just a bug, because "bugs are bugs". He said he doesn't remember any recent attempts to intentionally introduce malicious code.

Torvalds pointed out that the problem has never been people intentionally doing something bad, but, instead, trying to do something good and unintentionally ending up causing a security hole or other bug. He did note an attempt to introduce a back door into the kernel via the BitKeeper repository 7-8 years ago which "was caught by BitKeeper with checksums, because they [the attackers] weren't very good at it". While that is the only case he is aware of, "the really successful ones we wouldn't know about". One of Git's design goals was to keep things completely decentralized and to cryptographically sign all of the objects so that a compromise of a public git server would be immediately recognized, because it didn't match others' private trees, he said.

Performance regressions

Bottomley then turned to performance regressions, stating that Intel had been running a "database benchmark that we can't name" on every kernel release. They have found that the performance drops a couple of percentage points each release, with a cumulative effect over the last ten releases of about 12%. Torvalds responded that the kernel is "getting bloated and huge, yes, it's a problem".

"I'd love to say we have a plan" for fixing that, Torvalds said but it's not the case. Linux is "definitely not the streamlined, small, hyper-efficient kernel that I envisioned 15 years ago"; the kernel has gotten large and "our icache [instruction cache] footprint is scary". The performance regression is "unacceptable, but it's probably also unavoidable" due to the new features that get added with each release.

Audio and storage

In response to a question about professional audio, Torvalds said that the sound subsystem in the kernel was much better than it is given credit for, especially by "crazy" Slashdot commenters who pine for the days of the Open Sound System (OSS). Corbet also noted that audio issues have gotten a lot better, though, due to somewhat conflicting stories from the kernel developers over the years, audio developers "have had a bit of a rough ride".

A question about the need for handling memory failures, both in RAM and flash devices, led Ts'o to note that, based on his experience at a recent storage conference, there is "growing acceptance of the fact that hard disks aren't going away". Hard disks will always be cheaper, so flash will be just be another element in the storage hierarchy. The flash hardware itself is better placed to know about and handle failures of its cells, so that is likely to be the place where it is done, he said.

Lessons learned

The lessons learned during the six years of the 2.6 development model was the subject of another question from Bottomley. Kroah-Hartman pointed to the linux-next tree as part of a better kernel development infrastructure that has led to more effective collaboration: "We know now how to work better together". Corbet noted that early 2.6 releases didn't have a merge window, which made stability of those releases suffer. "What we've learned is some discipline", he said.

In comparing notes with the NTFS architect from Microsoft, Ts'o related that the core Windows OS team has a similar development model. "Redmond has independently come up with something almost identical to what we're doing", he said. They do quarterly releases, with a merge period followed by a stabilization period. Microsoft didn't copy the Linux development model, according to the NTFS architect, leading he and Ts'o to theorize that when doing development "on that scale, it's one of the few things that actually works well". That led Bottomley to jokingly suggest a headline: "Microsoft validates Linux development model".

Torvalds also noted that the development model is spreading: "The kernel way of doing things has clearly entered the 'hive mind' when it comes to open source". Other projects have adopted many of the processes and tools that the kernel developers use, but also things like the sign-off process that was added in response to the SCO mess. Sign-offs provide a nice mechanism to see how a particular chunk of code reached the mainline, and other projects are finding value in that as well.

Overall, the roundtable gave an interesting view into the thinking of the kernel developers. It was much more candid than a typical marketing-centric view that comes from proprietary OS vendors. Of course, that led to the "bloated" headlines that dominated the coverage of the event, but it also gave the audience an unvarnished look at the kernel. The Linux Foundation and Linux Pro magazine have made a video of the roundtable available—unfortunately only in Flash format—which may be of interest; it certainly was useful in augmenting the author's notes.

Comments (30 posted)

OpenInkpot: free software for e-book readers

Back in July, Jonathan Corbet lamented that Amazon was making the Kindle an unattractive hacking target for Linux users. The comments to his article suggested having a closer look at OpenInkpot, a fairly new Linux distribution for e-book readers. This much in advance: It doesn't run on the Kindle. Not yet, anyway.

OpenInkpot (or OI) intends to be a full alternative, free software stack for e-ink based readers. It comes with a "bookshelf" menu to handle your collection of e-books and brings the popular FBReader and Cool Reader to display most e-book formats, among them epub, fb2, txt, html, rtf, pdb, plucker and mobipocket. PDF files are handled by OI's own locoPDF and madeye is a simple viewer for images. A sound player application for audio books will join the OI software collection soon.

History

The initial motivation for OpenInkpot was the limited use of the original software that Debian hackers Mikhail Gusarov and Yauhen Kharuzhy found on their newly acquired Hanlin V3. They found it too slow and its software clunky. E.g., there was no way to adjust the PDF viewer's zoom and the bookshelf couldn't handle Cyrillic or other non-ASCII characters in file names.

Because of that, the V3 became the only supported device of the first public 0.1 OpenInkpot release in August 2008. Mikhail says they achieved most of their goals for the V3. OI supports more formats and is faster to display and turn pages, although the more complex user interface of OI eats up some of the speed improvements to the original firmware.

Right now, the team is busy porting OI to a second hardware platform for the upcoming 0.2 release, the Hanvon N516. Both V3 and N516 are available inexpensively under various brand names around the world. Intrigued by OI, your author quickly found an online shop based in his country and, a few days later, the original firmware of his brand new N516 didn't survive more than 30 minutes before it got overwritten with a development snapshot of OI.

With the new firmware, you win some and you lose some features. The N516 gains a lot more e-book formats through OI, but loses others such as the Chinese XEB format. The OI PDF reader is an improvement, but an audio player is missing since OI's sound drivers and applications are still under development. The main advantage of running OI is that it is fully open source and not tied to one manufacturer or device.

The internals of OI

OI's current development trunk for the upcoming 0.2 release uses a recent 2.6.29 kernel (with a switch to .31 planned), kernel drivers, and system software targeted for Hanlin V3 and Hanvon N516 devices.

To get the first version of OI going, kernel hacker Yauhen had to work without hardware documentation. He disassembled the V3's original firmware binary and wrote drivers for the buttons, the battery controller, and the display. The V3 is a simple ARM board with an e-ink display, but its audio hardware is unusual: It only decodes MP3 streams and further investigation is needed to see if it can be made to play simple raw PCM audio so that it can be used for generic audio applications.

The port to the N516 is mostly complete and luckily, its manufacturer is far more helpful with specs and sources. An audio driver is still missing for the N516 too, but it is in progress for the 0.2 release. Compared to the V3, the N516 sports a faster MIPS CPU and more RAM, which is helpful for applications such as FBReader, which keeps the full document file in memory. On the downside, the N516 uses some funky hardware components that complicate driver development, e.g. handling key presses or reading the status of the battery is unnecessarily difficult.

Yauhen also made some improvements to the e-ink display driver by Jaya Kumar to speed up screen updates. All drivers and modifications by the OI team are intended to be contributed upstream.

The OI user space software is based on the Debian-like IPlinux, which is a fork that Mikhail made of the dormant Slind project. (OpenEmbedded was also tried, but discarded, mostly because the team did not like OE's package build management.)

Alexander Kerner, the third main OI developer, maintains many of the user space libraries and applications and describes OI as an abstraction layer that hides most of the embedded nature of the hardware from the developer. He installs the same libraries on his x86 desktop to develop an application, so that cross-compiling for the device later is not much of an effort.

The static nature of an e-ink display is a challenge for user interface development. Screen updates are very slow and expensive, but the display does not consume power to keep its state. An e-ink device only needs to render a new page and then goes back to deep sleep. There is no use for the clutter toolkit, since animation is impossible on e-ink. OI uses X and the Enlightenment Foundation Libraries (EFL), which the OI team found to be feature-rich, yet fast and lightweight and thus well-suited for limited hardware. EFL's memory footprint is smaller than that of the GTK or Qt libraries (the latter requiring libstdc++). Since the OI team had bad experiences with GTK's slow performance on the Nokia N770, they wanted to try something else. While EFL turned out not to be as lean as hoped for, they consider it a good choice for a device such as the original V3 with its slow CPU and only 16 MB of RAM.

For development, OI uses the familiar array of open source tools: git repository, bugtracker, and documentation wiki (which is a bit outdated, as documentation tends to be). The mailing list is low volume and the IRC channel isn't crowded and thus friendly to newcomers.

Localization is done with Transifex. The UI strings are few and short, so it was not much of an effort for your author to contribute a few German translations. But not all text is in gettext yet, so would-be-translators may want to wait until the 0.2 release gets closer. The system uses UTF-8 and supports right-to-left text, so that any language supported by Unicode may become a user interface choice.

Commercial e-books and DRM

The OI software stack does not handle content "protected" with DRM, so most commercial e-book downloads available today cannot be read on an OI device. The team is not opposed to DRM per se, but to make it part of the distribution, it would have to be fully open source and may not rely on hardware to enforce its restrictions. That is rather tough to implement, so it is safe to expect that there will be no DRM found in OI in the foreseeable future.

You will find plenty of legal, DRM-free content at places like the Gutenberg Project — time to catch up on the classics. For web content, tools like Calibre, Readability, and many other PDF and e-book format converters will bring your morning paper (or LWN) onto your e-book reader. Maybe the publishing industry will see the light and offer DRM-free commercial downloads soon, just like the music industry has started to do after it went through a painful learning process.

Help wanted. Apply within

OI is a well-managed project. Alexander jokes that the quick and dirty hacks he found in the commercial e-book firmware sources would never make it past Mikhail. But the project does have a serious lack of manpower. Next to the three main developers, there are only a few casual contributors.

The current development trunk is very much work in progress, and not suitable for end users, but beta testing it is already fun. The PDF viewer is still too slow and the OI user interface is inconsistent. Alexander describes the team as a group of engineers, not usability professionals, and your author wholeheartedly agrees.

OI looks like a good foundation and the team would welcome commercial manufacturers joining the effort. The team's current work to port OI to the N516 is commissioned by Russian Ukrainian hardware distributor Azbooka (Азбука), who plans to sell N516 devices with OI as the official firmware. Their target audience is students and young budget-oriented users. Alexey Sednev of Azbooka is excited about the open source nature of OI and calls it "the greatest feature" of the Azbooka N516. He expects that OI will encourage software development by device owners and that this will help foster customization for specific user groups such as education, medicine, or law.

The team hopes to port the software to more hardware, so OI will soon need to add abstraction layers for device-specific input methods, storage media, and network devices. OI could also be a chance at new life for devices abandoned by their manufacturers, allowing users to avoid planned obsolescence, which the manufacturers create by not providing new firmware for "old" products. The Sony PRS-505 may become the third supported e-reader, as there are only a few driver details missing. They are confident that it is possible to port OI to any hardware, including the Kindle, but lack of manpower and time is stopping them. They need the help of device owners willing to write and maintain drivers. If you are a kernel developer with an e-ink reader lying around, you may just have found an exciting new hacking target.

Comments (9 posted)

LPC: 25 years of X

The X Window System quietly hit its 25th anniversary back in June; it is, undoubtedly, one of the oldest and most successful free software projects in existence. Keith Packard has been working with X for most of that time; at the Linux Plumbers Conference in Portland he used his keynote address to look at the highlights (and lowlights) of those 25 years and some of the lessons that have been learned.

The version of X we know today is X11. There were nine predecessor versions (one got skipped), but the first version to escape widely was X10, which was released in 1986. Companies were shipping it, and the vendors which formed the X Consortium were starting to think that the job was done, but the X developers successfully pleaded for the opportunity to make one more "small" set of revisions to the X protocol. The result was X11 - a complete reworking of the whole system - which was released on September 15, 1987; it is still running today.

There was a wealth of new ideas in X11, some of which made more sense than others. One of those ideas was the notion of an external window manager. In X, the window manager is just another process working with the same API. This approach helped to create a consistent API across windows, and it also made it possible to manage broken (non-responding) applications in a way that some other systems still can't do. On the other hand, the external window manager created a lot of on-screen flashing - a problem which still pops up today - and it does not work entirely well with modern compositing techniques, getting in the way of the page-flipping operations needed to make things fast.

The use of selections for cut-and-paste operations was another early X11 innovation. With selections, the source of selected data advertises its availability, and the destination requests it in the desired format. This mechanism allows data to be selected and moved between applications in almost any format. Unfortunately, the "cut buffer" concept was left in, so applications had to support both modes; the fact that Emacs was not updated to use selections for a very long time did not help. The existence of multiple selections created interoperability problems between applications. On the other hand, the selection mechanism proved to be a very nice foundation for drag-and-drop interfaces, and it handled the transition to Unicode easily.

Input has been the source of a number of problems. The requirement that applications specify which events they want made sense when the focus was on trying to make the best use of a network connection, but it led to some interesting behavioral changes depending on how applications selected their events. X was meant to be a policy-free system, but, in retrospect, the rules for event delivery were a significant amount of policy wired into the lowest levels of the system.

"Grabs," where an application can request exclusive delivery of specific events, were a case in point. "Passive grabs" allow window managers to bind to specific keys (think alt-middle to resize a window), but that required a non-intuitive "parent window gets it first" policy when these grabs are in use. "Synchronous grabs" were worse. They were intended to help create responsive interfaces in the face of slow networks and slow applications; clicking on a window and typing there will do the right thing, even if the system is slow to respond to the click and direct keyboard focus correctly. It was a complicated system, hard to program to, harder to test, and it required potentially infinite event storage in the X server. And it's really unnecessary; no applications use it now. This "feature" is getting in the way of more useful features, like event redirection; it may eventually have to be removed even at the cost of breaking the X11 protocol.

Text input was not without problems of its own; X went to considerable effort to describe what was written on every key, and required applications to deal with details like keyboard maps and modifier keys. It worked reasonably well for English-language input, but poorly indeed for Asian languages. The addition of the XIM internationalization layer did not really help; it was all shoved into the Xlib library and required that applications be rewritten. It also forced the installation of a large set of core fonts, despite the fact that most of them would never be used.

Text output was "an even bigger disaster." It required that fonts be resident in the server; applications then needed to pull down large sets of font metrics to start up. That was bad enough, but generating the font metrics required the server to actually rasterize all of the glyphs - not fun when dealing with large Asian fonts. Adding fonts to the system was an exercise in pain, and Unicode "never happened" in this subsystem. In retrospect, Keith says, there was an obvious warning in the fact that neither FrameMaker nor Xdvi - the two applications trying to do serious text output at that time - used the core fonts mechanism.

This warning might have been heeded by moving font handling into clients (as eventually happened), but what was done at that time, instead, was to layer on a whole set of new kludges. Font servers were introduced to save space and make addition of fonts easier. The XLFD (X logical font description) mechanism inflicted font names like:

    -adobe-courier-medium-r-normal--14-100-100-100-m-90-iso8859-1

on the world without making life easier for anybody. The compound text mechanism brought things forward to iso-2022, but couldn't handle Unicode - and, once again, it required rewriting applications.

The X drawing model had amusing problems of its own. It was meant to be "PostScript lite," but, to get there, it dispensed with small concepts like paths, splines, and transforms, and it required the use of circular pens. So there really wasn't much of PostScript left. The model required precise pixelization, except when zero-width "thin" lines were used - but all applications ended up using thin lines. Precise pixelization was a nice concept, and it was easily tested, but it was painfully slow in practice.

The use of circular pens was the source of more pain; the idea was taken from the PostScript "Red Book," but, by then, the PostScript folks had already figured out that they were hard to work with and had kludged around the problem. A line drawn with a circular pen, in the absence of antialiasing, tends to vary in width - it looks blobby. The generation of these lines also required the calculation of square roots in the server, which was not the way to get the best performance. Even so, people had figured out how to do circular pens right, but nobody in the X team knew about that work, so X did not benefit from it.

Rather than provide splines, the X11 protocol allowed for the drawing of ellipses. But there was a catch: ellipses had to be aligned with the X or Y axis, no diagonal ellipses allowed. There was a reason for this: there was a rumor circulating in those days that the drawing of non-axis-aligned ellipses involved a patented algorithm, and, for all of the usual reasons, nobody wanted to go and actually look it up. It turns out that the method had been published in 1967, so any patent which might have existed would have been expired. But nobody knew that because nobody was willing to take the risks involved with researching the alleged patent; even in the 1980's, software patents were creating problems.

As an added bonus, the combination of ellipses and circular pens requires the evaluation of quartic equations. Doing that job properly requires the use of 128-bit arithmetic; 64-bit floating-point numbers were not up to the job.

Color management was bolted on at a late date; it, too, was shoved into the "thin and light" Xlib layer. It provided lots of nice primitives for dealing with colors in the CIE color space, despite the fact that users generally prefer to identify colors with names like "red." So nobody ever used the color space features. And the "color management" code only worked with X; there was no provision for matching colors in output to graphic metafiles or printed output. X color management was never a big hit.

[PULL QUOTE: All of these mistakes notwithstanding, one should not overlook the success of X as free software. END QUOTE] All of these mistakes notwithstanding, one should not overlook the success of X as free software. X predates version 1 of the GPL by some five years. Once the GPL came out, Richard Stallman was a regular visitor to the X Consortium's offices; he would ask, in that persistent way he has, for X to change licenses. That was not an option, though; the X Consortium was supported by a group of corporations which was entirely happy with the MIT license. But in retrospect, Keith says, "Richard was right."

X was an industry-supported project, open to "anybody but Sun." Sun's domination of the workstation market at that time was daunting to vendors; they thought that, if they could displace SunView with an industry-standard alternative, they would have an easier time breaking into that market. Jim Gettys sold this idea, nearly single-handedly, to Digital Equipment Corporation; it is, arguably, the first attempt to take over an existing market with free software. It worked: those vendors destroyed Sun's lock on the market - and, perhaps, Keith noted, the Unix workstation market as a whole.

There were problems, needless to say. The MIT license discourages sharing of code, so every vendor took the X code and created its own, closed fork. No patches ever came back to the free version of X from those vendors. Beyond that, while the implementation of X11 was done mainly at DEC, the maintenance of the code was assigned to the X Consortium at MIT. At that point, Keith said, all innovation on X simply stopped. Projects which came out of the X Consortium in these days were invariably absolute failures: XIE, PEX, XIM, XCMS, etc. There began the long, dark period in which X essentially stagnated.

X is no longer stagnant; it is being heavily developed under freedesktop.org. As X has come back to life, its developers have had to do a massive amount of code cleanup. Keith has figured out a fail-safe method for the removal of cruft from an old code base. The steps, he said, are these:

1. Publish a protocol specification and promise that there will be long-term support.

2. Realize failure.

3. "Accidentally" break things in the code.

4. Let a few years go by, and note that nobody has complained about the broken features.

5. Remove the code since it is obviously not being used.

Under this model, the XCMS subsystem was broken for five years without any complaints. The DGA code has recently been seen to have been broken for as long. The technique works, so Keith encouraged the audience to "go forth and introduce bugs."

The important conclusion, though, is that, after 25 years, X survives and is going strong. It is still able to support 20-year-old applications. There are few free software projects which can make that sort of claim. For all its glitches, kludges, and problems, the X Window System is a clear success.

Comments (63 posted)

FOSS compliance engineering in the embedded industry

[ Editor's note: This is part two of a series of three articles on FOSS license compliance. Part one introduces the topic and describes what developers can do to protect their rights. Part three is coming soon and will look at what companies can do to comply, as well as what to do in the case of a violation. ]

This article examines a field called compliance engineering. Compliance engineering was pioneered by technical experts who wanted to address misuses of software, and was made famous by gpl-violations.org, FSF, and similar organizations correcting Free and Open Source Software (FOSS) license violations. The field has grown into a commercial segment with companies like Blackduck Software and consultancy firms like Loohuis Consulting offering formal services to third parties.

Rather than attempting to examine compliance engineering in all market segments and under all conditions, this article will focus on explaining some of the tools and skills required to undertake due diligence activities related to licensing and binary code in the embedded industry. It is based on the GPL Compliance Engineering Guide, which in turn is based on the experience of engineers contributing to the gpl-violations.org project.

Some of the methods described in this article may not be permitted by the DMCA or similar legislation in certain jurisdictions. It is important to stress that the goal of compliance engineering is not to reverse engineer a product so it can be resold for monetary gain, but rather to apply digital forensics to see if copyright was violated. You should consult a lawyer to find out the legal status of the engineering methods described here.

Context and confusion

The first phase of compliance engineering is not engineering. It is about about understanding the license that applies to code and understanding what that means with regards to obligations in a particular market segment. This dry art is sometimes challenging because of the culture of FOSS. FOSS has an innovative, fast moving, and diverse ecosystem. Contributors tend to be passionate about their work and about how it is released, shared, and further improved by the community as a whole. This can be something of a double-edged sword, providing exceptional engagement and occasionally an overabundance of enthusiasm in areas like software licensing or compliance.

The gpl-violations.org project enforces the copyright of Harald Welte and other Linux kernel developers, and has a mechanism for third parties to report suspected issues with use of Linux and related GPL code. One of the most common false positives reported is that companies are violating the GNU GPL version 2 by providing a binary firmware release for embedded devices without shipping source code in the package or offering it on a website for download. This highlights a misunderstanding regarding what the GPL requires. It is true that the GPL comes into effect when distributing code and that offering a binary firmware for download is distribution, but compliance with the license terms is more subtle than it may appear to parties who have not read the license carefully.

In the GPLv2 license there is no requirement for source code to be provided in the product package or on a website to ensure compliance. Instead, in sections 3a and 3b of the GPLv2 license there are two options regarding source code available to people distributing binary versions of licensed software. One is to accompany a product with the source code and the other is to include a written offer to supply the source code to any third party for three years. When someone gets a device with GPLv2 code and wants to check compliance, they need to look for accompanying source or a written offer on the manual, the box, a separate leaflet, web interface menus and any interactive menus.

It gets a little more complex when you consider that the above constitutes only the terms applying to source code. Finding source code or a written offer for it does not constitute GPLv2 full compliance. Instead compliance depends on whether the offered source code is complete and corresponds precisely to what is on the product, if the product also shipped with a copy of the license, and what else is shipped in what way alongside the GPL code. The full text of the license spells out how the parameters of this relationship work.

Compliance engineering is an activity that requires a mixture of technical and legal skills. Practitioners have to identify false positives and negatives, and to contextualize their analysis within applicable jurisdictional constraints. This can appear daunting for parties who have a casual approach to reading licenses. However, the skills and tools applied are relatively simple as long as a balanced approach is taken when understanding what is explicitly required in a license and what is actually present in a product. Given these two skills anyone can help make sure that people who use GPL or other FOSS licenses are adhering to the terms the copyright holders selected.

The nuts and bolts

Compliance engineers in organizations like gpl-violations.org do not have an extensive toolset. In the embedded market the product from a software perspective is a firmware image, and this is just a compilation of binary code. The contents may include everything needed to power an embedded device (bootloader, plus operating system) or just updates to certain parts of the embedded device software.

Checking if firmware is meeting the terms of a license like the GPLv2 requires the application of knowledge and a sequence of tests such as extracting visible strings from binary files and correlating them to source code. One aspect is identifying GPL software components and making sure they are included in source releases, and another requires opening the device to get physical access to serial ports. The only essential tools required are a Linux machine, a good editor, binutils, util-linux, and the ability to mount file systems over loopback or tools like unsquashfs to unpack file systems to disk.

Opening firmware

The most common operating systems for embedded devices today are Linux-kernel based or VxWorks. There are a few specialized operating systems and variants of BSD available in the market, but they are becoming less common. Linux-based firmware nearly always contains the kernel itself, one or more file systems, and sometimes a bootloader.

The quickest way to find file systems or kernels in a firmware is to search for padding. Padding usually consists of NOP characters such as zeroes which fill up space. This ensures that the individual components of a firmware are at the right offsets. The bootloader uses these offsets to quickly jump to the location of the kernel or a file system. Therefore if you see padding there will either be something following it, or it marks the end of the file. Once you have identified the components you will know what type of firmware you are dealing with, what's in there on the architecture level, and (with a little bit of experience) what's likely to be problematic with regards complete source code releases.

If you can't find any padding in the firmware then another method is to look for strings like "done, booting the kernel", as these indicate that something else will follow immediately afterwards. This method is a little more tricky and involves things like searching for markers that indicate compression (gzip header, bzip2 header, etc.), a file system (squashfs header, cramfs header, etc.), and so on. The quickest way to do this is to use hexdump -C and search for headers. Detailed information about headers is already available on most Linux systems in /usr/share/magic.

Problems you can encounter

The techniques employed for compliance engineering are essentially the same as those employed for debugging an embedded system. While this means the basic knowledge is easy to obtain, but it also means that issues can arise when the tools you are attempting to apply are different from the tools used for designing and building the system in the first place:

• Encryption: Some devices have a firmware image that is encrypted. The bootloader decrypts it during boot time with a key that is stored in the device. Unless you know the decryption key it is impossible to take these devices apart by looking at the firmware only. Examples are ADSL modem/routers which are based on the Broadcom bcm63xx chipset. There are also companies that encrypt their firmware images using a simple XOR. It is often quite easy to find these if you see patterns that repeat themselves very often.
• Code changes: Sometimes slight changes were made to the file system code in the kernel, which make it hard or even impossible to mount a file system over loopback without adapting a kernel driver. Examples include Broadcom bcm63xx-based devices and devices based on the Texas Instruments AR7 chipset, which both use SquashFS implementations with some modifications to either the LZMA compression (AR7) or the file system code.

To explore what code is present in these cases you need network access or even physical access to the device.

Network scanning

With portscanners like nmap you can make a fairly accurate guesstimate of what a certain device is running by using fingerprinting: many network stacks respond slightly differently to different network packets. While a fingerprint is not enough to use as evidence, scanning can give you useful information, like which TCP ports are open and which services are running. Surprisingly often you can still find a running telnet daemon which will give you direct access to the device. Sometimes exploiting bugs in the web interface also allow you to download or transfer individual files or even the whole (decrypted) file system.

Physical access

Most embedded devices have a serial port, and this is sometimes the only way to find violations. This may not be visible and sometimes is only present as a series of solder pads on the internal board. After adding pin headers you can connect a serial port to the device and – perhaps with the addition of a voltage level shifter – attach the device to a PC. Projects like OpenWrt have a lot of hardware information on their website and this can be useful in working out how to start.

Once physical access is granted things get easier. The bootloader is usually configured to be accessible via the serial port for maintenance work such as uploading a new firmware, and this often translates into a shell starting via the serial port after device initialization. Many devices are shipped with GPL licensed bootloaders, such as RedBoot, u-boot, and others. The bootloader often comes preloaded on a device and is not included in firmware updates because the firmware update only overwrites parts of the flash and leaves the bootloader alone. More problematically, the bootloader may not be included in the source packages released by the vendor, as they overlook its status as GPL code.

Example: OpenWrt firmware

GPL compliance engineering is best demonstrated using a concrete example. In this example we will take apart a firmware from the OpenWrt project. OpenWrt is a project that makes a kit to build alternative firmwares for routers and some storage devices. There are prebuilt firmwares (as well as sources) available for download from the OpenWrt website. In this example we have taken firmware 8.09.1 for a generic brcm47xx device (openwrt-brcm47xx-squashfs.trx).

Running the strings command on the file seems to return random bytes, but if you look a bit deeper there is structure. The hexdump tool has a few options which come in really handy, such as -C which displays the hexadecimal offset of the file, the characters in hexadecimal notation and the ASCII representation of those characters, if available.

A trained eye will spot that at hex offset 0x001c there is the start of a gzip header, starting with the hex values 0x1f 0x8b 0x08:

    $ hexdump -C openwrt-brcm47xx-squashfs.trx
    00000000  48 44 52 30 00 10 22 00  28 fa 8b 1c 00 00 01 00  |HDR0..".(.......|
    00000010  1c 00 00 00 0c 09 00 00  00 d4 0b 00 1f 8b 08 00  |................|
    00000020  00 00 00 00 02 03 8d 57  5d 68 1c d7 15 fe e6 ce  |.......W]h......|
    ...

Extracting can be done using an editor, or easier with dd:

    $ dd if=openwrt-brcm47xx-squashfs.trx of=tmpfile bs=4 skip=7

This command reads the file openwrt-brcm47xx-squashfs.trx and outputs it to another file, skipping the first 28 bytes.

    $ file tmpfile
    tmpfile: gzip compressed data, from Unix, max compression

With zcat this file can be uncompressed to standard output and redirected to another file:

    $ zcat tmpfile > foo

The result in this particular case is not a Linux kernel image or a file system, but the LZMA loader used to uncompress the LZMA compressed kernel that is used by OpenWrt. LZMA does not always use the same headers for compressed files, which makes it quite easy to miss. In this case the LZMA compressed kernel can be found at offset 0x090c.

    $ dd if=openwrt-brcm47xx-squashfs.trx of=kernel.lzma bs=4 skip=579

Unpacking the kernel can be done using the lzma tool.

    $ lzma -cd kernel.lzma > bar

Running the strings tool on the result quite clearly shows strings from the Linux kernel.

In openwrt-brcm47xx-squashfs.trx you can see padding in action around hex offset 0x0bd280, immediately followed by a header for a little endian SquashFS file system.

    $ hexdump -C openwrt-brcm47xx-squashfs.trx
    ...
    000bd270  1d 09 36 96 85 67 df 8f  1b 25 ff c0 f8 ed 90 00  |..6..g...%......|
    000bd280  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
    *
    000bd400  68 73 71 73 9b 02 00 00  00 c6 e1 e2 d1 2a 00 00  |hsqs.........*..|
    ...

    $ dd if=openwrt-brcm47xx-squashfs.trx of=squashfs bs=16 skip=48448

From just the header of the file system it is not obvious which compression method is used:

    $ file squashfs
    squashfs: Squashfs filesystem, little endian, version 3.0, 1322493 bytes,\
    667 inodes, blocksize: 65536 bytes, created: Tue Jun  2 01:40:40 2009

The two most used compression techniques are zlib and LZMA, the latter becoming more popular quickly. Unpacking with the unsquashfs tool will give an error:

    zlib::uncompress failed, unknown error -3

This indicates that probably LZMA compression is used instead of zlib. Unpacking requires a version of unsquashfs that can handle LZMA. The OpenWrt source distribution contains all necessary configuration and buildscripts to fairly easily build a version of unsquashfs with LZMA support.

The OpenWrt example is fairly typical for real cases that are handled by gpl-violations.org, where unpacking the firmware is usually the step that takes the least effort, often just taking a few minutes. Matching the binary files to sources and correct configuration information and verifying that the sources and binaries match is a process that takes a lot more time.

In conclusion

Compliance engineering is a demanding and occasionally tedious aspect of the software field. Emotion has little place in the analysis applied and the rewards of volunteer work are not visible to most people. Yet compliance engineering is also essential, providing as it does a clear imperative for people to obey the terms of FOSS licenses. It contributes part of the certainty and stability necessary for diverse stakeholders to work together on common code, and it allows a clear mechanism for discovering which parties are misunderstanding their obligations as part of the broader ecosystem. Transactions between individuals, projects and businesses cannot be sustained without such mechanisms.

It is important to remember that the skills involved in compliance engineering are not necessarily limited to a small subset of consultants and companies. Documents like the GPL Compliance Engineering Guide describe how to dig through binary code suspected of issues. Engineers from all aspects of FOSS can contribute assistance to a project or business when it comes to forensic analysis or due diligence, and they can report any issues discovered to the copyright holders or to entities like FSF's Free Software Licensing and Compliance Lab, gpl-violations.org, FSFE's Freedom Task Force and Software Freedom Law Center.

Comments (4 posted)