Another patent battle for Android

In 2011, an auction was held for some 6,000 patents held by Nortel Networks. A consortium named Rockstar — formed by Microsoft, Apple, Sony, EMC, Blackberry (then Research In Motion), and Ericsson — competed in the bidding against Google. Rockstar won the bidding for a staggering $4.5 billion, roughly $750,000 per patent. Google, and its Chief Legal Officer David Drummond, were concerned at the time about those patents being used against Android — something that has now come to pass.

Google chose not to get involved with Rockstar, despite being invited to join the consortium. Drummond explained that the company refused to join because it suspected that the acquisition terms would not have included extending patent licenses to Android and Android manufacturers.

Drummond turned out to be right about what the Nortel patents would be used for. Two weeks ago, Rockstar filed eight lawsuits in the plaintiff-friendly Eastern District of Texas; one against Google, and seven against the major Android OEMs — Samsung, HTC, Huawei, LG, Asus, Pantech, and ZTE — for infringing patents from Nortel.

Although there are eight lawsuits in total, there are effectively only two different legal battlegrounds here. Google faces claims of infringing seven patents that cover an "associative search engine" invention. Six of those are "continuing patents": that is, they are patents that follow on one or more earlier patents in the "series", as improvements to the original invention. The original patent was 6,098,065 (filed in 1997), and the six continuing patents (filed from 1999 to 2007) are: 7,236,969, 7,469,245, 7,672,970, 7,895,178, 7,895,183, and 7,933,883.

These patents are largely very similar, and all claim "an advertisement machine which provides advertisements to a user searching for desired information within a data network". The "base invention" claimed describes an online search engine that provides results by correlating the search string with relevant entries in a database of results, using profile information from the searcher to help provide better results for that user. The continuing patents extend upon this "base", until we get to the last patent, number 7,933,883, which adds: a secondary database of advertisements, which the search string is matched against to provide targeted advertisements; multiple systems for profiling users of the search engine; and using the searcher's profile in combination with their search string to provide targeted advertisements to the searcher along with their search results.

So Rockstar is claiming that Google's AdWords, one of Google's main sources of income, is infringing seven of Rockstar's patents. That's a bold attack: Rockstar has fired missiles at the heart of Google's revenue stream. Given the gravity of the claims, a countersuit from Google against the consortium organizers as a reprisal seems likely.

The lawsuits against the Android OEMs all claim that a different set of patents are infringed by at least some of their respective Android devices. The specific patents claimed are:

• Patent 5,838,551: Filed in 1996, the invention simplifies circuit board design by eliminating the need to connect electromagnetic interference (EMI) shields to boards via solder traces by using instead an electrical connection to a "rigid planar dielectric substrate", such as "a printed circuit board or a ceramic substrate". [Not asserted against Pantech or ZTE.]

• Patent 6,037,937: Filed in 1997, covers an overlay of a "control tool" over content shown on a screen to provide for improved user navigation through a graphical user interface; this is an improvement over the use of hardware buttons or additional devices to conduct the navigation.

• Patent 6,128,298: Filed in 1997: a device that provides internet access to "nodes of private networks"; the device "presents a single IP address to the internet and uses a plurality of IP ports to solve the problem of IP address conservation". This invention could read on network address translation (NAT), like that used in mobile wireless Internet hotspots.

• Patent 6,333,973: Filed in 1997: the invention details an "Integrated message center" which "consolidate[s] [notification] messages of different types for viewing and manipulation by a user". Could be read against Android's notification shade, which centralizes the display of different notifications. [Not asserted against Pantech]

• Patent 6,463,131: Filed in 2000: "a system and method" which allows users to distinguish between different notifications by customizing how they are received. For example, different ring tones could be used to signal different callers, or to distinguish a text from a call. This patent could read on Android notifications.

• Patent 6,765,591: Filed in 1999: a graphical user interface for "managing a virtual private network" (VPN).

• Patent 6,937,572: Filed in 2000: tracing Voice over IP calls, providing one or more different types of trace information, including: IP address, the type of device making the call, and a call-back number.

All of these lawsuits claim willful infringement by the defendants. If proven, that leads to treble damages — a tripling of the final damage award after damages for all other patent infringement claims are calculated. In Rockstar's written claim against Google, it refers to Google's failed efforts to buy the Nortel patents as evidence that Google knew it was infringing these patents and was trying to buy itself a license. This argument is analogous to claiming that people who buy house insurance know that their house is going to burn down.

As Rockstar is a non-practicing patent-holding entity (i.e. a patent troll) — it does not actually make any products — Rockstar is probably more interested in extracting money out of Google and the Android OEMs than in getting an injunction, although claims for injunctions as remedies are included in the lawsuits. The lawsuits against the OEMs are only the latest in a series of efforts over the last few years to use patents against Android device manufacturers for a variety of reasons, from raising the costs of offering products based on open source software to simply extracting money from a booming industry.

We have yet to hear a public statement from the defendants about the Rockstar lawsuit. But we can expect Google and at least some of the OEMs to defend themselves. It is possible that some of the OEMs will settle with Rockstar. However, long and drawn out court battles fighting back against Rockstar, including demands that the patents be reexamined as potentially invalid due to obviousness and/or a lack of novelty in light of prior art, are to be expected. There is also a strong possibility of a countersuit from Google against the most powerful of Rockstar's organizers: Microsoft and Apple.

Patent litigation in the smartphone and mobile device space have been heating up for years, with some dramatic results, like that seen in Apple v. Samsung. But these lawsuits — simultaneously attacking every major Android OEM while also firing directly at Google's main profit stream — are the most audacious seen so far.

Comments (26 posted)

Prototyping with Pencil (the other one)

Earlier this year I was reminded of one of the peculiar joys of free software: the fact that (trademarks aside) anyone can name a project anything they like, even if that project name is already in use. Specifically, when comparing the various parallel forks of the Pencil cell-animation application in June, there were numerous false-positive search engine hits caused by Pencil, the entirely unrelated open source application for making graphical user interface mock-ups. The mock-up tool recently made a new release, so a fresh look at it seems in order.

This "Pencil" is a visual prototyping system. Users can draw simple interface elements onto mock-up screens like one might do with a generic drawing application such as Inkscape, but Pencil goes a few steps further. First, the application ships with several loadable collections of UI elements taken from existing operating systems and platforms. These "stencil" collections (as they are called) include GTK+, Android, iOS, and an assortment of web application frameworks, plus several generic options. Second, Pencil supports linking multiple mock-ups through clickable UI elements, so it is possible to create simple interactive mock-ups rather than mere static images. Finally, the application can export its mock-ups to some interesting output formats, such as linked web pages (again, helpful when creating interactive prototypes).

Version 2.0.5 was released in late September, following on from 2.0.3 in June. Both introduced new features, after a considerable gap since the previous update in 2012. Pencil is based on Mozilla's XUL runtime, and it can be downloaded as a standalone application or installed as a Firefox extension. Linux builds of the standalone version are provided as Ubuntu and Fedora packages as well as a tarball. The Firefox extension is provided only on the project's downloads page—and is not available through Mozilla's official Add-ons site—which prompts Firefox to display a big scary warning about installing software from unknown sources when one tries to install it.

It is not easy to say which installation option is better; Pencil is a heavyweight among add-ons and I consistently found it to run slower than the standalone version (and to slow down web browsing). On the other hand, the installable packages will conflict with the "Pencil" animation application, since both want to install /usr/bin/pencil. It seems like a little package polishing should enable peaceful coexistence, but thus far neither project seems interested in renaming its own binary.

When launched, the Pencil interface sports a large drawing canvas and a collapsible tree-view palette showing all of the installed UI element stencils. Adding elements to the drawing is a simple drag-and-drop; most elements are an image with optional text fields overlaid on top. That means nothing (other than common sense) prevents the user from mixing iOS, GTK, Windows, and web elements on a single drawing. The text fields are editable with a double click, so that the user can apply appropriate labels and text-entry content.

At this level of editing, creating a mock-up is trivial—or, perhaps, the mechanics of creating the mock-up are trivial, while proper UI design remains the real challenge. But what makes Pencil more useful than a collection of clip-art images is how it bakes in features to automatically guide the user in the right direction, and how it hides its more complex functionality while still making it available when needed.

For example, all UI elements have handles at the four corners of their bounding box, plus at the horizontal and vertical midpoints. Whenever an element is being dragged, as its midpoint nears the midpoint of something beneath it, a guide line appears and the user can snap the element to the guide to automatically center it. Nothing looks worse than a UI where things are slightly misaligned, after all. The same feature is available to snap elements to the top, bottom, or sides of other elements. And the snap function is smart enough to align items to the "active" area of the element underneath. This means that elements will snap to alignment with the screen of the "phone" mock-ups, rather than to the outside edge of the device.

For comparison, while Inkscape offers a slew of alignment and spacing tools, Pencil makes it difficult to not line things up correctly. Similarly, Pencil elements can be resized without distortion by grabbing one of the handles and dragging. In Inkscape dragging a handle scales the entire object (including changing the width of the lines), leaving it distorted. Pencil only scales the empty space inside the element, leaving its lines un-mangled. There are ways around that problem in Inkscape, but Pencil builds the feature into the structure of the UI elements itself.

At the same time, each element has a number of editable properties that can be changed from the right-click menu. Changing text labels is the most common operation, so that is the double-click behavior, but the rest can be altered if necessary. These properties include basics like color and font settings, but they include more complex options, too. For instance, UI elements can be grouped together, and each element in the group can have a different "sizing policy" that controls what happens when the entire group is resized. That lets users create things like relative-width web page designs, where some fields (like menus) stay the same size when the page is resized, but others (like text blocks) expand to fill the available space.

Although most UI elements are image-based, some offer more involved features and generally provide advanced functionality. The "Placeholder Text" stencil offers lorem ipsum text blocks (and its properties include adjustable margins), scrollbar elements can be scrolled up or down, and so on. It is a bit of work to build an interactive prototype, since each variation of the UI (button unpressed, button pressed, etc.) needs to be created as a separate canvas image, but Pencil saves some duplication of effort by letting the user make a copy of the current canvas rather than starting from scratch.

Pencil is certainly not free from problems. Sometimes when dragging an element from the element palette, the element disappears when the cursor reaches the canvas. There also does not appear to be a list view of elements on the canvas, so if one is hidden by another, it is impossible to select it. Probably the biggest practical limitation is the freshness of the stencil sets, however. The GTK+ collection, for example, is clearly a GTK2-era design, and there does not seem to be any urgency to update it. There seems to be no Qt collection at all, nor (ironically) a Firefox/Thunderbird collection. Admittedly, the collection that is the most fun to use is the "Sketchy" set that looks like genuine drawn-on-the-back-of-a-napkin mock-ups, but updates to the collections for Linux and web platforms that make them as current as the Android and iOS offerings would be nice.

Most of the professional UI and UX designers in the free software world seem to have gotten comfortable creating mock-ups in Gimp, Inkscape, and even Blender, so retraining on a different application may not sound appealing. Novices, however, will probably find Pencil easier to learn than a general-purpose drawing application. But it is possible that Pencil offers something worthwhile to interaction designers, too, and they may not be aware of it—after all, there are plenty of other Pencils available to choose from.

Comments (4 posted)

Progress on smaller and more colorful fonts

Concurrent with the central program of the 2013 ATypI conference in Amsterdam were various side meetings and workshops—not to mention the informal hallway discussions that are common to all technology conferences. In this case, the different side tracks resulted in some forward motion on some specifications that are likely to affect font development and software support for several years to come. The biggest is probably the Web Open Font Format version 2 (WOFF2), a proposed revision to the format used to deliver compressed font files over the web. WOFF 1.0 is still quite new, but Google is keen to update the format with support for a newly-released compression algorithm. At the same time, both of the two competing proposals for encoding color into fonts also moved forward, suggesting that the contest is far from over.

WOFF2

WOFF1 reached World Wide Web Consortium (W3C) "recommended" status in December 2012, but work was underway for a successor as early as March 2012. The format is intended to lossless-ly compress a font file for HTTP transmission. "Lossless" in this case means that the WOFF file retains the same glyphs as the input TrueType or OpenType font; the standard allows the WOFF creator to subset the characters included and remove unwanted tables (e.g., tables for character mappings, metrics, kerning, tracking, etc.). The file format is not simply a gzipped TTF, however: each data table in the font is compressed separately, so that applications only need to decompress the parts they need.

The first version of WOFF uses zlib's compress2() as the compression algorithm, which is a no-nonsense choice—after all, implementations are widely available and the algorithm is unencumbered with patents, which makes the W3C happy. But Google, purveyor of the largest web font–delivery service, was interested in improving on the compression in two respects: further reducing the size of the files and making decompression faster.

Reducing file size is an obvious improvement for any compression system, but the optimize-for-decompression model used for serving up the files might mean making different trade-offs than one would in a general-purpose algorithm. The font files only need to be compressed once, but need to be decompressed by every client—in browsers, the lag between loading page text and the application of the web font to that text is a common enough irritant that it has become known as FOUT ("flash of unstyled text"). Plus, optimizing decompression at the cost of more complex compression could help reduce the load on less powerful mobile devices.

Google's initial attempt to improve on WOFF1's compression used the LZMA entropy coder, but that algorithm proved aggravating on a number of fronts. First, its only documentation (much less specification) is sample code. Second, its lead developer was uninterested in working to incorporate LZMA into WOFF or other standards—a task that could involve time on his part for tasks like a rigorous security review. Third, although LZMA achieved smaller file sizes than zlib, it fell short on the goal of speeding up decompression.

The team at Google, led by Raph Levien and David Kuettel, reached out to other offices within the company and found a viable alternative. Jyrki Alakuijala and Zoltan Szabadka (who had previously worked on WebP compression) were already working on a variant of the Flate algorithm called Zopfli. They were able to further adapt their work into a new algorithm optimized for WOFF2. Called Brotli, the algorithm results in file sizes comparable to LZMA's (though a bit larger), but drastically faster decompression. Levien cited data rates of 120 to 300 MB/s decompression on the Google Fonts collection, compared to 20-30 MB/s for LZMA. The average file size is 29% smaller than WOFF1.

Google enabled the use of WOFF2 with Brotli as a runtime option for Chrome's "Canary" test builds in July 2013, and presumably has continued to tweak the algorithm based on what it has learned in that process. Keuttel has subsequently posted several updates to the W3C WebFonts Working Group mailing list, reporting the results of tests done on other font libraries. Most recently, on November 6, he noted additional improvements to the average decompression speed that came at the cost of altering the bit-stream format. That change had not yet been released in the open source code as of press time. Google also noted that the Brotli algorithm has not been optimized at all (in comparison to decades of optimization efforts for zlib), so hopefully with additional work there will be additional performance gains.

Improving the compression algorithm is the primary aim of WOFF2, but there are a few incidental improvements thrown in as well. Monotype's earlier MicroType Express (MTX) format proposal introduced some space-saving optimizations, too, like replacing composite glyphs (e.g., accented characters) with references to the original glyphs (e.g., the unaccented character and the accent mark), and transforming the tables in a font in order to take advantage of redundancy (for instance, WOFF1 required every glyph to have a bounding box, but in practice many glyphs' bounding boxes are identical and thus redundant). Google's Brotli-based WOFF2 reuses those ideas from MTX, and adds a few more, such as allowing some or all of the font file's tables to be compressed together, rather than requiring each table to be handled separately.

After the ATypI meeting, the WebFonts Working Group released its Evaluation Report for WOFF2, the first official publication in the publication-heavy process of W3C standardization. File compression fans will be happy to hear that Brotli is moving toward standardization, too; Google's Kenji Baheux posted a preliminary specification for Brotli to the mailing list after ATypI.

Outside of WOFF2 development, the WebFonts Working Group has looked at two other questions, but without resolution. The first was building support into WOFF for TrueType Collection (TTC) files. These are essentially bundles of multiple TTF fonts (such as a regular, bold, and italic) compacted together. Some people feel that delivering TTCs (instead of multiple TTFs compressed into multiple WOFFs) would further improve compression efficiency. The trouble is that in the real world, virtually no one publishes TTCs. Finally, Monotype's Vladimir Levantovsky resurrected a proposal to add "font" as a top-level MIME filetype with the IETF. Doing so might simplify the semantics of further standards work—right now, all fonts are registered underneath the "application" catch-all MIME type, like application/font-woff. As with TTC, however, what seems to be missing is motivation to push for the change. The reality is that what is in use today is good enough.

Colorful language

While TTC support and MIME-type registration languish, there is an abundance of interest in the area of standardization for chromatic fonts (i.e., fonts with color elements). As we discussed in August, there are two competing proposals from different players. Microsoft has been pushing for adding color index tables to the OpenType specification, which for historical reasons is managed by the MPEG body of the ISO. The W3C has a community group that is backing a different solution that adds SVG to OpenType instead. The W3C proposal was developed by Mozilla and Adobe.

Neither group has blinked yet. The W3C camp released its final proposal on October 9, notably with the additional backing of Monotype. On November 1, MPEG published its formal call for proposals for OpenType color support.

One might well ask whether or not the W3C group could simply submit its SVG-based proposal to MPEG. But the specifics of the MPEG call for proposals may make that difficult; among the listed requirements for submissions is "Low implementation complexity," which states that a proposal "shall not introduce significant burden on implementers and shall be easily implemented on various platforms including devices with limited capabilities and constrained memory / CPU resources". That language was certainly not invented to exclude SVG from consideration, but even die-hard SVG fans would probably agree that the format is rarely described as a "low implementation complexity" one.

The most probable outcome is that both proposals will be approved by their respective standards bodies; that is frequently what happens when standards-body proliferation goes unchecked. But the most important lesson may be that Microsoft has learned which standards bodies it can work with and which it cannot. WOFF actually began as an answer to Microsoft's Embedded OpenType (EOT) proposal, a compressed font format that explicitly supported DRM-like restrictions. But the EOT submission to the W3C never garnered outside support, and WOFF beat it handily. Years later when the chromatic font discussions began, it seems, Microsoft decided to skip the W3C and head straight for MPEG.

The W3C's process is not the fastest in the world, but it does have the benefit of requiring consensus between disparate parties. As the Encrypted Media Extensions (EME) debate has shown, the W3C process does not always reflect the will of everyone who uses the web. But it is more resilient against single-vendor solutions. Like a lot of plumbing underneath the web, users may not notice WOFF2 at all (aside from less-frequent FOUT annoyances), but they will notice chromatic fonts. Hopefully the dueling proposals will get cleanly resolved without years of frustrating incompatibility—but the more officially-blessed standards there are, the less likely that could be.

Comments (10 posted)

Email insecurities

As the software development world continues to react to the Edward Snowden revelations about pervasive government surveillance, a lot of attention has been paid not just to hardening the various implementations of core Internet services against exploitation, but to what needs to be fixed in the core protocols as well. While there is clear room for improvement where web traffic is concerned—from the certificate authority system to SSL/TLS—there is far less agreement on what can be done with email. Some bold new projects have been announced, but it remains to be seen if replacing SMTP or IMAP can put a stop to the real threat posed by spying conducted by law enforcement agencies.

Lava down

Prior to August 8, 2013, Lavabit offered an encrypted email service that boasted of second-to-none privacy protection for its users. The cornerstone of that protection was that user data was securely stored to the point that not even Lavabit itself could decrypt and read any users' stored messages. In July, however, news broke that Edward Snowden was a user of the service, and the US government got a search warrant requiring Lavabit to hand over its private SSL keys so that investigators could examine the account of an unnamed customer—presumably Snowden. Lavabit objected to the warrant, arguing that surrendering the keys would expose not just the account named in the request, but all of its other customers, too. The courts did not regard that complaint as particularly persuasive, and ordered Lavabit to surrender the keys immediately or face a fine of $5,000 per day. On August 8, the company turned over the keys, and shut down the email service.

Because Lavabit stored customer messages in encrypted form on its servers, the supposition of many was that the SSL keys could only be used to tap connections between clients and servers. Thus, by shutting down the service, Lavabit was making it impossible for the government to eavesdrop on the SSL connections, since none were taking place.

Although this string of incidents was particularly high-profile, it was not the only one of its kind. On August 9, another encrypted email service provider, Silent Circle, shut down its service as well, citing the Lavabit case as the cause. Silent Circle then proceeded to erase its private keys, even though they had not been requested by the government.

The service shutdowns might be regarded as nothing but two isolated closures (albeit casualties of government interference), except that Lavabit and Silent Circle subsequently announced the Dark Mail Alliance, a joint project with the stated mission of bringing "the world our unique end-to-end encrypted protocol and architecture that is the 'next-generation' of private and secure email." Dark Mail was announced on October 30, and the announcement says that the group will make both the system architecture and the protocol open source. But, other than that (certainly admirable) goal, no visible work has emerged from the project yet.

The dark side

Despite the general agreement that email needs a major overhaul—and that PGP-style encryption is probably not going to catch on in a big way—not everyone finds the approach taken by Lavabit worth following. On his blog, Moxie Marlinspike posted an in-depth critique of Lavabit's design, noting in particular that the company's claim that customer email could not be read by Lavabit administrators seemed to be entirely untrue. Lavabit did store messages in encrypted form on the server side, but it also stored the decryption key and that key's password on the server.

In fact, Marlinspike noted, the government's warrant requesting Lavabit's SSL keys suggests that the government was more interested in decrypting historical SSL traffic that it had collected, rather than tapping new connections. If true, of course, then Lavabit's shutdown means the problem won't get any worse (since no new traffic is there to be collected), but it does not protect the service's users against the real threat.

Marlinspike recommends two other email projects worth following rather than further work from the Lavabit team. Although he has not made comments about Dark Mail directly, Marlinspike does express disinterest in donating to Lavabit founder Ladar Levinson's Kickstarter project, which involves both releasing the Lavabit source code and developing Dark Mail. The Kickstarter project is titled "Lavabit's Dark Mail Initiative" and says:

Marlinspike concludes his analysis with words of caution about Lavabit:

Instead, Marlinspike points his readers toward Mailpile and the Leap Encryption Access Project (LEAP). Mailpile (which we looked at in September), is a local mail server with a web UI that does not rely on third-party storage. LEAP is an effort to build an easy-to-deploy encryption system for service providers. Email is one of several use-cases targeted by the project. Marlinspike also suggests following Trevor Perrin on Twitter in order to follow the latest on Perrin's work developing a secure email protocol.

Of course, even that list of secure email replacements is far from exhaustive. At least five others are mentioned in the comments on Marlinspike's blog post (BitMail, FlowingMail, Mailvelope, Pond, and Scramble). Ultimately it is impossible to meaningfully assess the security of any protocol or application that has not yet been deployed, so the final word on the Dark Mail Alliance remains out for the foreseeable future. As Marlinspike's critique points out, however, high publicity does not guarantee security. The Lavabit shutdown debacle certainly had the world's attention, but the approach it took to security might not be the best one to bank on from here on out.

Comments (9 posted)

Security quotes of the week

— Sam Hartman

— ComputerWeekly.com

— Dan Geer (worth reading in full)

Comments (5 posted)

A Critique of Website Traffic Fingerprinting Attacks

Mike Perry has written a detailed article posted at the Tor site that looks at "website traffic fingerprinting" attacks—that is, attacks in which "the adversary attempts to recognize the encrypted traffic patterns of specific web pages without using any other information." In particular, he examines recent publications claiming to be able to recognize specific pages in encrypted Tor traffic, and finds the claimed results less than convincing. The issues vary from study to study, but small sample sizes and false-positives are among several recurring factors. Perry concludes: "It is likely that in practice, relatively simple defenses will still substantially increase the false positive rate of this attack when it is performed against large numbers of web pages (and non-web background traffic), against large volumes of Tor-like traffic, against large numbers of users, or any combination thereof." He does, however, suggest steps to improve subsequent studies, in addition to suggesting countermeasures for Tor users.

Comments (none posted)

OpenSSH 6.4 released

OpenSSH 6.4 is out; this is a security-related release. The vulnerability is only exploitable by an authenticated user, and only to perform actions with the privileges of that user, so it will not be of concern to most installations. Sites using configurations that restrict users to specific commands, though, may wish to install the update.

Full Story (comments: 16)

freeradius: denial of service

Package(s):	freeradius	CVE #(s):	CVE-2010-3696 CVE-2010-3697
Created:	November 13, 2013	Updated:	November 13, 2013
Description:	From the CVE entries: The fr_dhcp_decode function in lib/dhcp.c in FreeRADIUS 2.1.9, in certain non-default builds, does not properly handle the DHCP Relay Agent Information option, which allows remote attackers to cause a denial of service (infinite loop and daemon outage) via a packet that has more than one sub-option. NOTE: some of these details are obtained from third party information. (CVE-2010-3696) The wait_for_child_to_die function in main/event.c in FreeRADIUS 2.1.x before 2.1.10, in certain circumstances involving long-term database outages, does not properly handle long queue times for requests, which allows remote attackers to cause a denial of service (daemon crash) by sending many requests. (CVE-2010-3697)
Alerts:	Gentoo 201311-09 freeradius 2013-11-13

Comments (none posted)

java-1.5.0-ibm: multiple vulnerabilities

Package(s):	java-1.5.0-ibm	CVE #(s):	CVE-2013-4041 CVE-2013-5372 CVE-2013-5375
Created:	November 8, 2013	Updated:	November 22, 2013
Description:	From the Red Hat advisory: CVE-2013-4041 IBM JDK: unspecified sandbox bypass (JVM) CVE-2013-5372 IBM JDK: XML4J xml entity expansion excessive memory use (XML) CVE-2013-5375 IBM JDK: The XML4J parser in IBM WebSphere Message Broker 6.1 before 6.1.0.12, 7.0 before 7.0.0.7, and 8.0 before 8.0.0.4 and IBM Integration Bus 9.0 before 9.0.0.1 allows remote attackers to cause a denial of service (memory consumption) via a crafted XML document that triggers expansion for many entities.
Alerts:	SUSE SUSE-SU-2013:1677-1 IBM Java 5 2013-11-15 Red Hat RHSA-2013:1507-01 java-1.7.0-ibm 2013-11-07 Red Hat RHSA-2013:1508-01 java-1.6.0-ibm 2013-11-07 Red Hat RHSA-2013:1509-01 java-1.5.0-ibm 2013-11-07 SUSE SUSE-SU-2013:1677-3 IBM Java 7 2013-11-22 SUSE SUSE-SU-2013:1677-2 Java 6 2013-11-19 SUSE SUSE-SU-2013:1669-1 IBM Java 5 2013-11-14

Comments (none posted)

java-1_6_0-ibm: unspecified vulnerability

Package(s):	java-1.6.0-ibm	CVE #(s):	CVE-2013-5457
Created:	November 8, 2013	Updated:	November 13, 2013
Description:	From the Red Hat advisory: CVE-2013-5457 IBM JDK: unspecified sandbox bypass (ORB)
Alerts:	SUSE SUSE-SU-2013:1677-1 IBM Java 5 2013-11-15 Red Hat RHSA-2013:1507-01 java-1.7.0-ibm 2013-11-07 Red Hat RHSA-2013:1508-01 java-1.6.0-ibm 2013-11-07 SUSE SUSE-SU-2013:1677-3 IBM Java 7 2013-11-22 SUSE SUSE-SU-2013:1677-2 Java 6 2013-11-19

Comments (none posted)

java-1_7_0-ibm: multiple unspecified vulnerabilities

Package(s):	java-1.7.0-ibm	CVE #(s):	CVE-2013-5456 CVE-2013-5458
Created:	November 8, 2013	Updated:	November 22, 2013
Description:	From the Red Hat advisory: CVE-2013-5456 IBM JDK: unspecified sandbox bypass (ORB) CVE-2013-5458 IBM JDK: unspecified sandbox bypass (XML)
Alerts:	SUSE SUSE-SU-2016:1388-1 IBM Java 1.6.0 2016-05-24 SUSE SUSE-SU-2016:1378-1 java-1_7_0-ibm 2016-05-21 SUSE SUSE-SU-2016:1379-1 java-1_6_0-ibm 2016-05-21 SUSE SUSE-SU-2016:1303-1 java-1_6_0-ibm 2016-05-13 SUSE SUSE-SU-2016:1300-1 java-1_7_1-ibm 2016-05-13 SUSE SUSE-SU-2016:1299-1 java-1_7_1-ibm 2016-05-13 Red Hat RHSA-2016:1039-01 java-1.8.0-ibm 2016-05-11 Red Hat RHSA-2016:0716-01 java-1.8.0-ibm 2016-05-03 Red Hat RHSA-2016:0701-01 java-1.7.1-ibm 2016-04-29 Red Hat RHSA-2016:0702-01 java-1.7.0-ibm 2016-04-29 Red Hat RHSA-2016:0708-01 java-1.6.0-ibm 2016-05-02 SUSE SUSE-SU-2013:1677-1 IBM Java 5 2013-11-15 SUSE SUSE-SU-2013:1677-3 IBM Java 7 2013-11-22 Red Hat RHSA-2013:1507-01 java-1.7.0-ibm 2013-11-07 SUSE SUSE-SU-2013:1677-2 Java 6 2013-11-19

Comments (none posted)

java-1_7_0-openjdk: multiple vulnerabilities

Package(s):	java-1_7_0-openjdk	CVE #(s):	CVE-2013-5805 CVE-2013-5806
Created:	November 13, 2013	Updated:	November 13, 2013
Description:	From the CVE entries: Unspecified vulnerability in Oracle Java SE 7u40 and earlier and Java SE Embedded 7u40 and earlier allows remote attackers to affect confidentiality, integrity, and availability via unknown vectors related to Swing. (CVE-2013-5805) Unspecified vulnerability in Oracle Java SE 7u40 and earlier and Java SE Embedded 7u40 and earlier allows remote attackers to affect confidentiality, integrity, and availability via unknown vectors related to Swing. (CVE-2013-5806)
Alerts:	Gentoo 201406-32 icedtea-bin 2014-06-29 Gentoo 201401-30 oracle-jdk-bin 2014-01-26 Ubuntu USN-2089-1 openjdk-7 2014-01-23 SUSE SUSE-SU-2013:1666-1 OpenJDK 7 2013-11-13 openSUSE openSUSE-SU-2013:1663-1 java-1_7_0-openjdk 2013-11-13

Comments (none posted)

kernel: denial of service

Package(s):	kernel	CVE #(s):	CVE-2013-4483
Created:	November 11, 2013	Updated:	November 13, 2013
Description:	From the CVE entry: The ipc_rcu_putref function in ipc/util.c in the Linux kernel before 3.10 does not properly manage a reference count, which allows local users to cause a denial of service (memory consumption or system crash) via a crafted application.
Alerts:	Red Hat RHSA-2015:0284-01 kernel 2015-03-03 Scientific Linux SLSA-2014:1392-1 kernel 2014-11-03 Oracle ELSA-2014-1392 kernel 2014-10-21 Red Hat RHSA-2014:1392-01 kernel 2014-10-14 Ubuntu USN-2238-1 linux-lts-raring 2014-06-05 Ubuntu USN-2233-1 kernel 2014-06-05 Ubuntu USN-2234-1 EC2 kernel 2014-06-05 Ubuntu USN-2227-1 linux-ti-omap4 2014-05-27 Ubuntu USN-2223-1 linux-lts-quantal 2014-05-27 Ubuntu USN-2221-1 kernel 2014-05-26 SUSE SUSE-SU-2014:0536-1 Linux kernel 2014-04-16 Scientific Linux SLSA-2014:0285-1 kernel 2014-03-13 Oracle ELSA-2014-0285 kernel 2014-03-13 Oracle ELSA-2014-0285 kernel 2014-03-13 CentOS CESA-2014:0285 kernel 2014-03-13 Red Hat RHSA-2014:0285-01 kernel 2014-03-12 openSUSE openSUSE-SU-2014:0247-1 kernel 2014-02-18 Mageia MGASA-2013-0342 kernel 2013-11-22 Mageia MGASA-2013-0346 kernel-vserver 2013-11-22 Mageia MGASA-2013-0344 kernel-tmb 2013-11-22 Mageia MGASA-2013-0345 kernel-rt 2013-11-22 Mandriva MDVSA-2013:265 kernel 2013-11-10 Mageia MGASA-2013-0343 kernel-linus 2013-11-22

Comments (none posted)

libav: multiple vulnerabilities

Package(s):	libav	CVE #(s):	CVE-2013-0844 CVE-2013-0850 CVE-2013-0853 CVE-2013-0854 CVE-2013-0857 CVE-2013-0858 CVE-2013-0866
Created:	November 11, 2013	Updated:	November 13, 2013
Description:	From the Debian advisory: Several security issues have been corrected in multiple demuxers and decoders of the libav multimedia library. The CVE IDs mentioned above are just a small portion of the security issues fixed in this update. A full list of the changes is available at http://git.libav.org/?p=libav.git;a=blob;f=Changelog;hb=r...
Alerts:	Gentoo 201603-06 ffmpeg 2016-03-12 Debian DSA-2793-1 libav 2013-11-09

Comments (none posted)

libvirt: privilege escalation

Package(s):	libvirt	CVE #(s):	CVE-2013-4401
Created:	November 11, 2013	Updated:	November 13, 2013
Description:	From the CVE entry: The virConnectDomainXMLToNative API function in libvirt 1.1.0 checks for the connect:read permission instead of the connect:write permission, which allows attackers to gain domain:write privileges and execute Qemu binaries via crafted XML. NOTE: some of these details are obtained from third party information.
Alerts:	Gentoo 201412-04 libvirt 2014-12-09 Ubuntu USN-2026-1 libvirt 2013-11-11

Comments (none posted)

libxml-security-java: xml signature spoofing

Package(s):	libxml-security-java	CVE #(s):	CVE-2013-2172
Created:	November 13, 2013	Updated:	November 6, 2014
Description:	From the CVE entry: jcp/xml/dsig/internal/dom/DOMCanonicalizationMethod.java in Apache Santuario XML Security for Java 1.4.x before 1.4.8 and 1.5.x before 1.5.5 allows context-dependent attackers to spoof an XML Signature by using the CanonicalizationMethod parameter to specify an arbitrary weak "canonicalization algorithm to apply to the SignedInfo part of the Signature."
Alerts:	Debian DSA-3065-1 libxml-security-java 2014-11-06 Mageia MGASA-2014-0002 xml-security 2014-01-06 Ubuntu USN-2028-1 libxml-security-java 2013-11-12

Comments (none posted)

lighttpd: multiple vulnerabilities

Package(s):	lighttpd	CVE #(s):	CVE-2013-4508 CVE-2013-4559 CVE-2013-4560
Created:	November 13, 2013	Updated:	February 24, 2014
Description:	From the Debian advisory: CVE-2013-4508: It was discovered that lighttpd uses weak ssl ciphers when SNI (Server Name Indication) is enabled. This issue was solved by ensuring that stronger ssl ciphers are used when SNI is selected. CVE-2013-4559: The clang static analyzer was used to discover privilege escalation issues due to missing checks around lighttpd's setuid, setgid, and setgroups calls. Those are now appropriately checked. CVE-2013-4560: The clang static analyzer was used to discover a use-after-free issue when the FAM stat cache engine is enabled, which is now fixed.
Alerts:	Gentoo 201406-10 lighttpd 2014-06-14 Fedora FEDORA-2014-2506 lighttpd 2014-02-22 Fedora FEDORA-2014-2495 lighttpd 2014-02-22 openSUSE openSUSE-SU-2014:0072-1 lighttpd 2014-01-15 Mageia MGASA-2013-0334 lighttpd 2013-11-20 Debian DSA-2795-2 lighttpd 2013-11-16 Debian DSA-2795-1 lighttpd 2013-11-13 Mandriva MDVSA-2013:277 lighttpd 2013-11-21

Comments (none posted)

maas: two vulnerabilities

Package(s):	maas	CVE #(s):	CVE-2013-1057 CVE-2013-1058
Created:	November 7, 2013	Updated:	November 13, 2013
Description:	From the Ubuntu advisory: It was discovered that maas-import-pxe-files incorrectly loaded configuration information from the current working directory. A local attacker could execute code as an administrator if maas-import-pxe-files were run from an attacker-controlled directory. (CVE-2013-1057) It was discovered that maas-import-pxe-files doesn't cryptographically verify downloaded content. An attacker could modify images without detection. (CVE-2013-1058)
Alerts:	Ubuntu USN-2013-1 maas 2013-11-06

Comments (none posted)

openssh: restriction bypass

Package(s):	openssh	CVE #(s):	CVE-2013-4548
Created:	November 8, 2013	Updated:	November 19, 2013
Description:	From the CVE entry: The mm_newkeys_from_blob function in monitor_wrap.c in sshd in OpenSSH 6.2 and 6.3, when an AES-GCM cipher is used, does not properly initialize memory for a MAC context data structure, which allows remote authenticated users to bypass intended ForceCommand and login-shell restrictions via packet data that provides a crafted callback address.
Alerts:	Slackware SSA:2013-322-02 openssh 2013-11-18 Ubuntu USN-2014-1 openssh 2013-11-08 openSUSE openSUSE-SU-2013:1726-1 openssh 2013-11-18

Comments (none posted)

openstack-keystone: unintentional role granting

Package(s):	openstack-keystone	CVE #(s):	CVE-2013-4477
Created:	November 8, 2013	Updated:	January 31, 2014
Description:	From the Red Hat bug report: The IBM OpenStack test team reported a vulnerability in role change code within the Keystone LDAP backend. When a role on a tenant is removed from a user, and that user doesn't have that role on the tenant, then the user may actually be granted the role on the tenant. A user could use social engineering and leverage that vulnerability to get extra roles granted, or may accidentally be granted extra roles. Only Keystone setups using a LDAP backend are affected.
Alerts:	Red Hat RHSA-2014:0113-01 openstack-keystone 2014-01-30 Fedora FEDORA-2013-23589 openstack-keystone 2013-12-28 Ubuntu USN-2034-1 keystone 2013-11-25 Fedora FEDORA-2013-20373 openstack-keystone 2013-11-08

Comments (none posted)

poppler: multiple vulnerabilities

Package(s):	poppler	CVE #(s):	CVE-2013-4473 CVE-2013-4474
Created:	November 11, 2013	Updated:	January 22, 2014
Description:	From the Red Hat bugzilla [1, 2]: Poppler is found to be affected by a stack based buffer overflow vulnerability in the pdfseparate utility. Successfully exploiting this issue could allow remote attackers to execute arbitrary code in the context of the affected application. Failed exploits may result in denial-of-service conditions. The issue is said to be fixed in poppler 0.24.2. (CVE-2013-4473) Poppler was found to have a user controlled format string vulnerability because it fails to sanitize user-supplied input. An attacker may exploit this issue to execute arbitrary code in the context of the vulnerable application. Failed exploit attempts will likely result in a denial-of-service condition. The issue is said to be fixed in Poppler 0.24.3. (CVE-2013-4474)
Alerts:	Ubuntu USN-2958-1 poppler 2016-05-02 Gentoo 201401-21 poppler 2014-01-21 Mandriva MDVSA-2013:272 poppler 2013-11-21 Fedora FEDORA-2013-20410 poppler 2013-11-16 Fedora FEDORA-2013-20443 poppler 2013-11-11 Mageia MGASA-2013-0332 poppler 2013-11-20

Comments (none posted)

quassel: denial of service

Package(s):	quassel	CVE #(s):	CVE-2010-3443
Created:	November 7, 2013	Updated:	November 13, 2013
Description:	From the Gentoo advisory: Quassel does not properly handle multiple CTCP requests (CVE-2010-3443). A remote attacker could send multiple CTCP requests in single private message, possibly resulting in a Denial of Service condition.
Alerts:	Gentoo 201311-03 quassel 2013-11-06

Comments (none posted)

rubygem-ruby-openid: denial of service

Package(s):	rubygem-ruby-openid	CVE #(s):	CVE-2013-1812
Created:	November 8, 2013	Updated:	May 19, 2014
Description:	From the Red Hat bug report: A denial of service flaw was found in the way ruby-openid, a library for verifying and serving OpenID identities, performed processing of certain XML files. An OpenID provider could provide a specially-crafted XML file that, when processed would lead to excessive CPU consumption (denial of service).
Alerts:	Gentoo 201405-14 ruby-openid 2014-05-17 Fedora FEDORA-2013-20260 rubygem-ruby-openid 2013-11-08

Comments (none posted)

spacewalk-java: unauthorized admin users

Package(s):	spacewalk-java	CVE #(s):	CVE-2013-4480
Created:	November 13, 2013	Updated:	November 13, 2013
Description:	From the SUSE advisory: This update fixes an admin user dialog problem in spacewalk. The "add new admin user" functionality didn't get disabled after it was used. So after install/adding the first admin user anyone could have added additional admin users.
Alerts:	SUSE SUSE-SU-2013:1661-1 spacewalk-java 2013-11-12

Comments (none posted)

spip: multiple vulnerabilities

Package(s):	spip	CVE #(s):
Created:	November 11, 2013	Updated:	November 13, 2013
Description:	From the Debian advisory: Several vulnerabilities have been found in SPIP, a website engine for publishing, resulting in cross-site request forgery on logout, cross-site scripting on author page, and PHP injection.
Alerts:	Debian DSA-2794-1 spip 2013-11-10

Comments (none posted)

wireshark: denial of service

Package(s):	wireshark	CVE #(s):	CVE-2013-6339
Created:	November 8, 2013	Updated:	November 13, 2013
Description:	From the Red Hat bug report: The dissect_openwire_type function in epan/dissectors/packet-openwire.c in the OpenWire dissector in Wireshark 1.8.x before 1.8.11 and 1.10.x before 1.10.3 allows remote attackers to cause a denial of service (loop) via a crafted packet.
Alerts:	Debian-LTS DLA-497-1 wireshark 2016-05-31 Scientific Linux SLSA-2014:0342-1 wireshark 2014-03-31 Oracle ELSA-2014-0342 wireshark 2014-03-31 CentOS CESA-2014:0342 wireshark 2014-03-31 Red Hat RHSA-2014:0342-01 wireshark 2014-03-31 Gentoo 201312-13 wireshark 2013-12-16 Mageia MGASA-2013-0347 wireshark 2013-11-22 openSUSE openSUSE-SU-2013:1675-1 wireshark 2013-11-14 Fedora FEDORA-2013-20985 wireshark 2013-11-11 Fedora FEDORA-2013-20829 wireshark 2013-11-08 Mandriva MDVSA-2013:279 wireshark 2013-11-22 openSUSE openSUSE-SU-2013:1671-1 wireshark 2013-11-14

Comments (none posted)

xen: denial of service

Package(s):	xen	CVE #(s):	CVE-2013-4494
Created:	November 11, 2013	Updated:	February 3, 2014
Description:	From the Xen security advisory: The locks page_alloc_lock and grant_table.lock are not always taken in the same order. This opens the possibility of deadlock. A malicious guest administrator can deny service to the entire host.
Alerts:	Debian DSA-3006-1 xen 2014-08-18 Gentoo 201407-03 xen 2014-07-16 openSUSE openSUSE-SU-2014:0483-1 xen 2014-04-04 SUSE SUSE-SU-2014:0470-1 Xen 2014-04-01 SUSE SUSE-SU-2014:0446-1 Xen 2014-03-25 SUSE SUSE-SU-2014:0411-1 Xen 2014-03-20 Scientific Linux SLSA-2014:0108-1 kernel 2014-01-29 Oracle ELSA-2014-0108 kernel 2014-01-30 Red Hat RHSA-2014:0108-01 kernel 2014-01-29 openSUSE openSUSE-SU-2013:1876-1 xen 2013-12-16 CentOS CESA-2013:X013 xen 2013-11-25 Fedora FEDORA-2013-20544 xen 2013-11-11 Fedora FEDORA-2013-20555 xen 2013-11-11 CentOS CESA-2014:0108 kernel 2014-01-30

Comments (none posted)

xen: denial of service

Package(s):	xen	CVE #(s):	CVE-2013-4416
Created:	November 7, 2013	Updated:	November 13, 2013
Description:	From the Novell bug report: The Ocaml xenstored implementation (oxenstored) in Xen 4.1.x, 4.2.x, and 4.3.x allows local guest domains to cause a denial of service (domain shutdown) via a large message reply.
Alerts:	Gentoo 201407-03 xen 2014-07-16 openSUSE openSUSE-SU-2013:1953-1 xen 2013-12-25 openSUSE openSUSE-SU-2013:1876-1 xen 2013-12-16 CentOS CESA-2013:X013 xen 2013-11-25 Fedora FEDORA-2013-20544 xen 2013-11-11 Fedora FEDORA-2013-20555 xen 2013-11-11 openSUSE openSUSE-SU-2013:1636-1 xen 2013-11-07

Comments (none posted)

Kernel release status

The 3.13 merge window is open, with nearly 6500 changesets merged as of this writing. See the separate article below for a summary of what has been merged so far.

Stable updates: 3.11.8, 3.10.19, and 3.4.69 were released on November 13.

Comments (none posted)

3.13 Merge window, part 1

As was predicted, the 3.13 merge window has gotten off to a relatively slow start due to Linus having more pressing things to do — mostly things involving travel to tropical islands and jumping into the water with an air tank strapped to his back. Even so, as of this writing, almost 6500 non-merge changesets have been pulled into the mainline for the 3.13 development cycle.

Some of the more noteworthy user-visible changes pulled so far include:

• At long last, the nftables packet filtering subsystem has been merged. Nftables replaces the current firewalling code with an in-kernel virtual machine that adds flexibility and enables the (eventual) removal of a lot of duplicated code. It will exist alongside iptables for some time until it's clear that the old code can be removed without breaking existing firewall setups.

• The "secure element" near-field communications API is now supported; among other things, it can be used to support payments over NFC.

• The new SO_MAX_PACING_RATE socket option can be used to cap the maximum pacing rate (as described in this article on TSO sizing) used for a connection; it only works with the FQ packet scheduler.

• The networking layer has gained support for IPv6 virtual tunnel interfaces.

• The network traffic control subsystem has a new packet classifier based on the Berkeley Packet Filter (BPF) virtual machine. This allows classification programs to be loaded into the kernel as bytecode which can then be compiled with the kernel's BPF JIT compiler. The only documentation for this feature appears to be in the patch changelog.

• The High-availability seamless redundancy (HSR) protocol is now supported in the network stack. HSR provides low-latency failover in Ethernet networks.

• The use of TCP fast open is now enabled by default.

• The ipset firewalling subsystem now supports network namespaces. There is also a new "hash:net,port,net" module that allows two subnets and a protocol or port number to be stored together in a set.

• The "ktap" dynamic tracing facility was briefly merged through the staging tree, but subsequently reverted; see this article for the underlying story.

• The 64-bit ARM architecture has gained support for big-endian systems, CPU hotplug, and a 42-bit virtual address space when the 64K page size is in use.

• Support for the unmaintained ARM "shark" and Renesas H8/300 subarchitectures has been removed.

• The PowerPC architecture now supports little-endian systems.

• The "perf" tool has seen a lot of enhancements; see Ingo Molnar's pull request for a detailed list.

• An extensive set of NUMA scheduling patches has been merged, hopefully fixing a number of the kernel's longstanding performance-related problems in this area.

• The maximum number of CPUs supported by the x86 architecture has been raised to 8192. There are evidently systems out there now that exceed the old value (4096).

• New hardware support includes:
  • Systems and processors: Renesas r7272100 and r8a7791 systems and NVIDIA Tegra T124 systems. It's worth noting that the number of new systems with explicit board support is dropping, while the number of systems supported through device trees is growing quickly.

  • Audio: Audio interfaces based on the TC Applied Technologies DICE chip.

  • Miscellaneous: Allwinner sunxi security ID fuses (read-only), Intel "many integrated core" (MIC) coprocessor devices, Microchip Technology MCP3422/3/4 analog-to-digital converters, TAOS TSL4531 ambient light sensors, TAOS TCS3472 color light-to-digital converters, Sharp GP2AP020A00F Proximity/ALS sensors, Micron SPI NAND flash controllers, Capella CM36651 proximity and RGB sensors, Freescale MAG3110 3-Axis magnetometers, Samsung S3C24XX DMA controllers, AMS AS3722 PMIC voltage regulators and pin controllers, ST Microelectronics STW481X VMMC regulators, ADI BF54x and BF60x pin controllers, Abilis Systems TB10x pin controllers, Freescale IMX27 and IMX50 pin controllers, and Broadcom Kona GPIO controllers.

  • Networking: Qualcomm Atheros WCN3660/3680 wireless interfaces, Sony Port-100 Series USB NFC interfaces, and MOXA ART MDIO interfaces.

  • Physical layer (PHY): Samsung S5P/EXYNOS SoC series MIPI CSI-2/DSI PHYs, Samsung EXYNOS SoC series Display Port PHYs, and Renesas R-Car Gen2 USB PHYs.

  • Real-time clocks: AMS AS3722 RTCs and Samsung S5M RTCs.

Changes visible to kernel developers include:

• There is a new "generic PHY framework" to assist with the writing of drivers for physical connection devices; network, SATA, and USB drivers should be able to make use of this framework. See Documentation/phy.txt for more information.

• There is a new kobj_completion object which pairs a kobject with a completion, making lifecycle-matching easier. See <linux/kobj_completion.h> for the interface.

• Directory removal in sysfs is now recursive: removing a directory will cause the removal of all subdirectories as well.

• The new utility function rcu_is_watching() returns true if it is safe for the current processor to enter an RCU read-side critical section.

• There is a new earlyprintk=efi command-line option that causes early printk() output to go to the EFI framebuffer. It is meant to help with the debugging of early boot problems.

• The GPIO descriptor API has been merged, foreshadowing the eventual removal of the number-based API.

In theory, the 3.13 merge window could stay open for a week longer than usual, meaning that it could close as late as November 24. Given the amount of code merged and poised to be merged, though, it would not be surprising if Linus were to decide to close things earlier than that. So subsystem maintainers should not count on the merge window remaining open that long.

Comments (none posted)

A new maintainer for XFS?

A recent proposed change to the MAINTAINERS file entry for the XFS filesystem, which added a new maintainer, caused a reaction that was probably rather different than expected. Current XFS maintainer Ben Myers wanted to change the co-maintainer of the code, but did so by proposing it without consulting others in the XFS community. That didn't sit well with a number of community members, some of whom believe that there are more qualified candidates for an XFS co-maintainer.

Ric Wheeler questioned the change, asking: "Shouldn't we have some discussion on the list and see some substantial history of contributions?". He went on to show that the proposed new co-maintainer, Mark Tinguely, was nowhere near the top of the contributor's list for XFS. Two names clearly stand out for contributions to XFS since 3.0: Dave Chinner and Christoph Hellwig. Wheeler suggested that "if we are going to add a co-maintainer for XFS, we really need to have one of our two leading developers in that role".

For his part, Myers thought he was simply replacing a co-maintainer that no longer had time (Alex Elder) with one who could fill in for Myers when he takes vacation or is otherwise unavailable. He was, effectively, swapping his backup—or so he intended. But Hellwig strongly pushed for Chinner as a maintainer, with Myers as a co-maintainer. He noted Trond Myklebust's definition of a maintainer and suggested that Chinner best fit that role:

SGI invented XFS (in 1993) and has a great deal of interest in maintaining it for its customers and the Linux world at large. But much of the XFS work over the last few years has come from outside SGI. Automatically assigning the maintainership to whoever SGI chooses is causing some friction in the community.

Much of the discussion went on while Chinner was away for the weekend. When he returned, he pointed to a post of his from August that he said summarized his views on the maintainership issue. The problem comes down to the role having been effectively assigned to a company, rather than an individual:

Hellwig also alluded to the problem of having an "SGI maintainer": "there's also been historically a way too high turnover, with the associated transition pains". Others in both threads followed suit. It is, it seems, a fairly longstanding problem in the XFS community, but it looks like that will be changing.

Chinner noted that he has resisted becoming the XFS maintainer for some time, but after reading the thread and having "a think about it", he is willing to take on the role. He laid out some ideas of what he thought co-maintainership looks like—that it is not just a backup role, nor one that he would take "in name only"—in short, he and Myers would share the maintainer duties. Chinner suggested that he and Myers have an offline discussion before making it official. Myers seemed amenable to all of that, so it would not be a surprise to find Chinner as one of the two XFS maintainers going forward—in fact, it would be a surprise if he were not.

Maintainers are typically pulled from the community based on their knowledge of the subsystem, as well as their willingness to take on a difficult set of roles. The situation with SGI and XFS is atypical for a kernel subsystem. By adding Chinner, XFS just comes into line with kernel norms.

Comments (7 posted)

Device trees I: Are we having fun yet?

Given that Linus Torvalds's biography is titled Just for Fun it seems appropriate that people working on Linux might expect to have some fun too. Yet when one hears the device tree concept (herein referred to as "devicetree") discussed at conferences or reads about it on mailing lists, there seems to be more agonizing and (generally constructive) arguments than enjoyment. The blessing, or the curse, of devicetree forming a stable ABI, how backward compatibility is a bane to one and a boon to another, what exactly it means to describe the hardware but not the behavior, and the joy that would flow if only we could have discoverable buses, are all topics which are thrown around with much fervor but not so much joyfulness (for indeed there are many buses which are not and never will be discoverable).

By contrast, my own experience with devicetree has produced a lot of fun (though it must be admitted that some was akin to the pleasure received when one stops a repeated cranial impact with a brick wall). This is the first in a two-part series on my experience with the devicetree mechanism.

The GTA04, the replacement motherboard for the Openmoko mobile phone, has struggled along until recently with no help from devicetree. As devicetree is apparently the way of the future and a necessary precondition for full upstream support, that had to change. The opportunity arose recently to pursue two ends in parallel: implementing sufficient devicetree support to boot and use the GTA04, and learning what this devicetree thing was really all about. Both have been achieved to a level of approximately 80% (suggesting that 20% of the required time has been spent so far). This experience was a lot of fun and, in order to savor that joy a little longer, the highlights are collected below to form a practical introduction to devicetree. Most of the examples are taken from the GTA04, partly because that is all I really know, but also because it has a variety of components sufficient to highlight several interesting devicetree issues.

It's all about the platform

While devicetree started life serving SPARC and PowerPC architectures, its use with ARM is the current focus of development. It is reasonable to ask: amid all this name dropping, where is x86? What do the Intel architectures use if they don't use devicetree?

The early IBM-PC triggered a boom in personal computer sales in part because it was so easy for other manufacturers to make copies or "clones". The specification was open and it went much further than just the choice of a particular CPU instruction set. It included known devices (like a keyboard) with a known controller at an known address in the I/O address space. It also included a "BIOS" (basic IO system) in ROM with well-defined entry points to achieve simple tasks like reading a block from the floppy disk, or writing a character onto the monitor. As long as cloners copied these standard interfaces, they could build a device that standard software could run on without needing to know it was running on something new.

As time progressed this "PC platform" evolved — largely driven by Intel creating hardware standards and Microsoft enforcing them through market dominance with its software. The BIOS was repeatedly extended, giving us a VBIOS (for video-drivers), an SMM BIOS (for system management) and ACPI, which does lots of different things.

While the PC platform has changed substantially over the years, there has always been the one platform with strong market forces to ensure compatibility. Operating systems can safely be written to assume the presence of whatever the platform requires, and to be able to probe for optional components with a confidence that, for example, probing for a mouse will not accidentally switch off the main power supply.

ARM has taken a very different approach to creating a platform, in that it hasn't bothered. ARM specifies the instruction set and CPU behavior (memory model, etc.) and provides VLSI designs (aka "IP blocks") which can be integrated into hardware, typically as parts of a system on a chip (SoC). Details beyond the CPU are largely left up to the individual manufacturer. There are no standard components, and no required BIOS.

ARM has another challenge which did not affect the early PC platform: power management is crucially important on many ARM-based devices, whereas it was largely uninteresting in the PC space. Part of the standard for the PC platform is a variety of "discoverable" buses which provide the bus-master with a mechanism for asking devices on the bus to identify and describe themselves. This leads to a very general solution for handling control and data flow. It is less clear that it leads to optimal solutions for power management. We will see an example of this below.

This lack of imposed standards in the ARM world provides for a great deal of flexibility (and product differentiation) for the hardware engineers but presents a real challenge for operating system engineers: you don't know what to expect or where it might be found, and just poking around is impractical and unlikely to be successful.

This is where devicetree comes in. A devicetree essentially describes a specific device. There is no BIOS component to the platform (which is likely a good thing given what kernel engineers seem to think of BIOS quality) but rather a list of devices or device-details that cannot be discovered by poking. This devicetree (encoded as a binary "dtb" file) can be stored in ROM on the system, or can be loaded from wherever the kernel is loaded. The theory is that when a system (e.g. motherboard) is created, a "dtb" can be created for it, and it will work with all future software releases. It is a nice theory...

Getting bored of board files?

Support for ARM hardware has been in the kernel a lot longer than devicetree has been used for it. The "old" approach (still widely used where devicetree support isn't complete) is the so-called "board" file. This is essentially a description of the platform written in C.

Each board file ends with a MACHINE description something like:

    MACHINE_START(GTA04, "GTA04")
        /* Maintainer: Nikolaus Schaller - http://www.gta04.org */
        .atag_offset    =   0x100,
        .reserve    	=   omap_reserve,
        .map_io    	=   omap3_map_io,
        .init_irq   	=   omap3_init_irq,
        .handle_irq 	=   omap3_intc_handle_irq,
        .init_early 	=   omap3_init_early,
        .init_machine   =   gta04_init,
        .init_late  	=   omap3630_init_late,
        .timer      	=   &omap3_secure_timer,
        .restart    	=   omap_prcm_restart,
    MACHINE_END

which, as you can see, is completely generic for "omap3" devices except for "init_machine".

gta04_init() contains a fairly ad-hoc collection of initializations, probably the most interesting being calls to platform_add_devices() and omap_register_i2c_bus(). These provide lists of device identifiers together with "platform_data" data structures which describe many of the various components on the GTA04 board and how they are connected together. (See this article for information on the platform device API).

So a board file identifies the SoC which the board is built around, identifies all the other components, and has various bits of glue code to make things work (like initializing GPIO lines).

A devicetree source file (dts) contains the first two elements (SoC identification and component configuration) but doesn't have the ad-hoc glue code. This is the first source of joy — much less clutter in the platform description as you cannot include code. This means, of course, that the generic code must be improved so that individual platforms don't need their own code and this is the second source of joy: more complete and coherent design in the generic code.

To see the difference, my git tree contains a board file for the GTA04 and a devicetree file that does nearly as much.

Let's start with a leaf

The following fragment is taken from somewhere several levels deep into the devicetree for the GTA04. It doesn't actually appear in omap3-gta04.dts file linked above, but rather in twl4030.dtsi which the former file includes.

    charger: bci {
    	compatible = "ti,twl4030-bci";
    	interrupts = <9>, <2>;
    	bci3v1-supply = <&vusb3v1>;
    };

This fragment describes the battery charger ("bci" for "battery charger interface"). This is one component on a multi-function chip which serves as the PMIC (Power Management IC) — the twl4030 from Texas Instruments.

The "charger:" string is simply a label which allows this node to be referenced from elsewhere in the tree as we will see shortly. "bci" is the name of this node within its parent. The full name in the GTA04 is actually /ocp/i2c@48070000/twl@48/bci. The choice of names seems to have little practical effect providing they are unique among siblings. There are standards that are best followed, such as the "@NNN" suffix to give the device's address. Failing to follow these standards certainly results in non-compliance but does not seem to result in non-functionality.

The "compatible" field, rather than the node name, tells you (and Linux) what this device does. Every device can list one or more strings that it is "compatible" with. Similarly every driver in the kernel can list one or more strings that it is compatible with (via the "driver.of_match_table" field). The driver that is bound to a particular device is the one that appears to be most compatible. In many cases both the device and the driver will only have one "compatible" name, but it is reasonable to assume that over time some IP blocks will prove particularly successful, will be refined in backward-compatible ways, and so will benefit from this flexibility.

The "interrupts" field lists two interrupt numbers as the BCI can generate two different interrupts. These are interpreted in the context of the nearest interrupt controller. As the "twl@48" node, which is the parent of the BCI, declares itself to be an interrupt controller (by having the attribute "interrupt-controller" present), these interrupt numbers (9 and 2) are interrupts within the twl4030 itself (interrupt management is one of the multiple functions of the chip).

Since the BCI is an integral part of the twl4030 with these interrupt lines hardwired in, there seems little point in explicitly listing the numbers in the devicetree node. Surely they can simply be hardcoded in any "ti,twl4030-bci" compatible driver. The reason they are explicit is that, in principle at least, the BCI IP block in the twl4030 might be reused in some other packaging when TI makes some new PMIC, and in that case the interrupts might be wired differently, but the same driver should be able to be used. So it is good forward-planning to keep their definition separate.

Given this, it is somewhat surprising that the bci node (like all the other nodes in the "twl" parent) does not have a "reg" property. This property identifies the address at which the device can be found, in whatever address space the current node in the tree resides. For example the parent "twl@48" node contains:

    reg = <0x48>;

meaning that the whole twl4030 multi-function device can be found at address 0x48 in the I2C bus that it is on. The twl4030 has a number of registers (accessed over the I2C bus) which are grouped into modules. The "MAIN_CHARGE" module is at address 0x74 and has 54 bytes of register space. So:

    reg = <0x74 0x36>

in the bci node might seem appropriate (when given, the second number is the size of the register set). Unfortunately the BCI driver needs to access registers for other modules, such as PM_MASTER, PM_RECEIVER, and INTERRUPTS. This could be achieved with something like:

    reg = <0x74 0x36> <0xB9 0x0E> <0x14 0x08> <0x00 0x14>

But those values, instead, are hardcoded in the driver. It's possible that the general solution just seemed to be more trouble than it is worth. While it is nice to imagine that each individual IP block can be treated as an individual device, independent from everything else, this is often not the case.

The final point of interest in this node is the attributes that aren't there.

Part of the role of the battery charger is to charge the backup battery (which, for example, keeps the real-time clock ticking when the main battery is removed). The parameters for charging the main battery can vary due to policy and circumstance so it is important that they are configured at run time, probably though a "sysfs" interface. However the parameters for charging the backup battery (which are a target voltage and a maximum current) depend primarily on the electrical characteristics of the battery (or super-capacitor) which is installed. So they are really part of the platform description.

Being part of the GTA04 platform, they should live in the "omap3-gta04.dts" devicetree file. However the above "bci" node lives in the "twl4030.dtsi" include file. So different fields for the one node might need to live in different files. This is where the "charger:" label comes in.

In the GTA04 file (omap3-gta04.dts) we have:

    &charger {
    	ti,bb-uvolt = <3200000>;
    	ti,bb-uamp = <150>;
    };

The "&charger" expands to the full name of the node with the label "charger", and this simply adds some attributes to that node. It can equally well replace attributes, so common defaults can be placed in an include file, and divergent values can be given in the main file. This ability to present the nodes in the tree in other than the obvious depth-first order is very valuable and quite widely used. I needed to follow several such indirections to piece together the full path of "/ocp/i2c@48070000/twl@48/bci".

It could be argued that specifying the charging parameters for the backup battery is specifying behavior (of the charger) rather than describing hardware. This is seen by some as contrary to the purpose of devicetree. This could be addressed by a simple sleight-of-hand. We simply create a new devicetree node that represents the battery.

    &backup-battery {
    	ti,target-uvolts = <3200000>;
    	ti,max-uamps = <150>;
    };

These are now physical properties of the battery: the voltage it produces when fully charged and the maximum charge current that it can comfortably accept. The driver could then inspect the properties of the battery (if one is present) and configure the charger accordingly.

This does raise a question of where in the devicetree the "backup battery" should be attached. It is conceptually connected to both the battery charger and the real time clock. As "devicetree" is in the form of a tree, the battery can only have one parent - which device node should that be? Hierarchical trees can be extremely powerful, but they don't always map cleanly to the real world.

From nodes to a tree

As we have already hinted at, devicetree nodes can contain child nodes as well as attributes. For example the "twl@48" node contains the "bci" node, as well as a real time clock, some power regulators, some GPIO pins, a watchdog timer, and more. The case where this is most obviously necessary is when the platform contains some devices on a bus that doesn't support discovery such as the I2C bus.

The OMAP3 contains three I2C buses. The GTA04 places just the twl4030 on one, leaves one unused, and includes quite a collection of sensors as well as the touchscreen and LED controllers on the third. There is no way that Linux could know anything about these unless they were described in a board file (passed to omap_register_i2c_bus), or in a devicetree.

Less obvious is the need for child nodes of the "twl@48" node. Certainly the driver for the twl4030 would know what component devices it contains. So the issue of having discoverable buses doesn't really apply here. There are at least two reasons that the member devices of the twl4030 need to be explicitly listed. One is that it allows platform-specific configuration to be added, as with the "ti,bb-uvolt" and "ti,bb-uamp" attributes for the battery charger (though if they were in a separate "battery" node, that would be less important).

The other is that other devices might need to make reference to the individual components. As mentioned the twl4030 contains some regulators and some GPIO pins. While the GTA04 doesn't use any of the GPIOs it does use the regulators. For example the WiFi chip is powered by "VAUX4" from the twl4030. The "MMC" driver which communicates with the WiFi chip needs to know about this so it can power up the WiFi interface to talk to it, then power it down while it isn't in use. This interconnection is specific to this particular platform and so needs to be explicit in the devicetree file. For that to be possible, each of the power regulators in the twl4030 must be listed as a child node. Given these obvious needs for many things to be listed, it makes a certain amount of sense to list everything.

One interesting twist in the GTA04 involves the module used for communicating with the GSM telephone network — the Option GTM601. This is primarily a USB device that is permanently connected to one of the USB ports on the OMAP3. As USB is considered to be a discoverable bus, there is no mechanism in devicetree to list the devices attached to a USB bus. However the GTM601 doesn't only use USB. It also has a DAI port (Digital Audio Interface) for bi-directional audio (which is connected to one of the McBSP audio ports on the OMAP3), and a "wake-up" line which is pulsed on an incoming phone call or text message.

While these three connections all relate to the one device, there is no way to describe this hardware in devicetree as a single unit. Rather the input "wake-up" signal and the audio channel are specified as separate devices, the USB interface is left to be discovered, and the relationship between the three is left for some application to just "know" about.

Both the audio data and the wake-up signal could be sent over the USB connection which would make it much easier for the operating system to treat it as a single device. However, as this approach would result in significantly higher energy usage, it is not used. Having a separate "wake-up" signal connected to an "always-on" GPIO bank on the OMAP3 allows the whole USB path to be completely powered off when idle. Having a separate DAI allows it to be connected directly to the audio codec/amplifier (in the magic twl4030 chip) so that the CPU is not involved in audio routing and can enter deep sleep during a phone call.

The second installment in this series will focus on some of the difficulties involved with the device tree abstraction and whether it will ever truly be possible to support system-independent kernel images on non-discoverable platforms.

Comments (18 posted)

Fedora debates apps and app stores

Fedora is currently in the midst of a reorganization using working groups to flesh out three separate "products" that the distribution will deliver: Workstation, Server, and Cloud. As part of that effort, the working groups need to come up with a description of what their product will be, who its users are, and so on. Christian Schaller posted a draft of the workstation product description to the fedora-devel mailing list on November 1. While there were quibbles about various aspects of the description, the biggest disagreement seems to be between those who advocate supporting "apps" and an "app store" model and those who don't.

Schaller's draft was attached [ODT] to his message. It lists four separate use cases (student, independent developer, small company developer, and developer in a large organization) that mesh well with the mission statement: "The system will primary be aimed at providing a platform for development of server side and client applications that is attractive to a range of developers - from hobbyists and students to developers working in a corporate environments." The draft also has a list of some policies/plans for the workstation product, a description of what the core platform components would consist of, and a bit of an idea on how the group would operate (including focusing on one "major engineering effort" at a time).

Overall, the reception has been rather positive. Some quibbles, as mentioned, but the replies have been largely supportive of its direction. But the "3rd party software" policy is more contentious. It reads:

Supporting third-party software, proprietary software in particular, would be a bad idea for the workstation product, Kevin Kofler said. He cited a number of reasons for that, most of which boiled down to possibly needing to support older libraries and other components to help keep those applications running. It could hold back Fedora development, even for those who aren't interested in those third-party programs, he said.

Schaller replied, but opened another can of worms when he did so. He noted that "support" means different things to different people, but that he had mostly meant "handling our ABI story better", rather than bending over backwards to help third-party applications continue to work. But he also pointed to GNOME's LinuxApps proposal for sandboxed applications for the Linux desktop, which are in some ways similar to smartphone "apps". In the product description, there is also a sentence that points in that direction: "Work towards a system where applications can be installed inside a container to improve security and simplify compatibility through library bundling".

Apps and the app store model for general-purpose Linux distributions is a fairly controversial topic. The model is clearly quite successful in the phone and tablet spaces, so it is not surprising that some would look to replicate it more widely. It has a number of downsides, though, starting with it being an almost complete departure from the "normal" Linux model of software distribution. Kofler outlined some of the problems he sees with "Apple-like 'apps'". Those include library bundling (with its attendant security and disk usage problems), a licensing free-for-all, non-centralized application distribution, and so on.

As one might guess, Kofler's disdain for apps and app stores was not universally shared. Chris Murphy sarcastically suggested that apps are "a model for success that shouldn't be either emulated or improved upon". The theme of taking the "good parts" from the app store model and applying it to Fedora was repeated several times in what turned into a truly enormous thread. To some, however, there really aren't any good parts to be had.

There is clearly a fundamental split in how people see the Linux desktop of the future. To some, it looks like the Linux desktop of the present (and past), while others see a more developer-friendly, app-oriented desktop that, at least to some extent, resembles the mobile ecosystem. In that model, apps are developed and packaged once, but run on a variety of platforms. Those platforms might be multiple versions of Fedora, for example, or they might be multiple distributions across the Linux landscape. Certainly, the GNOME proposal envisions a wider range of target platforms than just a single distribution (or just one version of a distribution).

Today's application development model for Linux is well-suited to free software applications that benefit from integration with the distribution. It has fewer benefits for third parties who just wish to make their program (free or not) available widely on Linux. In addition, it is not at all clear that the current distribution model, where each and every program is curated and packaged by members of the distribution's community, can scale to the numbers of applications seen in the mobile world—and hoped for, at least by some, on the Linux desktop. If distributions don't come up with a solution, there is a risk that some third party will, as Adam Williamson pointed out:

Williamson goes on to recognize that some big changes are being considered—or at least discussed. The distribution model has been with us for a long time, and has had a measure of success; moving away from it should not be done lightly:

But, some combination of the existing and the new should be possible, according to some thread participants. Several argued that competition between the two models would be healthy. Having both curated and integrated applications and apps, which will be able to get into the hands of users more quickly, will allow users to choose which suits them best. Others, like Kofler, are worried that it will lead to less free software (in both the gratis and freedom senses of the word) in the long term.

Another concern was expressed by Nicolas Mailhot, who is worried that the Fedora "brand" will be harmed by including apps. Mailhot sees the app mechanism as a way to solve developer problems, rather than user problems; he would like to see a clear distinction between Fedora-packaged applications and apps so that the brand is not damaged if apps are not the panacea predicted by some.

As Kevin Fenzi noted, though, the whole thread stemmed from just those few words about containerized apps in the proposal—presented without any technical details at all. He suggested that perhaps rewording the product description proposal along the lines of "investigate the implementation and usage for application containers" and then waiting to argue until some kind of concrete proposal was made. That suggestion largely fell on deaf ears—it is an emotional subject and one we are likely to hear of again, in multiple contexts, over the coming years.

On November 7, Schaller updated the fedora-devel mailing list on the status of the proposal. To start with, the discussion will be moving to the lower-traffic fedora-desktop list, as that is the designated "home" mailing list for the working group. The members of the group have been monitoring the discussion so far, Schaller said, and will be incorporating that feedback into the next draft. We can expect another lively discussion once that makes its appearance.

Comments (36 posted)

Distribution quotes of the week

-- Mark Shuttleworth

-- Ean Schuessler (Thanks to Mattias Mattsson)

Comments (none posted)

Fedora 20 Beta released

The beta version of the Fedora 20 release is out. "The beta release is the last important milestone before the release of Fedora 20. A Beta release is code-complete and bears a very strong resemblance to the third and final release. Only critical bug fixes will be pushed as updates up to the general release of Fedora 20." This is the best opportunity to get bugs fixed before the final release happens; click below for the full announcement with a long list of new features in Fedora 20.

Full Story (comments: 34)

Scientific Linux 5.10

Scientific Linux has released Scientific Linux 5.10. There are release notes available for i386 and x86_64.

Comments (none posted)

Slackware 14.1 released

The latest version of the Slackware Linux distribution, version 14.1, has been released. It comes with the 3.10.17 kernel, GNU libc 2.17, X.Org X11R7.7, GCC 4.8.2, LLVM and Clang, and more. "Slackware 14.1 brings many updates and enhancements, among which you'll find two of the most advanced desktop environments available today: Xfce 4.10.1, a fast and lightweight but visually appealing and easy to use desktop environment, and KDE 4.10.5, a recent stable release of the 4.10.x series of the award-winning KDE desktop environment. These desktops utilize udev, udisks, and udisks2, and many of the specifications from freedesktop.org which allow the system administrator to grant use of various hardware devices according to users' group membership so that they will be able to use items such as USB flash sticks, USB cameras that appear like USB storage, portable hard drives, CD and DVD media, MP3 players, and more, all without requiring sudo, the mount or umount command." (Thanks to Jean-Francois L. Blavier.)

Comments (5 posted)

call for Jessie artwork proposals

The call for artwork proposals for Debian's next stable release (Jessie) is open until February 5, 2014.

Full Story (comments: none)

SUSE Linux Enterprise 10 End of General Support

SUSE has released the final regular maintenance update for SUSE Linux Enterprise 10 Service Pack 4. Users of SLE10 SP4 are encouraged to upgrade to SLE11 SP3.

Full Story (comments: none)

Distribution newsletters

• This Week in CyanogenMod (November 9)
• DistroWatch Weekly, Issue 533 (November 11)
• Tails report (for October)
• Ubuntu Weekly Newsletter, Issue 342 (November 10)

Comments (none posted)

Shuttleworth: Mistakes made and addressed

Mark Shuttleworth writes about the fixubuntu.com takedown notice incident. "Last week, the less-than-a-month-at-Canonical new guy sent out the toughest template letter to the folks behind a 'sucks' site. Now, that was not a decision based on policy or guidance; as I said, Canonical’s trademark policy is unusually generous relative to corporate norms in explicitly allowing for this sort of usage. It was a mistake, and there is no question that the various people in the line of responsibility know and agree that it was a mistake. It was no different, however, than a bug in a line of code, which I think most developers would agree happens to the best of us. It just happened to be, in that analogy, a zero-day remote root bug." There's also an apology for the "open source tea party" remark.

Comments (57 posted)

Friday Interview #6: Glen MacArthur (zth music)

Zth music has an interview with Glen MacArthur, creator of AVLinux. "Well at a glance AV Linux is similar to 64/Ubuntu/Tango/Dream/KX Studio and is a custom tailored Live or Installable Linux OS specializing in Audio and Video creation. I guess it is more distinguished by it’s differences to the others than by it’s similarities."

Comments (none posted)

User-space RCU

The user-space read-copy update (URCU) library was established in February of 2009, and is now used by several projects and available from several distributions. URCU is similar to its Linux-kernel counterpart, providing a replacement for reader-writer locking, among other uses. This similarity continues with readers not synchronizing directly with RCU updaters, thus making RCU read-side code paths exceedingly fast, while furthermore permitting RCU readers to make useful forward progress even when running concurrently with RCU updaters—and vice versa.

Although people who have worked with the Linux kernel's RCU implementation find much to be familiar with in URCU, there are some important differences, including support for several concurrent data structures. To that end, this article summarizes the similarities and discusses the differences as follows:

1. RCU review
2. URCU overview
3. URCU flavors
4. URCU library API
5. Using URCU
6. Summary

And then there are, of course, the inescapable answers to the quick quizzes.

Companion articles cover RCU-protected hash tables and stacks and queues.

RCU review

RCU is most frequently used to provide concurrency control for read-mostly linked data structures, so that read-side overhead is minimal. The word “minimal” is no euphemism: In some common cases, RCU's read-side overhead both in the kernel and in user space approaches zero.

Of course, if readers are to have zero overhead, then there logically cannot be any way for updaters to delay them or otherwise prevent them from running. Which in turn means that RCU updaters must handle readers traversing the data structure at all times before, during, and after the update. RCU updaters accomplish this feat by maintaining multiple versions of the data structure, waiting to free up a given old version until such time as all readers that might be referencing that version have moved on.

The following examples show how this works, first for insertion of a new data element into an RCU-protected structure, and then for deletion from an RCU-protected list. As we will see later, RCU can be applied to a great many other data structures as well.

The insertion process is shown in the following diagram, with time progressing through four states from left to right.

The first state shows a global pointer named gptr with value NULL. The first green arrow shows the updater using malloc() to arrive at the second state, in which gptr is still NULL, but where the updater's local variable tmp now references an uninitialized block of memory. The second green arrow shows the updater initializing the newly allocated block of memory, resulting in the third state, where the new structure's fields ->a, ->b, and ->c have the values 1, 2, and 3, respectively. Finally, the red arrow shows the updater assigning a pointer to the new structure to the global variable gptr using rcu_assign_pointer(). The structure is now colored red, indicating that readers might now reference it. This in turn means that any further updates to the new structure must be done carefully, taking the possibility of concurrent readers into account.

Quick Quiz 1: Why use rcu_assign_pointer() rather than the simple gptr=tmp assignment statement that the C language provided for this straightforward job???

Answer

The process of deleting an element from an RCU-protected linked list is as follows, again with time progressing through four states from left to right.

The first state shows a linked list with elements A, B, and C. The first (red) arrow shows the updater removing element B from the list using cds_list_del_rcu().

Quick Quiz 2: Why cds_list_del_rcu() instead of simply list_del_rcu() like the Linux kernel does?

Answer

In the second state, old readers might still be accessing element B, but new readers have no path to it, hence the yellow color. This means that the list has two versions: old readers will see the list containing A, B, and C, while at the same time new readers will see the list containing A and C. Eventually, all the old readers still accessing element B will move to element C, but until then, element B cannot be freed. We clearly need some way to wait until all of these old readers have finished, and synchronize_rcu() does just that, waiting for any reader that was in already in progress at the time that synchronize_rcu() started executing.

Quick Quiz 3: And just how is synchronize_rcu() supposed to know when all the currently executing RCU readers started? Doesn't that mean that all the RCU readers must do heavyweight operations to get the current time and store it somewhere? And doesn't this also require perfect time synchronization?

Answer

After synchronize_rcu() completes, the list will be as shown in the third column. Element B is green to indicate that readers can no longer have a reference to it, so that all readers see the list as containing only elements A and C. It is thus safe to free() element B, resulting in the final state shown on the right.

Of course, for synchronize_rcu() to do its job, there must be some way of determining where RCU readers begin and end. This job is handled by rcu_read_lock(), which marks the beginning of an RCU read-side critical section and rcu_read_unlock(), which marks the end. RCU read-side critical sections may be nested, and cannot contain synchronize_rcu() (otherwise deadlock would result).

Any line of code not in an RCU read-side critical section is termed a quiescent state, and any period of time during which each reader thread resides in at least one quiescent state is called a grace period.

Quick Quiz 4: Why the “reader” above? Doesn't every thread need reside in a quiescent state in order for a grace period to have elapsed?

Answer

The code to traverse an RCU-protected linked list might look as follows:

  1 rcu_read_lock();
  2 cds_list_for_each_entry_rcu(p, head, list) {
  3   do_something_with(p->a, p->b, p->c);
  4 }
  5 rcu_read_unlock();

So what? There are any number of linked-list traversal schemes, and this probably does not look all that special. The special thing about RCU-protected list traversal is that the above code often compiles to exactly the same assembly language as does a simple single-threaded linked-list traversal but nevertheless provides full protection against concurrent modification.

Quick Quiz 5: When does RCU-protected list traversal compile to different assembly language than does simple single-threaded linked-list traversal?

Answer

More detail on RCU is available:

1. User-Level Implementations of Read-Copy Update.
2. Structured Deferral: Synchronization via Procrastination.
3. What is RCU, Fundamentally?
4. What is RCU's Usage?
5. The RCU API, 2010 Edition.
6. What Is RCU? [PDF]
7. Paul E. McKenney's RCU page.

Given this general RCU overview, we are ready to look at URCU in particular.

URCU overview

URCU is a library that is available in a number of Linux distributions as liburcu2 (liburcu1 and liburcu0 for older versions), or that can be downloaded here. An additional liburcu-dev package is required if you wish to develop programs that use RCU. It runs on a number of architectures, including x86, ARM, PowerPC, Alpha, Itanium, Mainframe, and SPARC, and also on several operating systems, including Linux, FreeBSD, and Cygwin. It is also expected to run on Android, NetBSD, OpenBSD, and Darwin, but more testing is required before full support can be claimed.

Along with a number of concurrent data structures, URCU provides five different flavors of RCU for different types of applications:

1. QSBR (quiescent-state-based RCU).
2. Memory-barrier-based RCU.
3. “Bullet-proof” RCU.
4. Signal-based RCU.
5. Signal-based RCU using an out-of-tree sys_membarrier() system call.

QSBR closely resembles the “classic” RCU implementations (RCU_TREE and RCU_TINY) in the Linux kernel in having zero-overhead implementations of rcu_read_lock() and rcu_read_unlock(). However, each thread must periodically invoke rcu_quiescent_state(), just as in the kernel, where schedule() must be invoked periodically. Each thread that is to execute RCU read-side critical sections must also invoke rcu_register_thread() after thread creation and rcu_unregister_thread() before thread exit. These requirements clearly put a stringent constraint on the overall application design that, for example, prohibit the use of QSBR RCU in most library code, but in return, QSBR provides unmatched performance.

Memory-barrier-based RCU resembles the earliest preemptible RCU implementation accepted into the -rt patchset in that rcu_read_lock() and rcu_read_unlock() contain memory barriers (though not heavyweight atomic instructions!). This situation results in high read-side overhead by RCU standards but, in return, removes QSBR's requirement that all threads periodically invoke anything, thus making memory-barrier-based RCU usable from within library functions, at least in cases where the the application is registering its threads with RCU via rcu_register_thread().

Bullet-proof RCU is like memory-barrier-based RCU but, in addition, automatically invokes rcu_register_thread() when needed from the RCU read-side primitives. This further increases these primitives' overheads, but in return allows RCU to be used by libraries that are used by applications that create their own threads such that RCU cannot hook into thread creation and destruction.

Signal-based RCU removes the memory barriers from rcu_read_lock() and rcu_read_unlock(), while still allowing these primitives to be used by library functions. This reduces these primitives' overheads to near those of the QSBR RCU implementation, but requires that the user application give up a POSIX signal to be used by synchronize_rcu() in place of the read-side memory barriers. However, this approach requires that all threads, including those created by library functions, invoke rcu_register_thread() before entering their first RCU read-side critical section.

The final flavor, interrupt-based RCU using sys_membarrier(), uses an experimental sys_membarrier() system call in place of the POSIX signals used by the preceding approach. This sys_membarrier() system call uses inter-processor interrupts, which are lighter weight than POSIX signals. In addition, in constrast to RCU_SIGNAL, which sends a POSIX signal to every thread in the process that has been registered as an RCU reader, RCU_MEMBARRIER interrupts only those threads in this process that are currently running. This optimization works because any blocked threads already executed memory barriers in the process of blocking and will execute more when they wake up.

Each of these flavors of RCU are described in the next section.

URCU flavors

There are five flavors of RCU available from liburcu, each of which can be selected on a per-compilation-unit basis as described below.

The first flavor is QSBR, which is accessed as follows:

    #include <urcu-qsbr.h>

It is also necessary to include “-lurcu-qsbr” on the linker command line.

QSBR provides the highest performance, but requires that all reader threads periodically indicate quiescent states via either rcu_quiescent_state() for a momentary quiescent state or using rcu_thread_offline()/rcu_thread_online() pairs for extended quiescent states.

Signal-based RCU is slightly slower than QSBR, but does not require explicitly indicating quiescent states. Instead, the application must allow RCU to have dedicated use of SIGUSR1. Users who are building their own liburcu library can override this default by using -DSIGRCU. Signal-based RCU is accessed as follows:

    #define RCU_SIGNAL
    #include <urcu.h>

It is also necessary to include “-lurcu-signal” on the linker command line.

Memory-barrier-based RCU is somewhat slower than signal-based RCU, but does not require a signal to be dedicated to RCU's use. Instead, this flavor of RCU's read-side primitives contains explicit memory barriers. Memory-barrier-based RCU is accessed as follows:

    #define RCU_MB
    #include <urcu.h>

It is also necessary to include “-lurcu-mb” on the linker command line.

Some kernels have a sys_membarrier() system call that causes every currently running thread of the current process to execute a memory barrier. Systems with such a system call can gain the performance benefits of signal-based RCU without the need to dedicate a signal to RCU, however, until sys_membarrier() is in mainline, those using it will need to carefully ensure that the kernel and user-space RCU agree on the system-call number. This variant of RCU is accessed as follows:

    #define RCU_MEMBARRIER
    #include <urcu.h>

It is also necessary to include “-lurcu” on the linker command line.

The four previous flavors of RCU require that reader threads be initialized using rcu_register_thread() before the first use of rcu_read_lock(), and further that they be cleaned up using rcu_unregister_thread() after the last use of rcu_read_unlock(). These requirements can be problematic in some types of libraries, and can therefore be dispensed with (with an additional slight degradation in performance compared to RCU_MB) by accessing bullet-proof RCU as follows:

    #include <urcu-bp.h>

It is also necessary to include “-lurcu-bp” on the linker command line.

For all flavors, defining either of the C preprocessor symbols _LGPL_SOURCE or URCU_INLINE_SMALL_FUNCTIONS before the first #include enables static linking, which gives the compiler more freedom to carry out optimizations, inlining in particular. These optimizations can be particularly important for the lightweight read-side primitives such as rcu_read_lock() and rcu_read_unlock(). In short, static linking provides increased performance for those willing to abide by its licensing and technical constraints. These constraints include the need to distribute “.o” object files with any binary of your application, and the need to provide a separate build of your application for each version of URCU's ABI.

Quick Quiz 6: Is it OK to use URCU_INLINE_SMALL_FUNCTIONS even in proprietary code?

Answer

The tradeoffs between the five flavors are shown in the following table, where blank cells indicate fewer restrictions:

	QSBR	RCU_MEMBARRIER	RCU_SIGNAL	RCU_MB	Bullet-proof
Header	<urcu-qsbr.h>	<urcu.h>	<urcu.h>	<urcu.h>	<urcu-bp.h>
Define		RCU_MEMBARRIER	RCU_SIGNAL	RCU_MB
Libraries	-lurcu-qsbr	-lurcu	-lurcu-signal	-lurcu-mb	-lurcu-bp
Read-Side Cost	Free!	++	++, test	++, smp_mb()	++, smp_mb(), test
Explicit QS Required	Yes
Thread Registry Required	Yes	Yes	Yes	Yes
Kernel Patch		Yes
POSIX Signal Required			Yes
OK From Library	Not in general
OK From Library with unannounced application threads	Not in general	Not in general	Not in general	Not in general

The first three rows show the compiler directives and linker libraries needed to access the corresponding RCU flavor. The “Read-Side” row roughly summarizes the read-side cost of each flavor, where “++” indicates a local increment/decrement pair, “test” indicates an if test and branch, and smp_mb() indicates a pair of memory barriers. Thus, although read-side cost does vary, all flavors have extremely low overhead when compared to synchronization primitives based on mutual exclusion.

The “Explicit QS Required” row shows which flavors require explicit calls to rcu_quiescent_state, the “Thread Registry Required” shows which flavors require explicit rcu_register_thread() and rcu_unregister_thread() calls from threads using RCU's read-side primitives, the “Kernel Patch” row shows which flavors require the sys_membarrier() kernel patch, and the “POSIX Signal Required” row shows which flavors require that the application give up a POSIX signal for RCU's use.

The “OK From Library” row shows which flavors can be used with little or no restriction from library functions intended to be linked with arbitrary applications, and finally, the “OK From Library with Unannounced Application Threads” row shows which flavors can be used with little or no restriction from such library functions, but where the linking application creates threads that cannot be forced to invoke the rcu_register_thread() and rcu_unregister_thread() primitives.

In short, no one of the five RCU flavors is suitable in all situations. The following rough rules of thumb can help select the flavor that is best for you:

• If you are building a standalone application, and if speed is of the essence, then QSBR is probably your best choice.

• If you are building a library or a library function, and you have absolutely no control over thread creation and destruction, then bullet-proof RCU is your only viable choice.

• If you are building a library or a library function, but you are able to hook into thread creation and destruction, then you will need to use one of RCU_MEMBARRIER, RCU_SIGNAL, or RCU_MB as follows;
  • If you are running Linux and can patch your kernel, then build your kernel with Mathieu Desnoyers's sys_membarrier() patch and use RCU_MEMBARRIER. (You will also need to inform your application of sys_membarrier()'s syscall number, for example, by patching the relevant include files.) If you build with RCU_MEMBARRIER and run on a system lacking sys_membarrier(), URCU will fall back to RCU_MB. Assuming, that is, that the kernel does not contain another custom system call with a number that happens to collide with the choice of sys_membarrier() on the build machine.

  • Otherwise, if you can reserve a signal for your library's use (perhaps in conjunction with any other libraries or library functions wishing to use RCU), then use RCU_SIGNAL.

  • Otherwise, use RCU_MB.

Regardless of the URCU flavor chosen, the API is the same; for example, you will use rcu_read_lock() regardless of the URCU flavor. This is very convenient because it allows common source code to be shared among different programs or libraries that might select different URCU flavors. However, it also means that special care is required when sharing RCU-protected data structures among different libraries that are using different flavors of RCU. In some cases, it is necessary to include pointers to the relevant RCU functions in order to avoid RCU-flavor confusion. That said, in the typical case of a standalone application using RCU, this problem does not arise.

URCU library API

The URCU library's API is surprisingly large, and will therefore be discussed in the following pieces:

1. Atomic-operation and utility API
2. Details of atomic-operation and utility API focused on memory barriers
3. The URCU API
4. RCU-Protected Lists

Using URCU

The following sections give some advice on the use of RCU:

1. When is URCU useful?
2. Application quiescent states
3. Mixing and matching URCU flavors
4. Building URCU

When is URCU useful?

RCU is a specialized synchronization mechanism, and its performance, scalability, and real-time response advantages are due to this specialization. It is always important to use the right tool for the job, and RCU is no exception to this rule. The following diagram gives some rules of thumb for where RCU is best used:

As shown in the blue box, RCU works best if you have read-mostly data where stale and inconsistent data is permissible. The canonical example of this case in the Linux kernel is routing tables. Because it may have taken many seconds or even minutes for the routing updates to propagate across the Internet, the system has been sending packets the wrong way for quite some time. Having some small probability of continuing to send some of them the wrong way for a few more milliseconds is almost never a problem. User-level classification and routing data structures are likely to be just as amenable to RCU as those in the Linux kernel.

If you have a read-mostly workload where consistent data is required, RCU works well, as shown by the green box. Examples of this situation are data structures that map from a key to a structure, but where operations on each such structure must be fully synchronized, especially including deletion of the structure. The trick here is to use RCU to protect the mapping data structure and to use a per-structure lock to protect the individual structures being mapped to. In addition, each structure has a flag indicating that whether or not it has been deleted. When an RCU-protected search finds a data structure, it acquires that data structure's lock and checks the deletion flag. If the flag is set, the search pretends not to have found the structure, otherwise, the desired operation on the structure is carried out under the protection of the lock.

In this case, RCU provides high performance and scalability for the mapping operation, and also guarantees that the structure will remain in existence: Updaters must wait for a grace period after removing a given structure before they are permitted to free that structure.

As indicated by the yellow box, RCU can also be useful for read-write workloads where consistent data is required, although usually in conjunction with a number of other synchronization primitives, including per-data-structure locks (as above), per-thread locks, sequence locks, and atomic operations.

Finally, as indicated by the red box, update-mostly workloads requiring consistent data are rarely good places to use RCU. As noted in the figure, RCU's existence guarantees can be useful even in update-heavy situations because this allows simpler per-structure locking designs to be constructed, as is in fact the case for lfstack and rculfqueue—even though these data structures typically only have operations that update the structure itself. In effect, RCU is providing type-safe memory for algorithms using non-blocking synchronization. In addition, the low latency of RCU readers can be important to real-time applications in cases where the real-time threads do only reads, and non-real-time threads do updates.

So, in cases where RCU is the right tool for the job, what benefits does it provide?

1. Excellent performance and scalability for RCU readers.

2. Wait-free RCU readers, resulting in determinism, which can be quite useful for real-time applications.

3. Read-side immunity to lock-based deadlocks.

4. Existence guarantees that can simplify design of algorithms that use per-data-structure locks.

5. RCU read-side critical sections can be freely nested, enabling high levels of composability.

6. Because RCU read-side critical sections are not subject to rollback and retry, they can contain irrevocable operations such as I/O operations (in contrast to many transactional-memory implementations).

7. RCU readers and writers can make concurrent forward progress, even in the presence of conflicting operations. In contrast, many other synchronization operations impose some flavor of mutual exclusion, so that conflicts result in spinning, blocking, rollbacks, or retries.

8. RCU is independent of choice of memory allocator because it does not need to distinguish between pointers to the beginning of a given object and pointers internal to that object (in contrast with hazard pointers).

In short, within its area of applicability, RCU is a useful and powerful tool.

Quick Quiz 7: You say “read-side immunity to lock-based deadlocks”. So what non-lock-based deadlocks can involve RCU readers?

Answer

Quick Quiz 8: But given that most of the URCU implementations count the read-side nesting level, composability cannot be perfect, can it?

Answer

Application quiescent states

Kernels can use a context switch as a quiescent state, and many applications have similar natural quiescent states. However, just as RCU has hooks into the Linux scheduler in order to determine when context switches happen, applications using the QSBR flavor of URCU must tell RCU where those naturally occurring quiescent states are located using the rcu_quiescent_state(), rcu_thread_offline(), and rcu_thread_online() functions. For example, consider an application with a work-processing loop, such as show below:

Examples of such applications include those using work-stealing task frameworks. Each thread of this application processes one work item on each pass through its loop, then fetches the next work item. Because RCU read-side critical sections will not span units of work, a natural quiescent state occurs when each work item completes execution, as shown on the right-hand side of the diagram. The code represented by the green boxes can contain RCU read-side critical sections.

Quick Quiz 9: Can the code in the white rcu_quiescent_state() box contain RCU read-side critical sections?

Answer

In the typical work-stealing task framework, there is almost always work immediately available until the application terminates. In contrast, event-based systems might wait an arbitrary length of time for the next work item to arrive. URCU clearly needs to understand that a thread waiting on work to arrive is in a quiescent state, and the rcu_thread_offline() and rcu_thread_online() functions allow the application to tell URCU just that, as shown below:

The application executes rcu_thread_offline() after executing each work item, and then executes rcu_thread_online() immediately before starting execution of the next work item. Therefore, RCU read-side critical sections are permitted when executing a work item, but prohibited while waiting for the next work item.

In this way, the rcu_quiescent_state(), rcu_thread_offline(), and rcu_thread_online() allow the application to communicate the pertinent details of that application's structure to RCU.

Quick Quiz 10: But what if some portions of the “Wait For Next Work Item” code needed to use RCU read-side critical sections?

Answer

However, please note that these three functions are necessary only for the QSBR flavor of RCU. In the other four flavors, RCU is instead explicitly notified of the beginning and end of each RCU read-side critical section, so that the rcu_quiescent_state(), rcu_thread_offline(), and rcu_thread_online() functions are no-ops. Therefore, if your application does not have convenient quiescent states, you should use one of the other four RCU flavors.

Mixing and matching URCU flavors

Different compilation units can be using different flavors of RCU concurrently. This works extremely well when different modules or libraries are using RCU to access internal data structures: Each such module or library selects its flavor of RCU and uses it, and the multiple flavors operate independently as desired. One use case for this behavior is a tracer library for user-space applications and libraries (LTTng-UST), which in turn must use RCU-bp because it can neither control the application's threads nor even hook into their creation and destruction. This use case is supported quite naturally.

That said, it is necessary to take some care when passing RCU-protected data structures from one compilation unit to another. In some cases, it may be necessary to wrap the RCU functions in order to ensure that they are compiled in the correct compilation unit. In other cases, including the hash table described here, it is necessary to maintain function pointers to the selected RCU flavor's API members in order to allow the data structure to be safely manipulated by other compilation units that neither know or care what RCU flavor the data structure is using.

Building URCU

A number of Linux distributions provide the URCU library, including the Debian family (e.g., Ubuntu), Fedora, openSUSE, SUSE Enterprise RT Linux, Linaro, and all Yocto-based RT distros (e.g., Wind River Linux, Mentor Embedded Linux, Montavista, and ElinOS). However, if you want features and data structures from the latest version of the URCU library, you will need to download and build it.

The URCU library may be downloaded here. It can also be cloned or viewed using:

    git://git.liburcu.org/urcu.git
    https://github.com/urcu/userspace-rcu

Once downloaded, follow the build instructions in the README.

Summary

The user-space RCU library has been in existence for almost four years, and has grown from being just RCU to also including RCU-protected data structures, including a resizable hash table, a stack, and a couple of queues. We expect that more data structures will make their appearance over time, with possibilities including Judy arrays [PDF], bonsai trees [PDF], and many more besides. Other hoped-for enhancements include improved IPC (user space wait_event() and wake_up(), anyone?) and, of course, a locking validator similar to the Linux kernel's lockdep.

This library has been used by a number of projects, including LTTng-UST (User-Space Tracer) (for which it was first constructed), Knot DNS, the gdnsd geographic DNS server, the netsniff-ng toolkit, the Sheepdog Project, and an academic project on crowd simulation, as well as a number of commercial applications.

Acknowledgments

We are grateful to Jérémie Galarneau, Josh Triplett, Frédéric Weisbecker for their comments on a draft of this article. We owe thanks to Jim Wasko for his support of this effort.

Answers to Quick Quizzes

Quick Quiz 1: Why use rcu_assign_pointer() rather than the simple gptr=tmp assignment statement that the C language provided for this straightforward job???

Answer: Unfortunately, this job is not so straightforward. Remember that readers might be accessing gptr at any time: There is no way to stop them. We therefore need to prevent both the compiler and the CPU from mischievously reordering the memory references, which they are both otherwise fully within their rights to do. To see why this is important, suppose that either the compiler or the CPU decided to optimize the code by moving the gptr=tmp assignment statement so that it preceded the structure-initialization assignment statements. Then the concurrent readers might well load from gptr and get a pointer to a structure full of pre-initialization garbage. Not good!!!

Therefore, we use rcu_assign_pointer(gptr, tmp), which acts as a mischief-preventing assignment statement.

Back to Quick Quiz 1.

Quick Quiz 2: Why cds_list_del_rcu() instead of simply list_del_rcu() like the Linux kernel does?

Answer: We could not take the Linux kernel list primitives directly due to license issues, namely the Linux kernel's GPLv2 license as opposed to the user-space RCU library's LGPLv2.1-or-later license. Instead, the GNU C library's list primitives were pressed into service. There are a few differences from the kernel, and there will be more as the kernel's API evolves, so the cds_ prefix serves as a helpful reminder. In addition, names like list_add() and list_del() are already used by quite a few user applications, and the cds_ prefix helps avoid symbol-name clashes.

Back to Quick Quiz 2.

Quick Quiz 3: And just how is synchronize_rcu() supposed to know when all the currently executing RCU readers started? Doesn't that mean that all the RCU readers must do heavyweight operations to get the current time and store it somewhere? And doesn't this also require perfect time synchronization?

Answer: There are a number of ways for synchronize_rcu() to do its job, for example using the “Classic RCU” algorithm described here. Heavyweight read-side operations and perfect time synchronization are not required, although in-kernel RCU implementations have been known to complain when CPUs' notions of the current time differ by more than one minute.

Back to Quick Quiz 3.

Quick Quiz 4: Why the “reader” above? Doesn't every thread need reside in a quiescent state in order for a grace period to have elapsed?

Answer: The URCU Library API section introduces the rcu_register_thread() and rcu_unregister_thread() APIs. A reader thread is a thread that has invoked rcu_register_thread() and not yet invoked rcu_unregister_thread(). All other threads are forbidden from executing RCU read-side critical sections and are ignored by RCU.

Back to Quick Quiz 4.

Quick Quiz 5: When does RCU-protected list traversal compile to different assembly language than does simple single-threaded linked-list traversal?

Answer: In some flavors of user-space RCU, rcu_read_lock() and rcu_read_unlock() produce some lightweight code (more on this later). In all flavors of user-space RCU, cds_list_for_each_entry_rcu() uses the CMM_ACCESS_ONCE() macro (similar to ACCESS_ONCE() in the Linux kernel), which can disable some code-motion compiler optimizations. Finally, when running on DEC Alpha, cds_list_for_each_entry_rcu() contains a memory barrier.

Back to Quick Quiz 5.

Quick Quiz 6: Is it OK to use URCU_INLINE_SMALL_FUNCTIONS even in proprietary code?

Answer: Yes, it is. Use of URCU_INLINE_SMALL_FUNCTIONS inlines only small functions and macros that fit within LGPL's 10-line inlining limit for non-LGPL code.

See paragraph 4 of clause 5 of LGPL v2.1, which reads:

If such an object file uses only numerical parameters, data structure layouts and accessors, and small macros and small inline functions (ten lines or less in length), then the use of the object file is unrestricted, regardless of whether it is legally a derivative work. (Executables containing this object code plus portions of the Library will still fall under Section 6.)

Back to Quick Quiz 6.

Quick Quiz 7: You say “read-side immunity to lock-based deadlocks”. So what non-lock-based deadlocks can involve RCU readers?

Answer: Any sequence of events that can result in an RCU reader waiting for an RCU grace period results in deadlock in all RCU flavors except for QSBR. In QSBR, this bug results in splitting of the RCU read-side critical section containing the operation that waits on a grace period. Note that acquiring a lock that is held across a grace period can indirectly result in waiting for a grace period. There are of course a number of more elaborate ways of arriving at this sort of deadlock.

Back to Quick Quiz 7.

Quick Quiz 8: But given that most of the URCU implementations count the read-side nesting level, composability cannot be perfect, can it?

Answer: Indeed it cannot. This is an imperfect world, beset by finite-sized counters. And this problem is not restricted to RCU: Other composable synchronization operations have implementation-defined limits to nesting depth, and thus limits on composability.

Back to Quick Quiz 8.

Quick Quiz 9: Can the code in the white rcu_quiescent_state() box contain RCU read-side critical sections?

Answer: That is a matter that is internal to the RCU implementation. That said, any RCU read-side critical sections must be outside the area of code where RCU is ignoring this thread.

Back to Quick Quiz 9.

Quick Quiz 10: But what if some portions of the “Wait For Next Work Item” code needed to use RCU read-side critical sections?

Answer: Then the calls to rcu_thread_offline() and rcu_thread_online() would need to be moved into the “Wait For Next Work Item” code.

Back to Quick Quiz 10.

Comments (9 posted)

Quote of the week

— Matt Palmer (hat tip to Paul Wise)

Comments (9 posted)

PyDev 3.0 released

Version 3.0 of PyDev has been released, supporting Eclipse 3.7 or 4.3 and Java 7. Highlights include support for the Computational Crystallography Toolbox (CCTBX) and IPython 1.0, synchronization between the PyDev and Python interpreters, and numerous changes to the debugger, interpreter, and interactive console.

Full Story (comments: none)

Twisted 13.2.0 available

Version 13.2 of the Twisted framework has been released. This version adds support for "a HostnameEndpoint implementation which uses IPv4 and IPv6 in parallel, speeding up the connection by using whichever connects first (the 'Happy Eyeballs'/RFC 6555 algorithm)", as well as featuring recent contributions from Google Summer of Code and Outreach Program for Women students.

Full Story (comments: none)

NumPy 1.8.0 released

Version 1.8.0 of the NumPy Python extension for mathematical functions has been released. The release merges Python 2 and Python 3 support into a unified code base. Included among the changes are linear algebra functions on stacked arrays, functions to create value initialized arrays, and statistical functions that automatically skip NaNs.

Comments (none posted)

Development newsletters from the past week

• Caml Weekly News (November 12)
• What's cooking in git.git (November 6)
• What's cooking in git.git (November 11)
• What's cooking in git.git (November 13)
• Haskell Weekly News (November 6)
• Haskell Weekly News (November 12)
• Perl Weekly (November 10)
• PostgreSQL Weekly News (November 10)
• Ruby Weekly (November 7)
• Tor Weekly News (November 13)

Comments (none posted)

How did the Outreach Program for Women work out for the Linux kernel this year? (Opensource.com)

Opensource.com has an interview with Lisa Nguyen, focusing on her experience working on the Linux kernel as part of the Outreach Program for Women. "When I applied for the FOSS OPW program, the mentors provided a safe hacking space for someone like me who had never worked on the Linux kernel before. In the beginning, I found out that some applicants had Masters degrees, were long-term Linux users, and bragged about their accomplishments. I immediately thought, "Oh no, I don't have a chance now." I felt depressed for a few days until I chose to make myself stand out from the rest. I stopped thinking about how everyone else seemed more qualified, and before I knew it, I became one of the most memorable women in our IRC. I thanked every single person who gave me feedback and helped me troubleshoot issues. I said Hi to everyone whenever I logged into the IRC. These simple gestures made a huge difference, and I walked away with new friends and trust from multiple Linux kernel maintainers."

Comments (2 posted)

New Linux Magazine "Linux Voice"

Linux Voice is a new magazine from many of the former Linux Format editors. "We feel that Linux Voice isn't just a new magazine, but a new style of magazine that puts its readers and community ahead of profit, while at the same time, not compromising on quality."

Full Story (comments: none)

Ruby Under a Microscope--New from No Starch Press

No Starch Press has released "Ruby Under a Microscope" by Pat Shaughnessy.

Full Story (comments: none)

LibrePlanet 2014

LibrePlanet is the annual conference of the Free Software Foundation. The 2014 conference will take place March 22-23 in Cambridge, MA. The call for sessions deadline is November 22.

Full Story (comments: none)

Linux Audio Conference 2014 - Call for Participation

The Linux Audio Conference (LAC) will take place May 1-4, 2014 in Karlsruhe, Germany. The call for papers deadline is January 27, 2014.

Full Story (comments: none)

CFP Deadlines: November 14, 2013 to January 13, 2014

The following listing of CFP deadlines is taken from the LWN.net CFP Calendar.

Deadline	Event Dates	Event	Location
November 15	March 18 March 20	FLOSS UK 'DEVOPS'	Brighton, England, UK
November 22	March 22 March 23	LibrePlanet 2014	Cambridge, MA, USA
November 24	December 13 December 15	SciPy India 2013	Bombay, India
December 1	February 7 February 9	devconf.cz	Brno, Czech Republic
December 1	March 6 March 7	Erlang SF Factory Bay Area 2014	San Francisco, CA, USA
December 2	January 17 January 18	QtDay Italy	Florence, Italy
December 3	February 21 February 23	conf.kde.in 2014	Gandhinagar, India
December 15	February 21 February 23	Southern California Linux Expo	Los Angeles, CA, USA
December 31	April 8 April 10	Open Source Data Center Conference	Berlin, Germany
January 7	March 15 March 16	Chemnitz Linux Days 2014	Chemnitz, Germany
January 10	January 18 January 19	Paris Mini Debconf 2014	Paris, France

If the CFP deadline for your event does not appear here, please tell us about it.

Events: November 14, 2013 to January 13, 2014

The following event listing is taken from the LWN.net Calendar.

Date(s)	Event	Location
November 13 November 14	Korea Linux Forum	Seoul, South Korea
November 14 November 17	Mini-DebConf UK	Cambridge, UK
November 15 November 16	Linux Informationstage Oldenburg	Oldenburg, Germany
November 15 November 17	openSUSE Summit 2013	Lake Buena Vista, FL, USA
November 17 November 21	Supercomputing	Denver, CO, USA
November 18 November 21	2013 Linux Symposium	Ottawa, Canada
November 22 November 24	Python Conference Spain 2013	Madrid, Spain
November 25	Firebird Tour: Prague	Prague, Czech Republic
November 28	Puppet Camp	Munich, Germany
November 30 December 1	OpenPhoenux Hardware and Software Workshop	Munich, Germany
December 6	CentOS Dojo	Austin, TX, USA
December 10 December 11	2013 Workshop on Spacecraft Flight Software	Pasadena, USA
December 13 December 15	SciPy India 2013	Bombay, India
December 27 December 30	30th Chaos Communication Congress	Hamburg, Germany
January 6	Sysadmin Miniconf at Linux.conf.au 2014	Perth, Australia
January 6 January 10	linux.conf.au	Perth, Australia

If your event does not appear here, please tell us about it.