Tor and library freedom

The Tor project is working in concert with another non-profit organization in a push to bring private and anonymous browsing to public libraries. In particular, the two projects are collaborating on setting up Tor exit relays in libraries, beginning with a pilot program at a library in New Hampshire.

Spearheading the effort is the Library Freedom Project (LFP), a partnership that focuses on educating librarians about privacy and surveillance issues and equipping them with tools to address the challenges. In February, LFP won the "Knight News Challenge on Libraries" grant competition, and has been using the resulting funds to provide privacy education at libraries throughout the US and Canada, the UK and Ireland, and Australia, with more destinations still to come. A look at the resources (with more here) that LFP hosts for libraries provides some insight into its work—issues from password strength to PGP encryption to privacy-themed browser extensions are covered.

In July, though, LFP Director Alison Macrina announced the start of a more proactive project: to set up Tor exit relays on library networks. While all Tor nodes contribute to the health (and bandwidth) of the Tor network, exit relays are of particular importance because they are the gateway nodes through which traffic flows between Tor and the public Internet. Consequently, exit relays are at the highest risk for interference from ISPs or authorities that find some part of the traffic objectionable or that want to track users. See this recent story at BoingBoing for one account of how running a Tor exit relay can attract unwanted attention.

In the announcement, Macrina called libraries well equipped to handle the potential headaches that accompany running an exit relay, noting that:

In addition, she cited the American Library Association's (ALA's) Core Values of Librarianship, Freedom to Read Statement, and Code of Ethics as supporting a commitment to intellectual freedom and privacy. "Libraries serve a diverse audience; many of our community members are people who need Tor but don't know that it exists, and require instruction to understand and use it."

In the first stage of the program, LFP worked with Nima Fatemi from Tor to set up a middle (i.e., non-exit) relay at the Kilton Library in Lebanon, NH. The IT librarian at Kilton, Chuck McAndrew, already administers the library's public computers, which run Linux and are configured with Tor access plus a variety of other privacy measures.

The initial relay setup consists of a desktop PC running Debian and configured to use 10MB/s of the library's bandwidth. The relay is named LebLibraries and, as is the case with most Tor relays, interested parties can check its current status and recent performance on the Tor Globe site. According to the Globe statistics, LebLibraries first appeared online on July 20, then went offline before coming back online in more permanent fashion on the 22nd. Although it is hard to generalize from that small of a sample, the relay has more or less remained online, with just one incident of downtime between July 22 and publication time.

At any given moment, over 6,000 Tor relays are running, on average, of which about 1,000 are exit relays. The ALA estimates that there are over 119,000 public libraries in the US. Naturally, if even a small percentage of that total ran relays it would mark a substantial increase in the Tor network's capacity.

The relay running in the Kilton Library is just the first step. LFP said it intends to run the relay as a middle relay for about one month before reconfiguring it to serve as an exit relay, just to ensure that it does not interfere with the running of the rest of the library's network. Once the exit-relay transition happens, the project is likely to get its first test of how the non-technical side of managing a Tor relay impacts the library. If there are complaints from law enforcement, DCMA take-down requests, or other forms of criticism, other interested libraries will get to see how the Kilton staff and the LFP handle them and what the fallout is.

Moving forward, LFP plans to continue its campaign of privacy training for librarians, part of which includes providing help with setup for Tor Browser and related tools. Macrina commented that this training can be the first step toward convincing a library to run a relay, saying: "For libraries that have already installed Tor Browser on library PCs, running a relay is the obvious next step toward supporting free expression in their communities and all over the world."

It is also worth noting, though, that running a Tor relay may not be a viable option for every library at a technical level. The Kilton Library still required the expertise provided by Fatemi to set up and fully secure its test relay, and its IT librarian already had experience with Linux systems administration and Tor itself.

In an email, Macrina said that the availability of staffers to maintain relays would be a roadblock for some libraries, while others might be limited by their available bandwidth. Still, she added, the popularity of the LFP training program indicates that there is widespread interest in the subject. "Librarians are ready to take action against surveillance, and we see this as the necessary next step." She noted that a "not insignificant" portion of the librarian community was already quite familiar with Tor, although it is still a minority. But many more librarians without prior exposure to Tor have proven capable of understanding the technical details of running a relay—some just need a bit of assistance setting it up.

An assessment of the Kilton library's experience with its Tor relay should come in the next month or two, Macrina said, depending on her and Fatemi's schedules. In the meantime, LFP is inviting interested librarians to get in contact by filling out a questionnaire that covers various aspects of the library's network, hardware, and software organization—including whether or not it is already providing access to services like Tor. The concerns of public libraries may have a natural alignment to those of the Tor project, but it is good to see the interested parties making an active effort to reach out and work with one another.

Comments (5 posted)

Manipulating data streams with streamtools

Several years ago, when Yahoo was regularly doing battle with Google on the web-services front, one of its less-well-advertised properties that nevertheless proved popular with software developers was Yahoo Pipes. Yahoo Pipes was a web application that provided a graphical interface for manipulating RSS feeds—think "flow-based programming" applied to filtering, combining, and logically mixing RSS feed content. In June of 2015, Yahoo announced that it was shutting down Yahoo Pipes. Users who are searching for a replacement would do well to take a look at streamtools, which provides much the same functionality and can be self-hosted as well.

Streamtools is the product of The New York Times's research-and-development group, NYTLabs. Releases are available through GitHub; the latest is version 0.2.8 from August 2014. If that seems like far enough ago that one should worry about the project's health, it is also worth noting that there are multiple active forks—some from NYTLabs staff and some from outsiders. The last few releases were made in preparation for the public unveiling of streamtools at a 2014 conference; it would seem that the team now only adds functionality as it needs it.

The tool itself is written in Go; there is a single binary named st that launches a local web server on port 7070 and presents the user with a blank canvas. Individual data sources like site feeds are added as "blocks" that the user can place on the canvas and hook together: the output of one block can be fed into the inputs of an operator block, and the output of the operator block can be further manipulated or rendered as output.

The biggest difference between streamtools and Yahoo Pipes is that streamtools is built primarily to handle JSON streams rather than RSS. There are quite a few web services that have JSON-based public APIs, of course, but an RSS-only source would need to be transformed before streamtools could process it. Perhaps this is just another sign of the decreasing interest in RSS among web publishers; perhaps it is coincidental.

There are a few additional input block types defined in streamtools, though, that offer intriguing possibilities. They include IMAP, HTTP GET and POST requests, WebSockets, and Amazon's Simple Queuing System (SQS). The internal format of these other block types is converted to JSON, though.

The basic stream-manipulation blocks begin with primitive operations like join, mask, and filter. The join operation simply merges two JSON elements together, while mask strips an element down to just the attributes that you specify. The filter operation only passes incoming elements that match a pattern you supply—for example:

    {
          "foo": bar
    }

will only pass through elements whose "foo" attribute is exactly equal to "bar."

The expression:

    {
          "foo": {}
    }

in a mask block, however, will just strip all incoming stream elements down to their "foo" attributes.

The values of an attribute can be tested for more than just exact matching, of course—for example:

    {
        .foo < 42
    }

matches those elements where "foo" is less than 42. The syntax used for dealing with numeric and string comparisons is a little different, as this example shows. That said, its syntax is fairly straightforward, though it comes from another NYTLabs project called gojee and is designed for use with JSON manipulation. Thus, a quick read-though may be advisable.

But streamtools can do more complex manipulation of input streams as well. The pack block will concatenate all of the incoming elements that match a parameter into a single output object. The sync block allows you to introduce a timer to a stream, throttling the output to a particular speed or simply introducing some regularity to an unpredictable input.

The output options include writing JSON to a file, saving it in a MongoDB database, sending it as an email message, or initiating an Elasticsearch query. There are also functions available to do simple monitoring, such as displaying a live count of any tracked value, drawing histograms, or calculating moving averages.

On the whole, the streamtools basic function set is light on serious mathematical manipulation, but then again it is probably better to offload real number-crunching to something like R or a full-fledged database. What streamtools does excel at is grabbing live data off of the web and turning it into something that can be easily massaged into a form where other software can take over.

The NYTLabs site has several demo applications that one can experiment with (or build on one's own streamtools server), such as a tool that monitors the US Geological Survey feed for realtime earthquake data, and one that turns the New York City transit system's irregular updates about lost-and-found items into a well-formatted JSON stream.

Streamtools has the potential to do more than Yahoo Pipes did, and not just because it works with JSON (and other formats) out of the box. It is also an active, open-source software project, which means that no matter what The New York Times decides about its viability next year, it won't be unceremoniously shut down, leaving users in the lurch. As popular as Yahoo Pipes was in its heyday, it was still a proprietary service. By making streamtools open source, NYTLabs has the potential to give it a longer life.

Comments (1 posted)

"Big data" features coming in PostgreSQL 9.5

PostgreSQL 9.5 Alpha 2 is due to be released on August 6. Not only does the new version support UPSERT, more JSON functionality, and other new features we looked at back in July, it also has some major enhancements for "big data" workloads. Among these are faster sorts, TABLESAMPLE, GROUPING SETS and CUBE, BRIN indexes, and Foreign Data Wrapper improvements. Taken together, these features strengthen arguments for using PostgreSQL for data warehouses, and enable users to continue using it with bigger databases.

This release is still called an "alpha" because the PostgreSQL developers don't feel that it's entirely stable yet, and want to reserve the right to remove features that can't be fixed before the beta release. Among others, this includes the TABLESAMPLE feature described below; as of this writing, there are still problems with that patch and it could be dropped from 9.5.

PostgreSQL as a big data database

Some readers may not think of PostgreSQL for big data, but the database system has a long track record of use in data warehouses. For a decade before Hadoop launched, PostgreSQL was the only pure open-source option for large data volumes and complex analytics. Today, it is still heavily used in mid-sized data warehouses and "data marts", meaning databases in the one to ten terabyte range. Big data and analytics users are a major subset of the PostgreSQL community, and thus its contributor base, resulting in the addition of new features for large databases with each release.

More prominently, the European Union has chosen PostgreSQL as a key part of a publicly funded analytics technology project in the EU's Seventh Framework Programme, or "FP7". This project aims to enhance the technology base of the EU. Funding from FP7, channeled through the consulting firm 2nd Quadrant, paid for two of the features covered below, as well as performance testing and review work on others.

In addition to core features, the PostgreSQL project has been a source of code for many big data startups over the years. These include Netezza, Greenplum, ParAccel, Truviso, Aster Data Systems, and CitusDB. Both Yahoo! Everest and Amazon Redshift are PostgreSQL forks as well. In July, startup PipelineDB released an open-source streaming database that was forked from PostgreSQL 9.4. Streaming databases are used to process huge amounts of incoming data. These startups are generally attracted to PostgreSQL because of its sophisticated query planner and executor, liberal license, and well-documented code.

As hardware gets bigger and faster, the definition of "mid-sized data warehouse" keeps getting bigger and user expectations continue to grow. The PostgreSQL project continuously adds new features and better performance for big data use cases in order to keep up. Version 9.5 includes a lot of "goodies" for users with big databases.

Faster sorts

One thing relational databases do a lot of is sorting data. The bigger the database, the more the performance of those sorts becomes the dominating factor in overall response time. Sort time is critical not just for query results, but also for building indexes, grouping data, and certain kinds of joins. To help with this, PostgreSQL 9.5 comes with an across-the-board speedup in sorting text and long numeric values, yielding 3X to 12X speed improvements for many users.

Peter Geoghegan of Heroku wrote a patch in January that made text sorts faster by using a technique called "abbreviated keys". Previously, PostgreSQL sorted all text purely by using glibc's strcoll() function, which allows the database to sort in whatever locale the user has chosen for their data. The problem with this is that strcoll() is expensive, taking hundreds of times more CPU time than comparing integers.

Converting the text values to binary keys using strxfrm() and sorting them is much faster, except that those binary keys can be very large. So Peter hit on the technique of taking only the first eight bytes of the keys produced by strxfrm(), comparing those, and then breaking any ties by doing a full strcoll() comparison. This speeds up sorts of all kinds, both in-memory quicksorts and on-disk tapesorts. One user tested 9.5 with their data warehouse, and the new version reduced indexing eighteen million text values from almost eleven minutes to less than one minute.

After Geoghegan's patch was committed, contributor Andrew Gierth wrote a patch that uses a similar technique to speed up sorts on PostgreSQL's NUMERIC data type. In Postgres, NUMERIC is an arbitrary-precision number value, supporting over 100,000 digits. This means that it can't be sorted as an integer or float, so Gierth's improvement was welcome.

However, there still may be some issues with the sort improvements. Some platforms, especially older versions of Solaris, have buggy versions of the strxfrm() function that prevent use of this optimization. The developers are discussing whether these platforms are old enough, or obscure enough, to disregard so that most users can get enhanced performance, or whether platform-specific code might be required.

TABLESAMPLE

One feature funded by FP7 was written by Petr Jelinek; it adds the SQL-standard TABLESAMPLE query. This clause returns a pseudo-random sample of the rows in the result set. When used with large tables, TABLESAMPLE lets users get a quick "glimpse" of the data so that they can do further analysis.

For example, imagine that I have a table of 10 million user profiles in JSON. I want to take a look at a handful of rows from this table so that I can find out what kinds of keys the JSON has, but I don't want just the rows at the beginning of the table. In 9.5, I can do this:

    SELECT * FROM user_profiles TABLESAMPLE SYSTEM ( 0.001 );

Which will return around 0.001%, or 100, of the rows in the table. In the query above, SYSTEM is the name of the chosen sampling algorithm. The SYSTEM algorithm chooses a set of pseudo-random data pages, and then returns all rows on those pages, and has the advantage in running in constant time regardless of the size of the table. PostgreSQL 9.5 will also ship with the BERNOULLI sampling method, which is more rigorously random, but will take longer the larger the table is.

Currently, however, the TABLESAMPLE patch is under some intense review and rewriting. Tom Lane criticized the quality of the patch, and it remains to be seen if it will stay in 9.5.

CUBE, ROLLUP, and GROUPING SETS

In the SQL99 update of the SQL standard, the ANSI committee added a collection of grouping and reporting clauses to SQL to support the technology known as OLAP for "OnLine Analytical Processing". OLAP technologies, still used today, are ways to summarize and explore large data sets by grouping them in a multi-dimensional space. The three features added to SQL, ROLLUP, CUBE, and GROUPING SETS, provide different ways of summarizing data sets on several axes at once.

ROLLUP is the easiest to understand, since it simply provides subtotals and master totals for the whole set provided. For example, this query would provide counts for each city, then subtotals for each country, and finally a grand total of subscribers.

    SELECT country, city, count(*) 
    FROM lwn_subscribers
    GROUP BY ROLLUP ( country, city );

     country  |     city      | count 
    ----------+---------------+-------
    Australia | Brisbane      |   561
    Australia | Melbourne     |   302
    Australia | Perth         |   219
    Australia |               |  1082
    USA       | New York      |   591
    USA       | Portland      |   617
    USA       | San Francisco |   610
    USA       |               |  1818
	      |               |  2900

CUBE is less immediately understandable, because it's mainly intended to feed multi-dimensional data into an external OLAP tool like Mondrian. It expresses all possible totals for all combinations of specified columns, otherwise known as a "combinatorial explosion". For example, this query would provide totals for each country and each subscription level, and each combination of country and level.

    SELECT country, level, count(*) 
    FROM lwn_subscribers
    GROUP BY CUBE ( country, level );

     country  |    level     | count 
    ----------+--------------+-------
    Australia | leader       |   140
    Australia | professional |   490
    Australia | starving     |   394
    Australia | supporter    |    58
    Australia |              |  1082
    USA       | leader       |   301
    USA       | professional |   765
    USA       | starving     |   602
    USA       | supporter    |   150
    USA       |              |  1818
	      |              |  2900
	      | leader       |   441
	      | professional |  1255
	      | starving     |   996
	      | supporter    |   208

Finally, GROUPING SETS are sort of the "parent class" of both ROLLUP and CUBE. It allows you to select subtotal and total groups and combinations manually to display, in case you need more specific output than ROLLUP or CUBE provide.

For example, say I wanted totals for level and city, then level, and then a grand total, I would write:

    SELECT city, level, count(*)
    FROM lwn_subscribers
    GROUP BY GROUPING SETS ((city, level),(level),());

	 city      |    level     | count
    ---------------+--------------+-------
     Brisbane      | leader       |    94
     Melbourne     | leader       |    44
     New York      | leader       |   105
     Perth         | leader       |     2
     Portland      | leader       |    94
     San Francisco | leader       |   102
		   | leader       |   441
     Brisbane      | professional |   236
     Melbourne     | professional |   121
     New York      | professional |   250
     ...

The benefit for users in these query constructs is the ability to get totals, subtotals, and combinations in one query and one scan over the table, which in the past would have required multiple queries against the database. The other advantage for PostgreSQL is that it can now be supported by sophisticated "business intelligence" tools that previously only worked with proprietary SQL databases.

This feature was developed by Gierth, and has caused some discussion because of issues with the PostgreSQL review process that almost caused it to not get committed. It's now in and ready for users to try out.

Note: the above subscription data is fictitious and not related to LWN's actual subscription data.

BRIN indexes

Chilean committer Álvaro Herrera developed another feature funded by FP7. He wrote it to solve one of the major problems with really big tables: indexing them. PostgreSQL supports large tables easily, especially append-only tables, where the user may not even notice that the table has grown to several terabytes. However, standard B+ tree indexes grow increasingly inefficient at large numbers of leaf nodes, primarily because they no longer fit in memory.

Herrera figured out that "close" counts in indexes as much as it does with horseshoes and grenades. He devised a new index type that would index values down to an arbitrarily large "block" of data rather than to an individual data page. Instead of having a leaf node pointing to each individual row, the new index has a range of values to be found in each block. When the table is queried, the index is searched for ranges that correspond to the supplied filter conditions, and then the individual blocks are sequentially scanned. This approach is similar to how data is organized in column-store tables.

This new index type is called "BRIN" for "Block-Range INdex". These indexes are much smaller than conventional B+ trees — as little as 1% of the size of the standard indexes. This makes them much faster, since they usually fit in memory, and sometimes even in the CPU cache.

There are some drawbacks to BRIN indexes, though. They can't be used to enforce uniqueness or support keys. BRIN works much better on values that are incrementally increasing with each row inserted, like timestamps and incrementing integers. Most of all, BRIN indexes handle updates and deletes on the underlying table inefficiently, so they're best used with append-only tables. These restrictions would seem to make BRIN indexes a niche tool, except that large, continuously increasing append-only tables are a common use case. For example, any table used to hold a website log or an audit history can benefit.

Foreign Data Wrappers

In the last couple years, PostgreSQL has gained adoption as part of hybrid solutions involving several databases because of its Foreign Data Wrapper (FDW) feature. These wrappers allow users to link to external data in other databases, whether PostgreSQL or other platforms, and query them as if they were local tables. This has been called "data federation". For version 9.5, several developers have been hard at work on enhancements to the FDW capability.

One such enhancement is primarily administrative: IMPORT FOREIGN SCHEMA. In prior versions, if you wanted to link every table in a target remote database, you had to write individual CREATE FOREIGN TABLE statements for each one, which was tedious to do and annoying to maintain. Ronan Dunklau and Michael Paquier fixed this by implementing a command that creates all tables in the remote database as foreign tables so that you can link "the whole database" in one command.

The other major FDW improvement, JOIN pushdown, was introduced by KaiGai Kohei of NEC. Together with the new "custom scan" API, this allows FDWs to perform parts of queries, like index scans and joins between two tables, on the remote database before returning the result. Pushdown makes data federation much more scalable because it no longer requires sending entire tables across the wire for many common operations.

To take advantage of either of these features, though, the FDW driver for the external data source needs to support them. The postgres_fdw driver, which supports PostgreSQL-to-PostgreSQL connections, will support both, but many of the FDW drivers won't get them added for a while, if at all. Regardless, the improvements in FDWs make it more possible for PostgreSQL to be the interface for large data stores even where it is not the backend for them.

Other features

Several other features in PostgreSQL 9.5 will be of interest to users with large databases. PostgreSQL now makes more effective use of larger allocations of memory in "shared_buffers", by shrinking the array of page references kept by each process. GiST indexes, used for geographic searches, now support "index-only scans" for faster queries over large append-only tables. The vacuumdb utility now has a parallel, multi-process mode for doing maintenance on multiple large tables at once. Finally, UNLOGGED tables can be changed into regular tables, allowing users to build a data set and make it durable as the last step. UNLOGGED tables are non-durable tables that are not written to the transaction log, and are often used in data loading. This last feature was a Google Summer of Code project.

Outside of the core project, two tools have been updated that increase the size of databases PostgreSQL can handle. CitusData released version 1.3 of its cstore_fdw project, which adds a column-store option for tables. Column stores both compress data and makes large aggregation queries, like counts and totals, much faster. The company also released version 1.2 of pg_shard, a tool that "shards" a table by distributing it across a set of database nodes using a hash key. This allows table scans to be run on multiple machines in parallel.

Native parallel query, the ability to use multiple cores on the same machine to execute a large query, has been an active project for two years. Unfortunately, due to the technical challenges being more difficult than expected by the team led by EnterpriseDB programmer Robert Haas, no parallel query features have yet been committed. Parallel table scan is under active development for 9.6.

Overall, PostgreSQL continues to hold its own as the "good enough" big data database for many users, by both improving performance and adding new analytical features. We can expect to see larger PostgreSQL databases under 9.5 than we have before. The project further shows some possibility of expanding is ability to handle even bigger databases through federation and sharding, and via numerous forks. We'll have to wait to find out what 9.6 offers in this area.

PostgreSQL 9.5 Alpha 2 will be available on August 6th from PostgreSQL.org.

Comments (25 posted)

Fuzzing perf_events

You might be surprised to learn that starting with Linux 2.6.31 (in 2009) it has been rather easy to crash the Linux kernel. This date marks the introduction of the perf_event subsystem. It is likely that perf_event is not any more prone to errors than any other large kernel subsystem, but it has the distinction of being subjected to intense testing from the perf_fuzzer tool, which methodically probes the interface for bugs. Given enough time, the tool will trigger a crash (and often fill the system logs with warnings along the way).

For the past two years, an effort has been underway to fix every bug found by the perf_fuzzer. Progress has been made, thanks to the perf_event maintainers (especially Peter Zijlstra), who have been extremely patient and helpful in fixing the errors reported. The tool now takes hours to days before a crash occurs; previously crashes would happen within seconds. Most of the low-hanging fruit has been found, with the remaining problems tending toward complex race conditions that are hard to replicate, isolate, and fix.

Fuzzer background

A fuzzer is a tool that tests an interface by generating almost (but not quite) valid inputs with the intention of finding corner-cases that trigger unexpected behavior. The term dates back to 1988 when Barton Miller noticed that Unix utilities would die horribly when fed unexpected characters by his noisy ("fuzzy") modem connection. Since then, much work has been done on fuzzers, mostly by security researchers looking for exploitable bugs in programs.

The most common use case is to fuzz user-space programs, but work has been done on fuzzing operating system kernels. Various Linux kernel fuzzers are available (such as Tavis Ormandy's iknowthis) but by far the most well-known is Dave Jones's Trinity (see this conference report and this discussion of memory-management fuzzing for more information on Trinity). There are likely other kernel fuzzers out there; undoubtedly security researchers have developed internal ones that are not publicly available. What separates the perf_fuzzer from other projects is that it investigates not the entire kernel interface, but only that of a single system call.

Motivation

So why write a perf_event-specific fuzzer? I have spent much time in the performance-analysis area of High Performance Computing, specifically the maintenance of the cross-platform PAPI (Performance API) performance measurement library. The sudden appearance of the perf_event interface in 2009 (of which I have been diplomatically reported as being "sometimes critical") led to major code changes in the PAPI project. As an outside project, PAPI has faced many compatibility issues and ABI breakage due to kernel changes, issues the kernel developers tend not to notice due to the primary consumer of the interface (the perf tool) being shipped in sync with the kernel tree.

The need to keep up with the high rate of changes in the perf_event interface led me to undertake many activities designed to understand the interface, including writing the perf_event_open(2) man page as well as creating a series of validation tests. While these tests continue to find bugs, they tend to be reactionary—added after the fact (and often too late to be fixed before the new behavior has become ABI).

As Trinity rose in visibility, I sent some basic patches to improve perf_event support, enough that it had a much higher chance of generating valid events. Those patches were there for a few years until suddenly they became famous in 2013 due to the release of a dangerous kernel exploit. After this wakeup call, I wondered what other issues might be lurking in the interface. This led to more improvements contributed to Trinity, followed by the development of a separate, system-call-specific fuzzer.

The perf_event interface

The perf_event interface is complex, mirroring the complicated nature of the underlying hardware performance interfaces. The primary entry point is the perf_event_open() system call, which takes five arguments. The first argument is a structure with over forty different parameters that interact in complex ways. The system call returns one file descriptor per event opened; these file descriptors can be manipulated by a number of other system calls:

• prctl() — can enable or disable all active events in a process
• ioctl() — is used to control events, including starting, stopping, and adjusting existing events
• read() — can be used to read event values
• mmap() — can be used to set up a primary and an auxiliary ring buffer capable of buffering event results
• poll() — can be used to wait until buffers need to be read

In addition to system calls, there are other ways to interact with the infrastructure. Some CPUs support reading event values from user space without entering the kernel (on x86 this is the rdpmc instruction). Events can be configured to send a signal on overflow after a pre-determined count or if an mmap() buffer is full. There are also a large number of files under the /sys and /proc filesystems that affect the interface.

Much of the trickiness of the perf_event interface is due to the way it interacts with deep kernel internals. There are software events that count performance-critical operations such as context switches. The overflow interrupts are handled as non-maskable interrupts (NMIs) on many systems, which are often difficult to set up and tricky to debug. All user breakpoint support is handled by perf_event, and there are also interfaces for creating ftrace events and attaching eBPF filters. The wide scope of the perf_event code allows more chances for code to go wrong.

For the full details on the interface, you can read the manual page. In a testament to the complexity involved, this man page is the longest system-call man page, even longer than the one for ptrace().

How the fuzzer works

The perf_fuzzer program is just an infinite loop that randomly picks a piece of the interface to test each time through. Inputs are also picked randomly; while in theory using completely random inputs would eventually explore the entire search space, in practice this would take quite a long time. In order to more easily trigger bugs, inside knowledge of the interface is used to generate valid and mostly-valid event parameters in addition to purely random ones.

The following actions are chosen from at random:

• Open a random event — this code is shared in common with Trinity. The fuzzer repeats until a valid event is created.
• mmap() an event — attempts are made to attach regular and auxiliary mmap() buffers to an event.
• sigaction() an event — set up an overflow signal handler.
• Close an event.
• Call ioctl() on an event — this includes starting, stopping, refreshing, changing the period, attaching an ftrace filter, and attaching an eBPF program.
• prctl() the process — this will enable or disable all events.
• Read from an event.
• Access a /proc or /sys file.
• Fork the process — currently only one child process is allowed at a time to avoid fork bombs and file descriptor exhaustion.
• Poll an event.
• Doing nothing (to allow some variations in timing).

The difference between this tool and Trinity is that the latter simply attempts to open an event. In the rare occasion it generates a valid event, all further actions on the file descriptor are completely random. perf_fuzzer uses knowledge of the interface to pick the system calls known to be relevant and targets them, allowing bugs to be found much faster than a completely random search would.

Using the fuzzer

Running the fuzzer is straightforward. First check out the git tree:

    git clone http://www.github.com/deater/perf_event_tests.git

Enter the fuzzer directory, run make, and the perf_fuzzer binary will be generated. You can simply run that binary, but it typically will error out at some point due to some as-of-yet unexplained weirdness with signal handling. A better option is to run the included fast_repro99.sh script, which will repeatedly run the fuzzer for short amounts of time.

Before running, you probably want to configure your system to make error reporting easy. This usually involves setting up a serial console, as bugs are often hard crashes that cannot be captured easily otherwise. Once you have started the fuzzing it's just a matter of waiting. The fuzzer will print regular updates on its fuzzing status, such as:

    Iteration 10000
        Open attempts: 144277  Successful: 920  Currently open: 47
                EPERM : 24
                ENOENT : 783
                E2BIG : 12577
                EBADF : 12118
                EACCES : 588
                EBUSY : 6
                EINVAL : 116933
                EOPNOTSUPP : 328
                Type (Hardware 200/19733)(software 333/20972)\
		     (tracepoint 67/20782)(Cache 60/18015)\
		     (cpu 210/20976)(breakpoint 22/20669)\
		     (power 0/2625)(intel_bts 28/2456)\
		     (uncore_imc 0/2733)(#9 0/17)(#10 0/9)\
		     (#11 0/8)(#12 0/10)(#13 0/6)(#14 0/6)\
		     (>14 0/15260)
        Close:  873/873 Successful
        Read:   744/844 Successful
        Write:  0/887 Successful
        Ioctl:  328/873 Successful: (ENABLE 76/76)(DISABLE 82/82)\
	                            (REFRESH 6/104)(RESET 70/70)\
				    (PERIOD 5/84)(SET_OUTPUT 7/95)\
				    (SET_FILTER 2/108)(ID 80/80)\
				    (SET_BPF 0/84)(#9 0/0)(#10 0/0)\
				    (#11 0/0)(#12 0/0)(#13 0/0)\
				    (#14 0/0)(>14 0/90)
        Mmap:   434/1063 Successful: (MMAP 434/1063)(TRASH 95/146)\
	                             (READ 21/127)(UNMAP 428/1046)\
				     (AUX 0/251)(AUX_READ 3/14)
        Prctl:  880/880 Successful
        Fork:   450/450 Successful
        Poll:   820/897 Successful
        Access: 452/915 Successful
        Overflows: 0
        SIGIOs due to RT signal queue full: 0

If you do find a bug, please report it to the linux-kernel mailing list. It's helpful if you can isolate it first. At startup, the tool will output the command line (including the random number seed) to use to try to repeat the behavior. There are a large number of sources of non-determinism in performance-measurement code, but the perf_fuzzer tries to avoid as many of these as possible. It is often (but not always) possible to regenerate a bug by re-running the fuzzer with the same command line.

The fuzzer does support dumping system call traces, which can be fed into provided tools that both replay the traces as well as generate sample test code for repeating the problem. In the early days of the fuzzer, these tools were incredibly valuable. However, most bugs found these days tend to be obscure race conditions that are difficult to capture in this way, as the act of logging to disk disrupts timing enough to not trigger the bug.

Bugs found

A large number of issues have been turned up by the fuzzer: some are simply warnings, some cause denial of service (i.e. crashes), and at least one has been a root exploit.

All of these bugs can be problematic, as currently it is not possible to completely disable the perf_event interface, either at run time or compile time. Currently perf_event support must be built into the kernel, there is no possibility of making it a loadable module or disabling it during the build process. There have been some efforts to change this, but it is complicated by the fact that hardware breakpoint support depends on the presence of perf_event. In addition, while it is possible to disable some of the perf_event interface at runtime via /proc/sys/kernel/perf_event_paranoid, even at the most paranoid level it is still possible to create user-space measurement events.

A full list of all bugs found can be found on the project's website. Included below is a list of crashing bugs that have been found and fixed since the introduction of the tool; many more are still under investigation.

Type	CVE	Fixed in Linux		Description
crash	-	3.10	9bb5d40cd93c9dd4	mmap() accounting hole
crash	-	3.10	26cb63ad11e04047	mmap() double free
panic	-	3.11	d9f966357b14e356	ARM array out of bounds
root exploit	CVE-2013-4254	3.11	c95eb3184ea1a3a2	ARM event validation
panic	-	3.11	868f6fea8fa63f09	ARM64 array out of bounds
panic	-	3.11	ee7538a008a45050	ARM64 event validation
panic	-	3.13	6e22f8f2e8d81dca	Alpha array out-of-bounds
crash	CVE-2013-2930	3.13	12ae030d54ef2507	perf/ftrace wrong permissions check
crash	-	3.14	0ac09f9f8cd1fb02	page fault ftrace cr2 corruption
crash	-	3.15	46ce0fe97a6be753	race when removing event
crash	-	3.15	ffb4ef21ac4308c2	function cannot handle NULL return
reboot	-	3.17	3577af70a2ce4853	race in perf_remove_from_context()
crash	-	3.19	98b008dff8452653	misplaced parenthesis in rapl_scale()
crash	-	3.19	c3c87e770458aa00	fix the grouping condition
crash	-	3.19	a83fe28e2e453924	Fix put_event() ctx lock
crash	-	3.19	af91568e762d0493	IVB-EP uncore assign events
crash	-	4.0	d525211f9d1be8b5	Fix perf_callchain() hang
crash	-	4.1	8fff105e13041e49	arm64/arm reject groups spanning PMUs
crash	-	4.1	15c1247953e8a452	snb_uncore_imc_event_start() crash
crash	-	4.2	57ffc5ca679f499f	Fix AUX buffer refcounting

Sample bug

An example bug found by the fuzzer was the one that eventually lead to CVE-2013-4254. A routine fuzzing on a 32-bit ARM Pandaboard triggered a kernel panic. In this particular bug, the ARM validate_event() function called armpmu->get_event_idx() on the group leader for an event. However, if the group leader was not an armpmu type, but a PMU type with a shorter structure size (such as a software event), then the function pointer being called was whatever arbitrary value happened to be at that memory offset, which was past the end of the structure. Normally, this would just cause a panic and crash but, if you were unlucky, this arbitrary value was a valid user address. For a short window of time in the 3.11-rc development cycle, this value pointed to a location initialized to INT_MIN which is a valid user mappable address of 0x80000000. If a user mapped exploit code there, this bug could lead to privilege escalation, and some code was put together that did just that. Luckily, this bug was found and fixed before it made it into any released kernel.

Current and future work

Work on the fuzzer has been progressing. Now that bugs are harder to trigger there has been time available to enhance the functionality rather than spending the (sometimes considerable) time needed to push a bug through to a fix in the kernel tree.

Recent work includes adding support for testing new features (such as the introduction of the AUX ring buffer for high-volume events) as well as a push to fully test all of the perf_event ioctl() calls. Support for ioctl() is more complex than it sounds, as fuzzing it involved creating an ftrace filter generator (and the ftrace filter language is lacking documentation), as well as some method of fuzzing the new eBPF language. The eBPF fuzzing is currently stalled; even though there is existing code for generating eBPF programs in Trinity, it turns out you need to be root to actually attach such programs, and running perf_fuzzer as root is not advised. It might be worthwhile to harden the fuzzer so that it can run as root; part of the problem is there are various "expected" ways you can crash your machine as root. This includes setting the overflow threshold so low that the machine gets stuck in an interrupt storm, as well as problems where the ftrace function tracer can get stuck recursively trying to trace interrupt handler functions.

While I plan to continue to work on this project as long as it finds bugs, it is important to note that it is a volunteer effort with no support and few outside contributors. This can be frustrating at times, as noted by Dave Jones's recent comments regarding the Trinity fuzzer. I have encountered problems similar to his, where finding and fixing kernel bugs is appreciated, but the work is not considered important enough to get employer support. This work is also not considered groundbreaking enough to easily lead to publications or grants through traditional venues, which is needed by academics like myself. With the demise of the Ottawa Linux Symposium, there are also no longer any peer-reviewed conferences with proceedings for Linux, which are critical for academics trying to publish Linux-related work in a way that matters to their home institutions.

One area with room for improvement is the amount of testing that is done using perf_fuzzer. The current primary testing environment is a horribly abused Haswell desktop. Tests are also run on Intel Core 2, Pentium 4, and AMD Jaguar machines when convenient. It would be nice to test on other architectures; there is probably low-hanging fruit for the untested ones. Power is notable as an architecture with elaborate perf_event support but, as of yet, has not been tested. I have many ARM machines and try to test on those when possible. This is complicated because, when fuzzing, you want to run an up-to-the-minute mainline kernel (to avoid hitting older, known bugs), but it can be extremely time-consuming if not impossible to run mainline kernels on arbitrary ARM development boards.

One final area of future work would be to extend this to other system calls. There are many others out there that are currently not well-tested. Even if a custom tool is not designed, it would be worthwhile to extend Trinity with the lessons learned from perf_fuzzer. While fuzzing is not the only route to ensuring a secure kernel environment, it is definitely a powerful tool in the Linux security toolbox.

Comments (13 posted)

Security quotes of the week

— Bruce Schneier

— Bas Alberts in an interesting rant (Thanks to Paul Wise.)

— Lauren Weinstein on Windows Update Delivery Optimization

— Lorenzo Franceschi-Bicchierai

Comments (21 posted)

drupal7-path_breadcrumbs: cross-site scripting

Package(s):	drupal7-path_breadcrumbs	CVE #(s):
Created:	July 30, 2015	Updated:	August 5, 2015
Description:	From the Drupal advisory: The module didn't sufficiently filter user input values [in the] administration interface.
Alerts:	Fedora FEDORA-2015-11858 drupal7-path_breadcrumbs 2015-07-30 Fedora FEDORA-2015-11836 drupal7-path_breadcrumbs 2015-07-30

Comments (none posted)

ipython: cross-site request forgery

Package(s):	ipython	CVE #(s):	CVE-2015-5607
Created:	July 30, 2015	Updated:	August 5, 2015
Description:	From the Red Hat bugzilla entry: POST requests exposed via the IPython REST API are vulnerable to cross-site request forgery (CSRF). Web pages on different domains can make non-AJAX POST requests to known IPython URLs, and IPython will honor them. The user's browser will automatically send IPython cookies along with the requests. The response is blocked by the Same-Origin Policy, but the request isn't.
Alerts:	Mageia MGASA-2015-0300 ipython 2015-08-03 Fedora FEDORA-2015-11767 ipython 2015-07-30 Fedora FEDORA-2015-11677 ipython 2015-07-30

Comments (none posted)

ipython: cross-site scripting

Package(s):	ipython	CVE #(s):	CVE-2015-4707
Created:	August 4, 2015	Updated:	August 5, 2015
Description:	From the Mageia advisory: JSON error responses from the IPython notebook REST API contained URL parameters and were incorrectly reported as text/html instead of application/json. The error messages included some of these URL params, resulting in a cross site scripting attack
Alerts:	Mageia MGASA-2015-0300 ipython 2015-08-03

Comments (none posted)

kernel: denial of service

Package(s):	kernel	CVE #(s):	CVE-2015-3212
Created:	July 31, 2015	Updated:	August 18, 2015
Description:	From the Debian bug tracker: SCTP race condition allows list corruption and panic from userlevel.
Alerts:	openSUSE openSUSE-SU-2016:0301-1 kernel 2016-02-01 Oracle ELSA-2015-2152 kernel 2015-11-25 Oracle ELSA-2015-3098 kernel 3.8.13 2015-11-13 Oracle ELSA-2015-3098 kernel 3.8.13 2015-11-13 Oracle ELSA-2015-3078 kernel 2015-09-16 Oracle ELSA-2015-3078 kernel 2015-09-16 Scientific Linux SLSA-2015:1778-1 kernel 2015-09-15 Oracle ELSA-2015-1778 kernel 2015-09-15 CentOS CESA-2015:1778 kernel 2015-09-16 Red Hat RHSA-2015:1787-01 kernel-rt 2015-09-15 Red Hat RHSA-2015:1788-01 kernel-rt 2015-09-15 Red Hat RHSA-2015:1778-01 kernel 2015-09-15 Ubuntu USN-2714-1 linux-ti-omap4 2015-08-17 Ubuntu USN-2718-1 linux-lts-vivid 2015-08-17 Ubuntu USN-2717-1 linux-lts-utopic 2015-08-17 Ubuntu USN-2715-1 linux-lts-trusty 2015-08-17 Ubuntu USN-2719-1 kernel 2015-08-17 Ubuntu USN-2716-1 kernel 2015-08-17 Ubuntu USN-2713-1 kernel 2015-08-17 openSUSE openSUSE-SU-2015:1382-1 kernel 2015-08-14 Debian DSA-3329-1 kernel 2015-08-07 SUSE SUSE-SU-2015:1324-1 kernel 2015-07-31

Comments (none posted)

moodle: multiple vulnerabilities

Package(s):	moodle	CVE #(s):	CVE-2015-3272 CVE-2015-3274 CVE-2015-3275
Created:	August 4, 2015	Updated:	August 5, 2015
Description:	From the Mageia advisory: In Moodle before 2.8.7, phishing is possible when redirecting to external site using referer headers in error messages (CVE-2015-3272). In Moodle before 2.8.7, several web services returning user information did not clean text in text custom profile fields, leading to possible XSS (CVE-2015-3274). In Moodle before 2.8.7, possible Javascript injection was discovered in the SCORM module (CVE-2015-3275).
Alerts:	Fedora FEDORA-2015-14996 moodle 2015-09-15 Fedora FEDORA-2015-14988 moodle 2015-09-15 Mageia MGASA-2015-0302 moodle 2015-08-03

Comments (none posted)

nx-libs: unspecified vulnerabilities

Package(s):	nx-libs	CVE #(s):
Created:	July 30, 2015	Updated:	August 5, 2015
Description:	From the Fedora advisory: Proper integration of all patches in the source tarballs. Bugs in the tarball generation script and patch file names prohibited inclusion of many patches previously, including security fixes.
Alerts:	Fedora FEDORA-2015-11244 nx-libs 2015-07-30

Comments (none posted)

openafs: multiple vulnerabilities

Package(s):	openafs	CVE #(s):	CVE-2015-3282 CVE-2015-3283 CVE-2015-3284 CVE-2015-3285
Created:	July 31, 2015	Updated:	September 8, 2015
Description:	From the Scientific Linux advisory: CVE-2015-3282: vos leaks stack data onto the wire in the clear when creating vldb entries. CVE-2015-3283: bos commands can be spoofed, including some which alter server state. CVE-2015-3284: pioctls leak kernel memory. CVE-2015-3285: kernel pioctl support for OSD command passing can trigger a panic.
Alerts:	Debian-LTS DLA-342-1 openafs 2015-11-18 Debian DSA-3320-1 openafs 2015-07-30 Scientific Linux unknown openafs 2015-07-30 Mageia MGASA-2015-0337 openafs 2015-09-08

Comments (none posted)

openafs: denial of service

Package(s):	openafs	CVE #(s):	CVE-2015-3287
Created:	July 31, 2015	Updated:	August 5, 2015
Description:	From the OpenAFS advisory: The vlserver allows pattern matching on volume names via regular expressions when listing attributes. Because the regular expression is not checked for situations which can overflow the buffers used, an attack is possible which reads arbitrary memory beyond the end of the buffer and can act on it as part of the expression evaluation, potentially crashing the process.
Alerts:	Debian DSA-3320-1 openafs 2015-07-30

Comments (none posted)

openssh: improper output filtering

Package(s):	openssh	CVE #(s):
Created:	July 31, 2015	Updated:	August 5, 2015
Description:	From the Fedora bug report: The scp utility shipped with OpenSSH does not filter out non-printable characters when it displays a progress meter during the actual secure-copy process. So when a file is created with embedded control characters and it is scp'ed those control characters are run on the local terminal (on the client side), these can have undesired visible affects on the current terminal.
Alerts:	Fedora FEDORA-2015-12054 openssh 2015-08-03 Fedora FEDORA-2015-12177 openssh 2015-07-31

Comments (none posted)

oxide-qt: code execution

Package(s):	oxide-qt	CVE #(s):	CVE-2015-1329
Created:	August 5, 2015	Updated:	August 5, 2015
Description:	From the Ubuntu advisory: A use-after-free was discovered in oxide::qt::URLRequestDelegatedJob in some circumstances. If a user were tricked in to opening a specially crafted website, an attacker could potentially exploit this to cause a denial of service via application crash, or execute arbitrary code with the privileges of the user invoking the program.
Alerts:	Ubuntu USN-2677-1 oxide-qt 2015-08-04

Comments (none posted)

php: multiple vulnerabilities

Package(s):	php	CVE #(s):
Created:	August 4, 2015	Updated:	August 5, 2015
Description:	From the Mageia advisory: The php package has been updated to version 5.6.11, fixing several bugs and security issues. See the upstream Changelog for more details.
Alerts:	Mageia MGASA-2015-0303 php 2015-08-03

Comments (none posted)

remind: buffer overflow

Package(s):	remind	CVE #(s):	CVE-2015-5957
Created:	August 3, 2015	Updated:	September 21, 2015
Description:	From the Mageia advisory: Buffer overflow in remind before 3.1.15 in the DumpSysVar() function in src/var.c.
Alerts:	openSUSE openSUSE-SU-2015:1579-1 remind 2015-09-19 Debian-LTS DLA-289-1 remind 2015-08-07 Mageia MGASA-2015-0299 remind 2015-08-02

Comments (none posted)

sqlite3: code execution

Package(s):	sqlite3	CVE #(s):	CVE-2013-7443
Created:	July 31, 2015	Updated:	August 5, 2015
Description:	From the Ubuntu advisory: It was discovered that SQLite incorrectly handled skip-scan optimization. An attacker could use this issue to cause applications using SQLite to crash, resulting in a denial of service, or possibly execute arbitrary code. This issue only affected Ubuntu 14.04 LTS.
Alerts:	Ubuntu USN-2698-1 sqlite3 2015-07-30

Comments (none posted)

squid: security bypass

Package(s):	squid3	CVE #(s):	CVE-2015-5400
Created:	July 30, 2015	Updated:	September 9, 2015
Description:	From the Debian LTS advisory: Alex Rousskov discovered that Squid configured with cache_peer and operating on explicit proxy traffic does not correctly handle CONNECT method peer responses. In some configurations, it allows remote clients to bypass security in an explicit gateway proxy.
Alerts:	SUSE SUSE-SU-2016:2089-1 squid3 2016-08-16 openSUSE openSUSE-SU-2016:2081-1 squid 2016-08-16 SUSE SUSE-SU-2016:1996-1 squid3 2016-08-09 Fedora FEDORA-2016-7b40eb9e29 squid 2016-05-06 Fedora FEDORA-2016-7b40eb9e29 libecap 2016-05-06 Debian DSA-3327-1 squid3 2015-08-03 Mageia MGASA-2015-0347 squid 2015-09-08 Debian-LTS DLA-286-1 squid3 2015-07-30

Comments (none posted)

wordpress: cross-site scripting

Package(s):	wordpress	CVE #(s):	CVE-2015-3429
Created:	August 4, 2015	Updated:	August 5, 2015
Description:	From the CVE entry: Cross-site scripting (XSS) vulnerability in example.html in Genericons before 3.3.1, as used in WordPress before 4.2.2, allows remote attackers to inject arbitrary web script or HTML via a fragment identifier.
Alerts:	Debian DSA-3328-2 wordpress 2015-08-04 Debian DSA-3328-1 wordpress 2015-08-04

Comments (none posted)

wpa_supplicant: code execution

Package(s):	wpa_supplicant	CVE #(s):	CVE-2015-1863
Created:	July 30, 2015	Updated:	August 5, 2015
Description:	From the Fedora advisory: Fix for NDEF record payload length checking
Alerts:	Gentoo 201606-17 hostapd 2016-06-27 Fedora FEDORA-2015-11691 wpa_supplicant 2015-07-30

Comments (none posted)

xmltooling: denial of service

Package(s):	xmltooling	CVE #(s):	CVE-2015-0851
Created:	July 31, 2015	Updated:	September 9, 2015
Description:	From the Debian advisory: The InCommon Shibboleth Training team discovered that XMLTooling, a C++ XML parsing library, did not properly handle an exception when parsing well-formed but schema-invalid XML. This could allow remote attackers to cause a denial of service (crash) via crafted XML data.
Alerts:	Debian-LTS DLA-290-2 opensaml2 2015-08-10 Debian-LTS DLA-290-1 xmltooling 2015-08-09 Debian DSA-3321-2 opensaml2 2015-08-08 Debian DSA-3321-1 xmltooling 2015-07-30 Mageia MGASA-2015-0350 xmltooling 2015-09-08

Comments (none posted)

xrdp: denial of service

Package(s):	xrdp	CVE #(s):
Created:	July 30, 2015	Updated:	August 5, 2015
Description:	From the Red Hat bugzilla entry: It was discovered by Ken Milnore that xrdp 0.6.1 and earlier, when validating user accounts against plain passwd files or via shadow-utils, does not check for NULL returns from crypt(). A NULL return crashes the xrdp-sesman daemon resulting in an xrdp server denial of service (for all modules that use xrdp's session manager for user authentication via old-style passwd files or via shadow passwords).
Alerts:	Fedora FEDORA-2015-11688 xrdp 2015-07-30 Fedora FEDORA-2015-11756 xrdp 2015-07-30

Comments (none posted)

Kernel release status

The current development kernel is 4.2-rc5, released on August 2. Linus is wishing things were going a bit more smoothly. "We're getting up there to the later rc's, but it's looking like 4.2 might be one of the releases needing more than the usual seven rc releases - things aren't calming down like I would wish, and we've still had some fairly annoying issues pop up."

Stable updates: 4.1.4, 3.14.49, and 3.10.85 were released on August 3.

Comments (none posted)

Quotes of the week

— Geert Uytterhoeven

— Steve Rostedt

— Dave Airlie

Comments (none posted)

Real-world use of Linux multipath TCP

LWN looked at the Linux multipath TCP implementation back in 2013. That code remains out of tree, but it now seems that it is being used in some Samsung phones in Korea. "This service enables smartphone users to reach bandwidth of up to 1 Gbps on existing smartphones. This is probably the fastest commercially deployed mobile network. They achieve this high bandwidth by combining both fast LTE (with carrier aggregation) and fast WiFi networks on Multipath TCP enabled smartphones." (Thanks to Oliver Bonaventure).

Comments (11 posted)

ioremap() and memremap()

Like user space, the kernel accesses memory through page tables; as a result, when kernel code needs to access memory-mapped I/O devices, it must first set up an appropriate kernel page-table mapping. The in-kernel tool for that job has long been ioremap(), which has a number of variants. It turns out that some of those variants are not always the right tool for the job, leading to a certain amount of workaround code in the kernel. That situation may change, though, as part of a move away from ioremap() for the problematic cases.

A successful call to ioremap() returns a kernel virtual address corresponding to start of the requested physical address range. This address is not normally meant to be dereferenced directly, though, for a number of (often architecture-specific) reasons. Instead, accessor functions like readb() or iowrite32() should be used. To enforce this rule, the return address from ioremap() is annotated with the __iomem marker; that will cause the sparse checker to complain about accesses that do not use the proper functions.

There is also the little matter of caching. The CPU normally caches data from memory, but that is a bad idea when I/O is involved for a number of reasons. Attempts to read a full cache line from I/O memory can have no end of unexpected side effects, and delaying writes to I/O memory can change the way the device operates. I/O memory should normally function as a direct control channel to the device; to that end, ioremap() disables caching on device memory — on the x86 architecture, at least.

In truth, the caching status of a memory range obtained from ioremap() is not fully defined. As a general rule, uncached is the default, but there is still an ioremap_nocache() that can be called by code that wants to be absolutely sure that there will be no cache between it and its device memory.

In some cases, though, I/O memory is just memory; the video memory used by a graphics adapter is a classic example. With this kind of memory, direct pointer references can be expected to work and caching in the CPU may be acceptable; indeed, it may be required to get reasonable performance. For such cases, there is an ioremap_cache() that creates a cached mapping if possible. Most architectures also have a couple of variants that allow caching of reads but limit caching of writes. In particular, ioremap_wc() allows combining of write operations and ioremap_wt() causes writes to go directly to device memory. With these variants, driver writers can obtain the kind of mapping they need for a specific piece of device memory.

Dan Williams recently ran into a couple of problems with this family of functions, though. One is that they all return pointers with the __iomem annotation. A driver that is mapping I/O memory with caching enabled almost certainly will treat the resulting address range as if it were ordinary memory — including directly dereferencing pointers into that range. To do so, they must either cast away the __iomem annotation or simply ignore it. In the former case, the code is noisier than it would otherwise be; in the latter case, anybody running sparse on the code will have to ignore the resulting warnings.

Beyond that, many architectures do not support all of the various caching modes, so the architecture-specific header files are full of lines like:

    #define ioremap_wt ioremap_nocache

The result is that callers of functions like ioremap_wt() may silently fail to get the writethrough caching that they are asking for.

Dan's answer to both problems is a patch set adding a new function for the mapping of device memory that behaves like memory:

    void *memremap(resource_size_t offset, size_t size, unsigned long flags);

This function will (on success) return an address for a mapping to the device memory found at the given physical offset and of the given size (in bytes). The flags argument can be either MEMREMAP_WB for full writeback caching or MEMREMAP_WT for writethrough caching. The returned address does not have the __iomem annotation. If the requested caching behavior cannot be provided, memremap() will return NULL rather than fall back to a different type of caching.

The patch set converts most in-kernel code over to the new interface.

This work is in its third revision as of this writing, and the (few) review comments made have been addressed. It clarifies the driver API, clearly separating two different use cases for the mapping of device memory, and it should result in less sparse warning noise. There is not much to dislike at this point, so there shouldn't be much keeping it out of the 4.3 merge window.

Comments (none posted)

Atomic mode setting design overview, part 1

Over the past few years, two big trends forged the need for a completely new kernel display driver interface. On one hand, people stopped appreciating partial redrawing and windows torn to pieces when anything changed in their GUI. New compositors like Wayland have been created with the slogan that "every frame is perfect". On the other hand, there are battery-powered phones and tablets with fancy graphical interfaces, but serious limits on power consumption. And that brought along an explosion of special-purpose display hardware to help out the rather power-hungry, but more general purpose, GPU in compositing screen contents. Bringing these trends together yields the need to update a lot of display hardware state in an all-or-nothing, atomic manner to ensure every frame is perfect and all the power-usage-optimized hardware is used as much as possible.

After a few years of development, the atomic display update ioctl() for Direct Rendering Manager (DRM) drivers is finally ready for prime time with the 4.2 pull request from Dave Airlie. It's been a long road, with a lot of drivers already converted over to atomic and even more in progress, and the atomic helper libraries and support code in the DRM subsystem sufficiently polished. But what's really missing is a design overview of what the overall atomic infrastructure looks like and why some decisions and details are implemented the way they are.

This article, which is first of the two articles in a series, will start with a recap of the history of kernel display mode-setting support to explain how the older interfaces came to be and why they're no longer suitable. It will then look at out-of-tree solutions and finally cover what the merged atomic display update interface looks like. The second article will delve deeper into some of the details of the implementation.

Before digging into all the details, a quick overview over how display hardware is represented today in the DRM subsystem is needed. First there is struct drm_connector which represents a screen, whether that's an integrated panel or an external screen. Note that connectors can be hot-plugged nowadays, since DisplayPort supports branching and multiplexing of multiple devices over one cable, similar to other peripheral buses. At the other end there's struct drm_plane, representing a scanout engine that reads pixel data from memory represented by a struct drm_framebuffer and provides it to the display hardware.

To allow drivers to support hardware features beyond what's possible with the core control data for each object, DRM supports properties that can be attached to any DRM object. There are different types of properties that accept different inputs like enumerations (e.g. for selecting between upscaling modes like pillarbox or letterbox) or integer ranges (e.g. for brightness control).

With fancy hardware, a plane can be freely positioned in the output rectangle, scaled or otherwise adjusted. Both ends are tied together with a struct drm_crtc which represents a display pipeline. Note that CRTC means "cathode ray tube controller" and hence is one of those abbreviations that only make historical sense. Multiple planes can be connected to a single CRTC to provide it with input data, and such a display pipeline then, in turn, connects to one or more drm_connectors to actually show something on screens. Besides being the central object for routing, a CRTC also keeps track of other settings like the display mode (i.e. refresh rate and resolution) used by the display pipeline and the background color that should be shown where no plane is visible at all.

The old world — A pile of ioctl() commands and properties

There's a much better and detailed writeup of the mode-setting history around, so I'll just focus on the more recent bits. The new age of display drivers in the kernel started in earnest almost seven years ago with the initial merge of the KMS (kernel mode setting) support. Well, there was always fbdev, but that subsystem never gained dearly needed support for proper graphics memory management, didn't have a clean separation between display and rendering, and never solved a host of other troubles.

Initial KMS ioctl() commands were modeled after X's user-space mode-setting protocol XRandR, which means they were good enough to set modes on screens individually and connect a single primary framebuffer object (representing a driver-specific memory buffer) with that display. This was all designed when rotating desktop cubes were all the rage and everyone wanted to use the 3D rendering engine for desktop compositing only — old-style video overlay planes seriously fell out of favor (you can't wobble them!) and hence weren't supported at all.

Well, there was one exception: cursor support. But that was just a bolted-on ioctl() that didn't even use the KMS framebuffer abstraction. And cursor updates couldn't be synced to anything, neither primary framebuffer updates nor the vertical blank — X didn't need it and couldn't use it. Without synchronizing to the vertical blanking (Vsync for short), the screen redrawing can race with the update and result in ugly tearing effects. Later on non-blocking updates for the primary plane were added to have support for proper Vsynced, non-tearing updates of the primary plane.

Of course, then smartphones and tablets showed up, so it wasn't cool to blow through power for display anymore. Suddenly overlay planes became important again since they're much more power-efficient in some narrow but popular use cases like video playback. KMS gained support for them in the form of additional plane objects and a new set of ioctl() commands.

But, like cursor updates, plane updates couldn't be synced to anything else, neither plane updates nor Vsync, again because X couldn't do more and nothing else cared about upstream graphics. The result was a mess of three different ioctl() interfaces for essentially just different instances of the same hardware. Planes, whether primary, cursor, or overlay, all take a framebuffer object that then all get blended together somehow, before being fed to a display pipeline (represented by a CRTC object in kernel mode setting), which feeds the connectors and panels. Unifying the plane interfaces was fairly simple: primary and cursor planes simply had to be exported as such, optionally, in order to not confuse existing user space.

But there was still no unified ioctl() that could do it all; for example, only the primary plane supported non-blocking updates with precise completion events. And there was no interface to update multiple planes together — user space had to make multiple ioctl() calls and hope that the updates all happened in the same frame. That's obviously a no-go for modern compositors like Wayland that want to guarantee pixel-perfect updates for every frame.

The other thing that happened is adding property support to all KMS objects to easily expose additional features like controlling the blending between planes, setting a background color, or rotating planes or the entire output. Of course, that was again done with a separate ioctl(). And, again, because X couldn't do any better back when this was introduced, there's no way to synchronize updates. Which means broken updates become ever more likely, as, for example when the rotation value is already updated but the plane contents aren't yet updated to match. If it's possible at all — some values can only be changed together or in a specific order, like disabling an additional plane before switching the primary one to a more memory-bandwidth-demanding mode.

It was all a mess and in dire need of a solution.

Android's Atomic Display Framework

Outside of upstream graphics, especially in Android-land, the situation was even worse. Every GPU vendor had its own kernel/user-space interfaces and all the drivers were reinventing the same wheels, but broken in slightly different ways. Google was unhappy about the state of things and created the Atomic Display Framework (ADF). It was inspired a bit by the upstream kernel mode-setting support, but was a completely new subsystem otherwise. For our tour, the overall design isn't useful to look at, but it's interesting to look at where ADF fell short for upstream use:

• ADF supports only one update queue for the entire device. That's a perfect fit for Android's SurfaceFlinger, which just has one draw loop, and it's totally sufficient for phones and tablets where, in most cases, you only ever have one screen. But if you have multiple screens, which usually run at slightly different refresh rates, then one update queue isn't enough. You have to either stall the faster screen or drop frames on the slower one, both of which will result in not-perfectly-smooth animations. The non-blocking primary plane updates in upstream are already fully decoupled and compositors like Wayland already have per-output redraw loops. This was a big omission from ADF.
• ADF describes atomic updates in a driver-specific blob of data. That's fine for Android where you have a GPU-specific counterpart driver in user space behind the Hardware Composer interface (similar to an X device driver like xf86-video-intel). But upstream also wants to support generic user-space compositors like Wayland or the xf86-video-modesetting X driver. ADF has a generic interface for updates, but it's only really good enough for a simple boot splash. Of course there will always be some features specific to one driver, but by standardizing properties across drivers, upstream DRM already has the infrastructure to support arbitrary functionality in generic user-space code.
• ADF was only atomic for plane updates and not for reconfiguring the output routing. Again, this is not a problem if you only really care about the single-screen case, but on modern GPUs there are lots of shared resources when using more than one output. And the naive way of reconfiguring by just looping over all outputs can easily end up in a state that isn't supported by the hardware, for example because the driver ran out of display clock generators for the interim configuration. Hence atomic updates for the entire pipeline across all outputs was definitely needed in upstream. More important was some means to figure out whether a change would work out or not before applying it and risking being stuck with a black screen.
• ADF was implemented as a monolithic mid-layer subsystem. That's great if your goal is to improve the state of the art for 90% of all drivers and a real pain if your driver is one of the 10% where the mid-layer just doesn't fit. Despite some horror shows in some upstream DRM legacy subsystems, the mode-setting part is nicely structured by exposing the full interface from the ioctl() to the driver hooks and providing a big helper library for all the common cases. Definitely something to keep.
• ADF also has a completely new user-space ABI and driver interface, which would mean separate drivers for everything. Not desirable from a backward compatibility and maintenance point of view.

Of course solving these problems isn't all that easy. The following sections in this article and the next one will look at some of them in more detail and describe how it's done in the atomic support that was merged.

A generic driver interface that's actually useful

Since DRM already has properties, it was fairly clear to reuse them as the generic transport for the user-space ABI. User space simply supplies a list of (object_id, property_id, value) triples. And that immediately takes care of extensibility — user space that doesn't understand a given property just doesn't ever change it. As long as a driver initializes everything to something sane (like setting the rotation property to unrotated) then older generic user space will keep on working when new features get added.

Of course there were some gaps with that plan — properties for all the existing metadata had to be added, with a special flag to only expose them to atomic-aware user space. A new property type has been created that accepts kernel mode-setting objects as values to set up routing links. And a few other bits needed adjustments, like extending blob properties to make them usable for atomic updates.

Allowing partial updates also solved the in-kernel backward compatibility problem: All the old KMS ioctl() commands did partial updates, only allowing full updates would have meant that drivers needed to support both legacy and atomic interfaces. With partial atomic update support, legacy driver hooks can instead be implemented in terms of the atomic driver entry points in a generic helper library.

Finally, there was the question of exposing hardware and driver limitations to user space. There are many of those, and every time a new property is standardized it becomes more complex. Trying to describe constraints explicitly was quickly discarded as impossible; the only thing the kernel can do is reject requests for impossible states (or even just transitions, as sometimes that's the limiting factor). But that would require driver-specific user space, rendering all the effort with a generic interface moot.

Instead, the atomic ioctl() supports a DRM_MODE_ATOMIC_TEST_ONLY flag to not actually commit the update to the hardware. With this, generic user space can build up the state it wants step-by-step using some heuristics and test each time around whether the update will still work, until it's found the maximal configuration. For example, a compositor could add planes one-by-one in order of preference of what would save the most power when using a hardware plane to compose a given client buffer onto the screen and then fall back to using OpenGL for any remaining client buffers. It can then queue the real update once everything is ready with the assurance that it will work out. Assuming no bugs in drivers, of course. This way, generic user space can use hardware with really strange restrictions, without explicitly describing those restrictions in the interface. Of course it won't always make a perfect decision, but in most cases it will be good enough.

This was all settled fairly quickly and, except for some cosmetics, the upstream atomic user-space ABI has stayed unchanged since the first RFC was floated about three years ago. The big question that took a few years to settle was the core-to-driver interface. Just passing the same list of triples to drivers would have been easiest and was done for proof-of-concept implementations. But that would have meant a brittle and verbose interface for in-kernel users, and for the final atomic support there would be a lot of those to handle all the legacy ioctl() commands and legacy users like fbdev emulation. Simply passing decoded structures around, like with the old hooks, wasn't an option either because of the need for driver-private extensions and partial updates.

The currently merged solution is quite a bit of a beast. First there are generic state structures for each type of mode-setting object that you can assign properties for. The state structure for planes, for example, is:

    struct drm_plane_state {
	struct drm_plane *plane;

	struct drm_crtc *crtc;
	struct drm_framebuffer *fb;

	/* Signed dest location allows it to be partially off screen */
	int32_t crtc_x, crtc_y;
	uint32_t crtc_w, crtc_h;

	/* ... */

	struct drm_atomic_state *state;
    };

Every state structure has a pointer to the object the state is for. Then follows all the object-specific KMS state decoded into the kernel-internal representations. For planes, this is a pointer to the CRTC (which represents a display pipeline) the plane is attached to, and a pointer to the framebuffer it should scan out, the position of the plane on the display window, and a few other things left out for clarity. And, finally, a backpointer to a drm_atomic_state structure. This keeps track of all the various per-object states of an update, allowing partial updates at the object level.

When an update finally gets committed, a pointer to the state is stored in each object, here for planes that would be plane->state. When committing states, the plane->state->state backpointer is also cleared since, once committed, the state structure is owned by the driver and no longer owned by the update structure itself.

Partial updates within an object are done by duplicating the existing state. And support for driver-private extensions is handled by allowing drivers to embed struct drm_plane_state into their own structures. That means there's an ->atomic_duplicate_state() hook with a default implementation like drm_atomic_helper_plane_duplicate_state(). Since a few of the objects pointed at by state structures are reference counted (like framebuffers), there's also a ->atomic_destroy_state() hook to clean everything up. For all the hooks there's a default implementation even when there's not yet a need for it — that way it's easy to standardize the handling of some properties by moving them from driver-specific structures into the core ones.

This way, generic code and drivers that only implement generic properties never have to deal with the raw property IDs and values directly, as all the decoding is done in the core code implementing the atomic ioctl(). For fancy drivers, there's the ->atomic_set_property() and ->atomic_get_property() hooks that again operate on the state structures and are used for decoding additional properties.

Besides all these functions and hooks to handle per-object state structures, the main atomic driver interface is simple and consists of only two hooks:

• ->atomic_check() needs to make sure that the passed-in atomic update is possible. It is only allowed to look at and write to state structures for objects referenced from the passed-in struct drm_atomic_state. On one hand, this is needed to make sure that the TEST_ONLY mode doesn't accidentally change persistent hardware or software state. The other reason is to make sure that concurrent updates don't trample on each another by accident — duplicating a state also grabs the required locks behind the scenes. Locking will be discussed in more detail in the second part of this article series.
• ->atomic_commit() optionally commits the state that has been prepared and checked by ->atomic_check(). Drivers are allowed and encouraged to store derived state (like display clock configuration) in the driver-private part of their state objects to avoid duplicating logic between the check and commit hooks. Note that for robustness, such derived state should be cleared when duplicating state objects, to make sure that correct values are always computed. The commit function is only allowed to fail due to lack of memory or catastrophic hardware failure. Any other problem with the update (like lack of shared resources on the GPU) must be caught earlier in the check callback.

The next article will discuss a few more details of the interface around handling asynchronous updates and locking. Of course, drivers don't have to implement the main atomic hooks completely themselves, since that's anything but trivial — there's a large helper library that will also be covered.

Comments (10 posted)

RCU requirements part 2 — parallelism and software engineering

This is the second of a three-article series on the requirements that have driven the read-copy-update (RCU) design toward its current form. Part 1 covered the fundamental requirements that make RCU what it is. In this installment, we'll get into the issues that affect how those fundamental requirements are met; in particular, we'll look at:

• Parallelism facts of life
• Quality-of-implementation requirements
• Software-engineering requirements

Also, of course, no RCU article would be complete without the answers to the quick quizzes at the end.

Parallelism facts of life

These parallelism facts of life are by no means specific to RCU, but the RCU implementation must abide by them. They therefore bear repeating:

1. Any CPU or task may be delayed at any time, and any attempts to avoid these delays by disabling preemption, interrupts, or whatever are completely futile. This is most obvious in preemptible user-level environments and in virtualized environments (where a given guest OS's virtual CPUs can be preempted at any time by the underlying hypervisor), but can also happen in bare-metal environments due to ECC errors, NMIs, and other hardware events. Although a delay of more than about 20 seconds can result in warnings, the RCU implementation is obligated to use algorithms that can tolerate extremely long delays, but where “extremely long” is not long enough to allow wraparound when incrementing a 64-bit counter.
2. Both the compiler and the CPU can reorder memory accesses. Where it matters, RCU must use compiler directives and memory-barrier instructions to preserve ordering.
3. Conflicting writes to memory locations in any given cache line will result in expensive cache misses. Greater numbers of concurrent writes and more-frequent concurrent writes will result in more dramatic slowdowns. RCU is therefore obligated to use algorithms that have sufficient locality to avoid significant performance and scalability problems.
4. As a rough rule of thumb, only one CPU's worth of processing may be carried out under the protection of any given exclusive lock. RCU must therefore use scalable locking designs.
5. Counters are finite, especially on 32-bit systems. RCU's use of counters must therefore tolerate counter wrap, or be designed such that counter wrap would take way more time than a single system is likely to run. An uptime of ten years is quite possible, a runtime of a century much less so. As an example of the latter, RCU's dyntick-idle nesting counter allows 54 bits for the interrupt-nesting level (this counter is 64 bits even on a 32-bit system). Overflowing this counter requires 2⁵⁴ half-interrupts on a given CPU without that CPU ever going idle. If a half-interrupt happened every microsecond, it would take 570 years of runtime to overflow this counter, which is currently believed to be an acceptably long time.
6. Linux systems can have thousands of CPUs running a single Linux kernel in a single shared-memory environment. RCU must therefore pay close attention to high-end scalability.

This last parallelism fact of life means that RCU must pay special attention to the preceding facts of life. The idea that Linux might scale to systems with thousands of CPUs would have been met with some skepticism in the 1990s, but these requirements would have otherwise have been unsurprising, even in the early 1990s.

Quality-of-implementation requirements

These sections list quality-of-implementation requirements. Although an RCU implementation that ignores these requirements could still be used, it would likely be subject to limitations that would make it inappropriate for industrial-strength production use. Classes of quality-of-implementation requirements are as follows:

1. Specialization
2. Performance and scalability
3. Composability
4. Corner cases

These classes are covered in the following sections.

Specialization

RCU is and always has been intended primarily for read-mostly situations, as illustrated by the following figure. This means that RCU's read-side primitives are optimized, often at the expense of its update-side primitives.

This focus on read-mostly situations means that RCU must interoperate with other synchronization primitives. For example, the add_gp() and remove_gp_synchronous() examples discussed earlier use RCU to protect readers and locking to coordinate updaters. However, the need extends much farther, requiring that a variety of synchronization primitives be legal within RCU read-side critical sections, including spinlocks, sequence locks, atomic operations, reference counters, and memory barriers.

It often comes as a surprise that many algorithms do not require a consistent view of data, but many can function in that mode, with network routing being the poster child. Internet routing algorithms take significant time to propagate updates, so that by the time an update arrives at a given system, that system has been sending network traffic the wrong way for a considerable length of time. Having a few threads continue to send traffic the wrong way for a few more milliseconds is clearly not a problem: In the worst case, TCP retransmissions will eventually get the data where it needs to go. In general, when tracking the state of the universe outside of the computer, some level of inconsistency must be tolerated due to speed-of-light delays if nothing else.

Furthermore, uncertainty about external state is inherent in many cases. For example, a pair of veterinarians might use heartbeat to determine whether or not a given cat was alive. But how long should they wait after the last heartbeat to decide that the cat is in fact dead? Waiting less than 400 milliseconds makes no sense because this would mean that a relaxed cat would be considered to cycle between death and life more than 100 times per minute. Moreover, just as with human beings, a cat's heart might stop for some period of time, so the exact wait period is a judgment call. One of our pair of veterinarians might wait 30 seconds before pronouncing the cat dead, while the other might insist on waiting a full minute. The two veterinarians would then disagree on the state of the cat during the final 30 seconds of the minute following the last heartbeat.

Interestingly enough, this same situation applies to hardware. When push comes to shove, how do we tell whether or not some external server has failed? We send messages to it periodically, and declare it failed if we don't receive a response within a given period of time. Policy decisions can usually tolerate short periods of inconsistency. The policy was decided some time ago, and is only now being put into effect, so a few milliseconds of delay is normally inconsequential.

However, there are algorithms that absolutely must see consistent data. For example, the translation between a user-level System V semaphore ID to the corresponding in-kernel data structure is protected by RCU, but it is absolutely forbidden to update a semaphore that has just been removed. In the Linux kernel, this need for consistency is accommodated by acquiring spinlocks located in the in-kernel data structure from within the RCU read-side critical section, and this is indicated by the green box in the figure above. Many other techniques may be used, and are in fact used within the Linux kernel.

In short, RCU is not required to maintain consistency, and other mechanisms may be used in concert with RCU when consistency is required. RCU's specialization allows it to do its job extremely well, and its ability to interoperate with other synchronization mechanisms allows the right mix of synchronization tools to be used for a given job.

Performance and scalability

Energy efficiency is a critical component of performance today, and Linux-kernel RCU implementations must therefore avoid unnecessarily awakening idle CPUs. I cannot claim that this requirement was premeditated. In fact, I learned of it during a telephone conversation in which I was given “frank and open” feedback on the importance of energy efficiency in battery-powered systems and on specific energy-efficiency shortcomings of the Linux-kernel RCU implementation. In my experience, the battery-powered embedded community will consider any unnecessary wakeups to be extremely unfriendly acts. So much so that mere Linux-kernel-mailing-list posts are insufficient to vent their ire.

Memory consumption is not particularly important in most situations, and it has become decreasingly so as memory sizes have expanded and memory costs have plummeted. However, as I learned from Matt Mackall's bloatwatch efforts, memory footprint is critically important on single-CPU systems with non-preemptible (CONFIG_PREEMPT=n) kernels, and thus tiny RCU was born. Josh Triplett has since taken over the small-memory banner with his Linux kernel tinification project, which resulted in SRCU becoming optional for those kernels not needing it.

The remaining performance requirements are, for the most part, unsurprising. For example, in keeping with RCU's read-side specialization, rcu_dereference() should have negligible overhead (for example, suppression of a few minor compiler optimizations). Similarly, in non-preemptible environments, rcu_read_lock() and rcu_read_unlock() should have exactly zero overhead.

In preemptible environments, in the case where the RCU read-side critical section was not preempted (as will be the case for the highest-priority realtime process), rcu_read_lock() and rcu_read_unlock() should have minimal overhead. In particular, they should not contain atomic read-modify-write operations, memory-barrier instructions, preemption disabling, interrupt disabling, or backward branches. However, in the case where the RCU read-side critical section was preempted, rcu_read_unlock() may acquire spinlocks and disable interrupts. This is why it is better to nest an RCU read-side critical section within a preempt-disable region than vice versa, at least in cases where that critical section is short enough to avoid unduly degrading realtime latencies.

The synchronize_rcu() grace-period-wait primitive is optimized for throughput. It may therefore incur several milliseconds of latency in addition to the duration of the longest RCU read-side critical section. On the other hand, multiple concurrent invocations of synchronize_rcu() are required to use batching optimizations so that they can be satisfied by a single underlying grace-period-wait operation. For example, in the Linux kernel, it is not unusual for a single grace-period-wait operation to serve more than 1,000 separate invocations of synchronize_rcu(), thus amortizing the per-invocation overhead down to nearly zero. However, the grace-period optimization is also required to avoid measurable degradation of realtime scheduling and interrupt latencies.

In some cases, the multi-millisecond synchronize_rcu() latencies are unacceptable. In these cases, synchronize_rcu_expedited() may be used instead, reducing the grace-period latency down to a few tens of microseconds on small systems, at least in cases where the RCU read-side critical sections are short. There are currently no special latency requirements for synchronize_rcu_expedited() on large systems, but, consistent with the empirical nature of the RCU specification, that is subject to change. However, there most definitely are scalability requirements: a storm of synchronize_rcu_expedited() invocations on 4096 CPUs should at least make reasonable forward progress. In return for its shorter latencies, synchronize_rcu_expedited() is permitted to impose modest degradation of realtime latency on non-idle online CPUs. That said, it will likely be necessary to take further steps to reduce this degradation, hopefully to roughly that of a scheduling-clock interrupt.

There are a number of situations where even synchronize_rcu_expedited()'s reduced grace-period latency is unacceptable. In these situations, the asynchronous call_rcu() can be used in place of synchronize_rcu() as follows:

 1 struct foo {
 2   int a;
 3   int b;
 4   struct rcu_head rh;
 5 };
 6 
 7 static void remove_gp_cb(struct rcu_head *rhp)
 8 {
 9   struct foo *p = container_of(rhp, struct foo, rh);
10 
11   kfree(p);
12 }
13 
14 bool remove_gp_asynchronous(void)
15 {
16   struct foo *p;
17 
18   spin_lock(&gp_lock);
19   p = rcu_access_pointer(gp);
20   if (!p) {
21     spin_unlock(&gp_lock);
22     return false;
23   }
24   rcu_assign_pointer(gp, NULL);
25   call_rcu(&p->rh, remove_gp_cb);
26   spin_unlock(&gp_lock);
27   return true;
28 }

A definition of struct foo is finally needed, and appears on lines 1-5. The function remove_gp_cb() is passed to call_rcu() on line 25, and will be invoked after the end of a subsequent grace period. This gets the same effect as remove_gp_synchronous(), but without forcing the updater to wait for a grace period to elapse. The call_rcu() function may be used in a number of situations where neither synchronize_rcu() nor synchronize_rcu_expedited() would be legal, including within preempt-disable code, local_bh_disable() code, interrupt-disable code, and interrupt handlers. However, even call_rcu() is illegal within NMI handlers. The callback function (remove_gp_cb() in this case) will be executed within the softirq (software interrupt) environment within the Linux kernel (either within a real softirq handler or under the protection of local_bh_disable()). In both the Linux kernel and in user space, it is bad practice to write an RCU callback function that takes too long. Long-running operations should be relegated to separate threads or (in the Linux kernel) workqueues.

However, all that remove_gp_cb() is doing is invoking kfree() on the data element. This is a common idiom, and is supported by kfree_rcu(), which allows “fire and forget” operation as shown below:

 1 struct foo {
 2   int a;
 3   int b;
 4   struct rcu_head rh;
 5 };
 6 
 7 bool remove_gp_faf(void)
 8 {
 9   struct foo *p;
10 
11   spin_lock(&gp_lock);
12   p = rcu_dereference(gp);
13   if (!p) {
14     spin_unlock(&gp_lock);
15     return false;
16   }
17   rcu_assign_pointer(gp, NULL);
18   kfree_rcu(p, rh);
19   spin_unlock(&gp_lock);
20   return true;
21 }

Note that remove_gp_faf() simply invokes kfree_rcu() and proceeds, without any need to pay any further attention to the subsequent grace period and kfree(). It is permissible to invoke kfree_rcu() from the same environments as for call_rcu(). Interestingly enough, DYNIX/ptx had the equivalents of call_rcu() and kfree_rcu(), but not synchronize_rcu(). This was due to the fact that RCU was not heavily used within DYNIX/ptx, so the very few places that needed something like synchronize_rcu() simply open-coded it.

But what if the updater must wait for the completion of code to be executed after the end of the grace period, but has other tasks that can be carried out in the meantime? The polling-style get_state_synchronize_rcu() and cond_synchronize_rcu() functions may be used for this purpose, as shown below:

 1 bool remove_gp_poll(void)
 2 {
 3   struct foo *p;
 4   unsigned long s;
 5 
 6   spin_lock(&gp_lock);
 7   p = rcu_access_pointer(gp);
 8   if (!p) {
 9     spin_unlock(&gp_lock);
10     return false;
11   }
12   rcu_assign_pointer(gp, NULL);
13   spin_unlock(&gp_lock);
14   s = get_state_synchronize_rcu();
15   do_something_while_waiting();
16   cond_synchronize_rcu(s);
17   kfree(p);
18   return true;
19 }

On line 14, get_state_synchronize_rcu() obtains a “cookie” from RCU, then line 15 carries out other tasks, and finally, line 16 returns immediately if a grace period has elapsed in the meantime, but otherwise waits as required. The need for get_state_synchronize_rcu and cond_synchronize_rcu() has appeared quite recently, so it is too early to tell whether they will stand the test of time.

RCU thus provides a range of tools to allow updaters to strike the required tradeoff between latency, flexibility and CPU overhead.

Composability

Composability has received much attention in recent years, perhaps in part due to the collision of multicore hardware with object-oriented techniques designed in single-threaded environments for single-threaded use. And, in theory, RCU read-side critical sections may be composed, and in fact may be nested arbitrarily deeply. In practice, as with all real-world implementations of composable constructs, there are limitations.

Implementations of RCU for which rcu_read_lock() and rcu_read_unlock() generate no code, such as Linux-kernel RCU when CONFIG_PREEMPT=n, can be nested arbitrarily deeply. After all, there is no overhead. Except that if all these instances of rcu_read_lock() and rcu_read_unlock() are visible to the compiler, compilation will eventually fail due to exhausting memory, mass storage, or user patience, whichever comes first. If the nesting is not visible to the compiler, as is the case with mutually recursive functions each in its own translation unit, stack overflow will result. If the nesting takes the form of loops, either the control variable will overflow or (in the Linux kernel) you will get an RCU CPU stall warning. Nevertheless, this class of RCU implementations is one of the most composable constructs in existence.

RCU implementations that explicitly track nesting depth are limited by the nesting-depth counter. For example, the Linux kernel's preemptible RCU limits nesting to INT_MAX. This should suffice for almost all practical purposes. That said, a consecutive pair of RCU read-side critical sections between which there is an operation that waits for a grace period cannot be enclosed in another RCU read-side critical section. This is because it is not legal to wait for a grace period within an RCU read-side critical section: to do so would result either in deadlock or in RCU implicitly splitting the enclosing RCU read-side critical section, neither of which is conducive to a long-lived and prosperous kernel.

In short, although RCU read-side critical sections are highly composable, care is required in some situations, just as is the case for any other composable synchronization mechanism.

Corner cases

A given RCU workload might have an endless and intense stream of RCU read-side critical sections, perhaps even so intense that there was never a point in time during which there was not at least one RCU read-side critical section in flight. RCU cannot allow this situation to block grace periods: as long as all the RCU read-side critical sections are finite, grace periods must also be finite.

That said, preemptible RCU implementations could potentially result in RCU read-side critical sections being preempted for long durations, which has the effect of creating a long-duration RCU read-side critical section. This situation can arise only in heavily loaded systems, but systems using realtime priorities are of course more vulnerable. Therefore, RCU priority boosting is provided to help deal with this case. That said, the exact requirements on RCU priority boosting will likely evolve as more experience accumulates.

Other workloads might have very high update rates. Although one can argue that such workloads should instead use something other than RCU, the fact remains that RCU must handle such workloads gracefully. This requirement is another factor driving batching of grace periods, but it is also the driving force behind the checks for large numbers of queued RCU callbacks in the call_rcu() code path. Finally, high update rates should not delay RCU read-side critical sections, although some read-side delays can occur when using synchronize_rcu_expedited(), courtesy of this function's use of try_stop_cpus(). (In the future, synchronize_rcu_expedited() will be converted to use lighter-weight inter-processor interrupts (IPIs), but this will still disturb readers, though to a much smaller degree.)

Although all three of these corner cases were understood in the early 1990s, a simple user-level test consisting of close(open(path)) in a tight loop in the early 2000s suddenly provided a much deeper appreciation of the high-update-rate corner case. This test also motivated addition of some RCU code to react to high update rates, for example, if a given CPU finds itself with more than 10,000 RCU callbacks queued, it will cause RCU to take evasive action by more aggressively starting grace periods and more aggressively forcing completion of grace-period processing. This evasive action causes the grace period to complete more quickly, but at the cost of restricting RCU's batching optimizations, thus increasing the CPU overhead incurred by that grace period.

Software-engineering requirements

Between Murphy's Law and “to err is human”, it is necessary to guard against mishaps and misuse:

1. It is all too easy to forget to use rcu_read_lock() everywhere that it is needed, so kernels built with CONFIG_PROVE_RCU=y will complain if rcu_dereference() is used outside of an RCU read-side critical section. Update-side code can use rcu_dereference_protected(), which takes a lockdep expression to indicate what is providing the protection. If the indicated protection is not provided, a lockdep "splat" (a warning and traceback) is emitted.

   Code shared between readers and updaters can use rcu_dereference_check(), which also takes a lockdep expression, and emits a lockdep splat if neither rcu_read_lock() nor the indicated protection is in place. In addition, rcu_dereference_raw() is used in those (hopefully rare) cases where the required protection cannot be easily described. Finally, rcu_read_lock_held() is provided to allow a function to verify that it has been invoked within an RCU read-side critical section. I was made aware of this set of requirements shortly after Thomas Gleixner audited a number of RCU uses.

2. A given function might wish to check for RCU-related preconditions upon entry, before using any other RCU API. The rcu_lockdep_assert() does this job, asserting the expression in kernels having lockdep enabled and doing nothing otherwise.
3. It is also easy to forget to use rcu_assign_pointer() and rcu_dereference(), perhaps (incorrectly) substituting a simple assignment. To catch this sort of error, a given RCU-protected pointer may be tagged with __rcu, after which running sparse with CONFIG_SPARSE_RCU_POINTER=y will complain about simple-assignment accesses to that pointer. Arnd Bergmann made me aware of this requirement, and also supplied the needed patch series.
4. Kernels built with CONFIG_DEBUG_OBJECTS_RCU_HEAD=y will splat if a data element is passed to call_rcu() twice in a row, without a grace period in between. (This error is similar to a double free.) The corresponding rcu_head structures that are dynamically allocated are automatically tracked, but rcu_head structures allocated on the stack must be initialized with init_rcu_head_on_stack() and cleaned up with destroy_rcu_head_on_stack(). Similarly, statically allocated non-stack rcu_head structures must be initialized with init_rcu_head() and cleaned up with destroy_rcu_head(). Mathieu Desnoyers made me aware of this requirement, and also supplied the needed patch.
5. An infinite loop in an RCU read-side critical section will eventually trigger an RCU CPU stall-warning splat. However, RCU is not obligated to produce this splat unless there is a grace period waiting on that particular RCU read-side critical section. This requirement made itself known in the early 1990s, pretty much the first time that it was necessary to debug a CPU stall.
6. Although it would be very good to detect pointers leaking out of RCU read-side critical sections, there is currently no good way of doing this. One complication is the need to distinguish between pointers leaking and pointers that have been handed off from RCU to some other synchronization mechanism, for example, reference counting.
7. In kernels built with CONFIG_RCU_TRACE=y, RCU-related information is provided via both debugfs and event tracing.
8. Open-coded use of rcu_assign_pointer() and rcu_dereference() to create typical linked data structures can be surprisingly error-prone. Therefore, RCU-protected linked lists and, more recently, RCU-protected hash tables are available. Many other special-purpose RCU-protected data structures are available in the Linux kernel and the user-space RCU library.
9. Some linked structures are created at compile time, but still require __rcu checking. The RCU_POINTER_INITIALIZER() macro serves this purpose.
10. It is not necessary to use rcu_assign_pointer() when creating linked structures that are to be published via a single external pointer. The RCU_INIT_POINTER() macro is provided for this task and also for assigning NULL pointers at runtime.

This is not a hard-and-fast list: RCU's diagnostic capabilities will continue to be guided by the number and type of usage bugs found in real-world RCU usage.

The final installment in this series will cover issues specific to the Linux kernel and the future of RCU.

Answers to the quick quizzes

Quick Quiz 11: What about sleeping locks?

Answer: These are forbidden within Linux-kernel RCU read-side critical sections because it is not legal to place a quiescent state (in this case, voluntary context switch) within an RCU read-side critical section. However, sleeping locks may be used within user-space RCU read-side critical sections, and also within Linux-kernel sleepable RCU (SRCU) read-side critical sections. In addition, the -rt patchset turns spinlocks into a sleeping lock so that the corresponding critical sections can be preempted, which also means that these sleeplockified spinlocks (but not other sleeping locks!) may be acquired within -rt-Linux-kernel RCU read-side critical sections.

Note that it is legal for a normal RCU read-side critical section to conditionally acquire a sleeping lock (as in mutex_trylock()), but only as long as it does not loop indefinitely attempting to conditionally acquire that sleeping lock. The key point is that things like mutex_trylock() either return with the mutex held, or return an error indication if the mutex was not immediately available. Either way, mutex_trylock() returns immediately without sleeping.

Back to Quick Quiz 11.

Quick Quiz 12: Why does line 19 use rcu_access_pointer()? After all, call_rcu() on line 25 stores into the structure, which would interact badly with concurrent insertions. Doesn't this mean that rcu_dereference() is required?

Answer: Presumably the ->gp_lock acquired on line 18 excludes any changes, including any insertions that rcu_dereference() would protect against. Therefore, any insertions will be delayed until after ->gp_lock is released on line 25, which in turn means that rcu_access_pointer() suffices.

Back to Quick Quiz 12.

Quick Quiz 13: Earlier it was claimed that call_rcu() and kfree_rcu() allowed updaters to avoid being blocked by readers. But how can that be correct, given that the invocation of the callback and the freeing of the memory (respectively) must still wait for a grace period to elapse?

Answer: We could define things this way, but keep in mind that this sort of definition would say that updates in garbage-collected languages cannot complete until the next time the garbage collector runs, which does not seem at all reasonable. The key point is that in most cases, an updater using either call_rcu() or kfree_rcu() can proceed to the next update as soon as it has invoked call_rcu() or kfree_rcu(), without having to wait for a subsequent grace period.

Back to Quick Quiz 13.

Comments (6 posted)

Configuration management with Ansible

Any Linux distribution will come with a set of administration tools built in. These tools may be user-friendly and helpful, but they are, as a general rule, not aimed at an administrator who has a large number of systems to deal with. Patience with graphical administration tools and text editing tends to run out before the administrator runs out of fingers to count systems on. Local customization scripts can help preserve sanity for a little while, but, especially in this era where virtualized systems pop into and out of existence as a matter of course, there comes a point where it is necessary to overlay some sort of configuration-management tool on top of the distribution running on any given machine.

Your editor recently hit that point and decided that it was time to learn about these newfangled configuration tools. Tools like CFEngine (started in 1993) might be relatively new on the scene, but perhaps one might be able to conclude at this point that they are not going away in the near future. It didn't take much research time to come to a few preliminary conclusions.

One of those would be that there are quite a few of these tools now. Available offerings include Ansible, CFEngine, Chef, Puppet, Salt, Vagrant, and numerous others. These projects are all free software, and they all appear to be at least moderately healthy with significant user bases. Free software is said to be an exercise in scratching one's own itches; it seems that quite a few developers have this particular itch and have found the energy to do some scratching.

One also quickly concludes, however, that a fair amount of the itching driving these projects is financial in nature. It is a rare configuration-management project that doesn't have a company behind it just waiting for the opportunity to provide ancillary services. Ansible offers a dashboard add-on and consulting services; CFEngine has an "Enterprise Edition" with a graphical interface and support options; Chef has centralized configuration storage and, yes, a management console, and so on. Configuration-management tools appear to be almost uniformly open-core offerings with proprietary administrative tools and support services layered on top.

These tools also tend toward a high level of complexity. Many of them require multiple daemons running on each managed system and can be quite intimidating to approach. If one is trying to manage a data center with tens of thousands of nodes serving multiple functions and with its own dedicated hydroelectric plant for power, this complexity may prove to be necessary. It may also be useful if one has outsourced the power bill to a cloud provider and instantiates new systems like raindrops. For those with more modest requirements, though, all that complexity seems like overkill.

Your editor, being one of those with relatively modest requirements, shied away from most of the available configuration-management systems. The expected payback just didn't seem to justify the effort required to get to the first stage of learning (which is, of course, configuring a new system to boot and say "hello, world"). But then Ansible came into view, and it seemed like it might merit a further look.

Ansible

It is worth saying from this outset: your editor is not prepared to say that Ansible is the best solution for any particular use case. It is far too early for any such statement. This article, instead, should be seen as a look at one of a number of potentially interesting tools for configuration management.

Ansible got off on the right foot by making it clear that there is no need to install software on the machines to be managed. There are no daemon processes that run on these systems. Instead, everything is run in a "push" mode via SSH from a central server (or, really, from any system that has the Ansible configuration on it). That makes it easy to get started and to build up to a more complex configuration setup.

On the other hand, this mode of operation almost certainly slows things down. Before it can perform any configuration work on a target system, Ansible must push its own software onto that system and go through a "fact-gathering" phase. A long-running daemon on a target will not need to completely familiarize itself with the state of that target for every update, while Ansible does. For relatively small networks, speed is not a problem. For large, complex configurations it might be.

Ansible works with a declarative configuration in the YAML syntax; this configuration is split into one or more "playbooks." "Declarative" means that the configuration file describes the desired state of the target system, rather than a set of steps for getting into that state. So Ansible configuration blocks say things like "ensure that these packages are installed and current," "there should be an account called 'foo'," or "the 'bar' service should be running."

The advantage of this approach is that Ansible can compare the desired and current states of a system and figure out the minimal amount of work to get the system into the desired state. The tool can be run at any time and it will perform whatever tweaks are required while minimizing unnecessary thrashing on the target system. The downside is that it is not always easy to describe the desired state in this fashion.

As an example, consider this little configuration block:

    - name: Disable password logins
      lineinfile: dest=/etc/ssh/sshd_config
        regexp=^PasswordAuthentication
        line="PasswordAuthentication no"
        state=present
      notify:
        - restart sshd

This is essentially a declaration that the sshd_config file on the target system should have the requisite line disabling password logins. It can take a surprising number of tries to get this kind of thing right; without sufficient care, one might look at the sshd_config file one day and find dozens of PasswordAuthentication lines appended to the end. Not that your editor would make any such mistake, of course.

All of the real work in Ansible is done with "modules" that know how to perform a specific configuration task. The list of modules is extensive. Modules exist to manage file permissions, tweak Apache configurations, perform package management, deal with SSH keys, install Python libraries, manage firewall configurations, deploy software from Git repositories, and more. Much of the task of learning Ansible is an exercise in figuring out which is the right module for any specific job.

As can be seen from the snippet above, Ansible configurations can be on the verbose side. That verbosity can help to make configurations relatively easy to read, but it does get tiresome to type after a while. Some of that verbosity can be mitigated at the cost of using some fairly unintuitive looping constructs. For example:

    - name: install packages
      yum:
        name={{ item }}
        state=latest
      with_items:
        - emacs
        - git
        - nethack

This declaration causes Yum to be employed to install the listed packages on the target system(s). It is easy enough to write and understand once one gets used to it, but it feels awkward; it is an attempt to impose a somewhat imperative, loop-like structure onto a language that is supposed to be declarative. The upcoming Ansible 2.0 release adds conditional structures to deal with failures and such; it will increase the flexibility of the language, but the new structures feel awkward in the same way.

The above snippet highlights one other limitation that is not entirely Ansible's fault. Once one has an abstract description of a system's configuration, one might reasonably want to apply it to systems running different distributions — or, indeed, different operating systems altogether. But those other systems are unlikely to be using Yum, so this item fails. One can get around such issues by using different configurations for different operating systems, but that results in a certain amount of repetition.

The good news is that the 2.0 release includes a "package" module that works with Yum, DNF, Apt, opkg, Portage, and Zypper (and probably others as well). The bad news is that it still seems to have some glitches with some package managers. There is also little to be done about the sad fact that the same program is often packaged under different names on different distributions. Fully distribution-independent configurations are a nice idea, but they are not quite a reality yet.

A complete configuration for a given system type can be long; if one follows the suggested best practices, it will also be split into possibly dozens of files in a deep directory hierarchy. For added fun, half of the files will be called main.yml. This organization provides a lot of flexibility and modularity, but, as one is trying to figure out which main.yml needs to be edited to accomplish a particular task, it's hard not to feel that there should be a better way.

The error diagnostics provided by Ansible are, to put it bluntly, poor. There is, for example, no indication of which file contains a particular problem. The 2.0 update improves this situation considerably; the Ansible developers evidently figured out single-line "foo is not a legal parameter in an Ansible task or handler" failure messages were not helping their world-domination goals.

Needless to say, Ansible has lots of features designed to aid the administration of large networks, including variables and templates, a mechanism for combining configuration combinations into "roles," the ability to update many machines in parallel, and so on. There is a set of modules for interfacing with various cloud providers to perform basic orchestration tasks, and others to deal with OpenStack-based clouds. The modules themselves are written in Python and are relatively easy to create or extend.

Ansible is still not in production use here at LWN; there is more messing around to be done before we can reach that point. But it is clear that tools like Ansible have an important role to play in a world where "the server" is no longer a big box named after a Lord of the Rings character, but is, instead, just one of vast numbers of essentially anonymous appliances. It is not surprising that a lot of energy is going into the development of these tools. After all, system administrators have always been big fans of automation; a variety of free configuration-management tools makes it easy for each of them to scratch that itch in the way they think best.

Comments (14 posted)

Distribution quotes of the week

-- Greg Kroah-Hartman

-- Rich Freeman

-- Andy Wingo

-- Matthias Klose (Thanks to David Nielson)

Comments (none posted)

Oracle Linux 6.7 released

Oracle has announced the release of Oracle Linux 6.7. As usual this release features both a Red Hat compatible kernel and Oracle's enterprise kernel. Some notable features include Open Security Content Automation Protocol (OpenSCAP), including the oscap utility for enhanced security auditing and compliance, Load Balancing and High Availability with Keepalived and HAProxy, supported under Oracle Linux Premier Support subscriptions, Enhanced SSSD support for Active Directory, and more. See the release notes for details.

Comments (5 posted)

Announcing the CentOS Linux AltArch SIG

The formation of the CentOS Linux AltArch Special Interest Group has been announced. "This SIG will be setup and managed by community members who want to come and help port CentOS Linux to architectures and platforms not supported by the Core SIG itself."

Full Story (comments: none)

Release for CentOS 7 on AArch64

CentOS Linux 7 for AArch64 has been released. "This is the first major release of CentOS Linux 7 for ARM/AArch64 produced by the AltArch Special Interest Group. This release uses a 3.19 based kernel as well as incorporating fixes and updates provided through-out the beta process. This release is built from sources available at git.centos.org from the c7, c7-ppc64le, and c7-aarch64 branches."

Full Story (comments: none)

Distribution newsletters

• DistroWatch Weekly, Issue 621 (August 3)
• 5 things in Fedora this week (July 31)
• Launchpad news (July)
• openSUSE weekly review (August 5)
• Tails report (June)
• Ubuntu Weekly Newsletter, Issue 428 (August 2)

Comments (none posted)

FreeBSD quarterly report

The FreeBSD quarterly report, for the second quarter of 2015, has been released. "The cluster and release engineering teams continued to improve the structures that support FreeBSD's build, maintenance, and installation. Projects ran the gamut from security and speed improvements to virtualization and storage appliances. New kernel drivers and capabilities were added, while work to make FreeBSD run on various ARM architectures continued at a rapid pace. The Ports Collection grew, even while adding capabilities and fixing problems. Outside projects like pkgsrc have become interested in adding support. Documentation was a major focus, one that is often complimented by people new to FreeBSD. BSDCan 2015 was a great success, turning many hours of sleep deprivation into an even greater amount of inspiration."

Comments (none posted)

Mercurial 3.5

Version 3.5 of the Mercurial revision-control system was released on July 31, bringing with it a handful of interesting new features, such as a new wire protocol and an extensible data-exchange format.

The Mercurial project makes quarterly releases and, like many projects that adhere to a regular schedule, each new release may only usher in a few improvements. But that does not mean that progress has slowed down or that there is waning interest—Git may attract a larger share of the revision-control-system press, but Mercurial is used by some rather large free-software projects, including Mozilla and Python (at least for the present, where Python is concerned).

The 3.5 release debuts a new wire protocol called "bundle2." This is the protocol used to transfer data when doing push, pull, and related operations. Bundle2 was first made available in the 3.4 release, but was only enabled by default for servers—thus allowing for a measure of testing before widespread deployment. The 3.5 release activates bundle2 for clients, too. Furthermore, both the old and new protocols are still supported on the client and server side, so the update will opportunistically use bundle2 when available, but will not leave older systems stranded.

Although the previous protocol served Mercurial well for many releases, it was hampered by some rather striking design limitations. The most prominent was that a separate API call was used for each chunk of data transferred (e.g., each updated file). Thus, neither pushes nor pulls were atomic operations, which led to any number of race conditions and, no doubt, frustrating failure modes. With bundle2, all of the data for a given operation is transferred in one chunk, allowing operations to succeed or fail atomically.

Another user-visible feature of bundle2 is that it supports transferring a repository's cache of tags from the server to the client whenever a client performs a pull or clone. In previous releases, the client would have to recompute the tags which, for large repositories, obviously took unwanted excess time.

Bundle2 also allows Mercurial extensions to support custom additions to the data stream used for each operation. Additional parts (such as metadata) can be inserted into the payload stream for standard push and pull operations—whereas, in previous releases, such additions would need to be transported using separate requests.

Speaking of extensions, the progress extension has been merged into the core codebase and enabled by default. A popular extension in previous releases, it draws progress bars to report on in-progress operations.

A significant functional addition to Mercurial in this release is the "auto share" feature, which was contributed by Mozilla's Gregory Szorc. Auto share allows a developer to clone multiple branches of the same repository and have them automatically share the same backing storage. Mercurial will detect that a new clone operation is using the same remote as an existing one and (if configured to use auto share) pull down only the changesets unique to the new fork. Szorc notes that this feature was designed with automated tools like continuous-integration systems in mind, but that it can significantly reduce disk usage for developers as well.

Among the other changes is the addition of include and subinclude directives for hgignore files. This allows the contents of a directory-specific hgignore file to be referenced by the hgignore file in a parent directory—meaning that the parent directory no longer needs to include an exhaustive list of files to ignore. The result is that directories can be more easily rearranged and automatically preserve hgignore rules.

As one would expect, there are many additional changes in the new release beyond those described here. Work progresses on a number of fronts, such as splitting the content manifests for a repository (which map contents to files) from a single, monolithic manifest-per-repository model to a per-directory model.

Finally, the new release officially drops support for Python 2.4 and 2.5. While there were, no doubt, few users still running each of those releases, dropping them signifies that a cleanup effort is making steady progress—one whose ultimate goals may include adding Python 3 support. Whether that Python 3 support ever arrives remains to be seen, of course.

It can be easy to be accidentally Git-centric in one's views of the free-software community and that community's development trends. The new Mercurial release shows that, despite all of the ups and downs in the revision-control wars, there remains a competitive landscape.

Comments (none posted)

Quote of the week

— Ole Tange presents the results of some covert, real-world research.

Comments (2 posted)

A leadership change at FFmpeg

FFmpeg leader Michael Niedermayer has announced his departure from the project. "I hope my resignation will make it easier for the teams to find back together and avoid a more complete split which would otherwise be the result sooner or later as the trees diverge and merging all improvements becomes too difficult for me to do."

Comments (138 posted)

LibreOffice 5.0 released

The LibreOffice 5.0 release is out. "LibreOffice 5.0 sports a significantly improved user interface, with a better management of the screen space and a cleaner look. In addition, it offers better interoperability with office suites such as Microsoft Office and Apple iWork, thanks to new and improved filters to handle non standard formats." See this post from Michael Meeks for a detailed description of the work that went into this release.

Full Story (comments: 27)

Development newsletters from the past week

• What's cooking in git.git (August 3)
• Git Rev News (August 5)
• LLVM Weekly (August 3)
• OCaml Weekly News (August 4)
• OpenStack Community Weekly Newsletter (July 31)
• Perl Weekly (August 3)
• PostgreSQL Weekly News (August 2)
• Python Weekly (July 30)
• This Week In Rust (August 3)
• Ruby Weekly (July 30)
• Wikimedia Tech News (August 3)

Comments (none posted)

OpenSSL: License Agreements and Changes Are Coming

At the OpenSSL blog, Rich Salz has announced the project's decision to migrate away from the "rather unique and idiosyncratic" OpenSSL license to the Apache 2.0 license. In order to make the change in an upcoming release, though, the project "will soon require almost every contributor to have a signed a Contributor License Agreement (CLA) on file." Individual and corporate versions of the CLA are posted; trivial patches will evidently not trigger the need for the submitter to sign and file an agreement. Salz closes by noting that more details are still to come, since "there is a lot of grunt work needed to clean up the backlog and untangle all the years of work from the time when nobody paid much attention to this sort of detail."

Comments (34 posted)

Mozilla criticizes browser-selection change in Windows

Mozilla has launched a multi-pronged campaign to challenge a recent change in Windows that has the effect of overriding users' choice of Firefox as the default web browser. Mozilla CEO Chris Beard posted a blog entry outlining the problem as well as an open letter to Microsoft CEO Satya Nadella. The change apparently landed with the recent Windows 10 release and, as Beard explains it, "while it is technically possible for people to preserve their previous settings and defaults, the design of the new Windows 10 upgrade experience and user interface does not make this obvious nor easy." Mozilla has also posted tutorials and videos to help users restore Firefox as their default browser.

Comments (28 posted)

Announcing the shutdown of the Ada Initiative

The Ada Initiative has announced that it is shutting down in mid-October. In the four years since it was founded, the organization has accomplished a lot to help create a less hostile environment for women in open technology and open culture. "We are proud of what we accomplished with the support of many thousands of volunteers, sponsors, and donors, and we expect all of our programs to continue on in some form without the Ada Initiative." Essentially, the organization found it hard to find others with the same "experiences, skills, strengths and passions" as co-founders Valerie Aurora and Mary Gardiner when they wanted to change roles within the initiative. "The Ada Initiative will shut down in approximately mid-October after using our remaining funds to complete our current obligations and do the tasks necessary to shut down the organization properly. We have several Ally Skills Workshops booked or in the process of being booked during our remaining months of operation. (We will not be booking additional Ally Skills Workshops through the Ada Initiative, but we will refer clients to other people who are teaching the Ally Skills Workshop.) We will teach Impostor Syndrome training classes in Sydney and Oakland in August, and release the materials under the Creative Commons Attribution Sharealike license. We will do the work to keep the Ada Initiative's web content online and available after the Ada Initiative shuts down."

Full Story (comments: 25)

Coalition Announces New ‘Do Not Track’ Standard for Web Browsing

The Electronic Frontier Foundation (EFF), privacy company Disconnect and a coalition of Internet companies have announced a stronger “Do Not Track” (DNT) setting for Web browsing—"a new policy standard that, coupled with privacy software, will better protect users from sites that try to secretly follow and record their Internet activity, and incentivize advertisers and data collection companies to respect a user’s choice not to be tracked online."

Comments (11 posted)

Mourning Nóirín Plunkett

Here are a couple sad notes from the Ada Initiative and the Apache Software Foundation on the abrupt passing of Nóirín Plunkett. "Nóirín was an Apache httpd contributor, ASF board member, VP and ApacheCon organizer. Nóirín's passionate contributions and warm personality will be sorely missed. Many considered Nóirín a friend and viewed Nóirín's work to improving 'Women in Technology' as a great contribution to this cause."

Comments (none posted)

Free Software Supporter - Issue 88, August 2015

This edition of the Free Software Foundation's newsletter covers the FSF 30th birthday party, fall internships with the FSF, SeaGL, Replicant update, GCC 5.2, a statement on Canonical's updated licensing terms, ProteanOS, and much more.

Full Story (comments: none)

FSFE Newsletter - August 2015

The Free Software Foundation Europe newsletter looks at a reply to EU consultation on copyright, patents, and trade secrets, How to deal with firmware restrictions, European Coordinators Meeting, Matthias Kirschner interview, and several other topics.

Full Story (comments: none)

systemd.conf 2015 Announcement and CfP

The first systemd.conf will take place November 5-7 in Berlin-Kreuzberg, Germany. "At systemd.conf 2015 we will discuss the state and future of the Linux core platform and plumbing. The intended audience of the conference are developers, distribution packagers as well as devops professionals. The conference will consist of presentations as well as an extended hackfest." The call for presentations closes August 31.

Full Story (comments: none)

ELCE 2015 Technical Showcase - Call for demonstrations

There will be a technical showcase during the Embedded Linux Conference Europe, in Dublin, Ireland. The showcase will be on October 6 and the deadline for proposals is September 7.

Full Story (comments: none)

CFP Deadlines: August 6, 2015 to October 5, 2015

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

Deadline	Event Dates	Event	Location
August 7	October 27 October 30	PostgreSQL Conference Europe 2015	Vienna, Austria
August 9	October 8 October 9	GStreamer Conference 2015	Dublin, Ireland
August 10	September 2 September 6	End Summer Camp	Forte Bazzera (VE), Italy
August 10	October 26	Korea Linux Forum	Seoul, South Korea
August 14	November 7 November 9	PyCon Canada 2015	Toronto, Canada
August 16	November 7 November 8	PyCON HK 2015	Hong Kong, Hong Kong
August 17	November 19 November 21	FOSSETCON 2015	Orlando, Florida, USA
August 19	September 16 September 18	X.org Developer Conference 2015	Toronto, Canada
August 24	October 19 October 23	Tcl/Tk Conference	Manassas, VA, USA
August 31	November 21 November 22	PyCon Spain 2015	Valencia, Spain
August 31	October 19 October 22	Perl Dancer Conference 2015	Vienna, Austria
August 31	November 5 November 7	systemd.conf 2015	Berlin, Germany
August 31	October 9	Innovation in the Cloud Conference	San Antonio, TX, USA
August 31	November 10 November 11	Open Compliance Summit	Yokohama, Japan
September 1	October 1 October 2	PyConZA 2015	Johannesburg, South Africa
September 6	October 10	Programistok	Białystok, Poland
September 12	October 10	Poznańska Impreza Wolnego Oprogramowania	Poznań, Poland
September 15	November 9 November 11	PyData NYC 2015	New York, NY, USA
September 15	November 14 November 15	NixOS Conference 2015	Berlin, Germany
September 20	October 26 October 28	Samsung Open Source Conference	Seoul, South Korea
September 21	March 8 March 10	Fluent 2016	San Francisco, CA, USA
September 25	December 5 December 6	openSUSE.Asia Summit	Taipei, Taiwan
September 27	November 9 November 11	KubeCon	San Francisco, CA, USA
September 28	November 14 November 15	PyCon Czech 2015	Brno, Czech Republic
September 30	November 28	Technical Dutch Open Source Event	Eindhoven, The Netherlands
September 30	November 7 November 8	OpenFest 2015	Sofia, Bulgaria
September 30	December 27 December 30	32. Chaos Communication Congress	Hamburg, Germany
October 1	April 4 April 6	Web Audio Conference	Atlanta, GA, USA
October 2	October 29	FOSS4G Belgium 2015	Brussels, Belgium
October 2	December 8 December 9	Node.js Interactive	Portland, OR, USA

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

DebConf15 schedule and featured speakers announced

Debconf15, which will be held in Heidelberg, Germany August 15-23, has announced its schedule as well as four featured speakers: Allison Randal, President, Open Source Initiative and Distinguished Technologist, HP; Peter Eckersly, Chief Computer Scientist, Electronic Frontier Foundation; John Sullivan, Executive Director, Free Software Foundation; and Jon 'maddog' Hall, Executive Director, Linux International. "The DebConf content team is pleased to announce the schedule of DebConf15, the forthcoming Debian Developers Conference. From a total of nearly 100 talk submissions, the team selected 75 talks. Due to the high number of submissions, several talks had to be shortened to 20 minute slots, of which a total of 30 talks have made it to the schedule. In addition, around 50 meetings and discussions (BoFs) have been organized so far, as well as several other events like lightning talk sessions, live demos, a movie screening, a poetry night or stand-up comedy."

Full Story (comments: none)

Events: August 6, 2015 to October 5, 2015

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

Date(s)	Event	Location
August 7 August 9	GNU Tools Cauldron 2015	Prague, Czech Republic
August 7 August 9	GUADEC	Gothenburg, Sweden
August 8 August 14	DebCamp15	Heidelberg, Germany
August 12 August 15	Flock	Rochester, New York, USA
August 13 August 17	Chaos Communication Camp 2015	Mildenberg (Berlin), Germany
August 15 August 16	I2PCon	Toronto, Canada
August 15 August 16	Conference for Open Source Coders, Users, and Promoters	Taipei, Taiwan
August 15 August 22	DebConf15	Heidelberg, Germany
August 16 August 23	LinuxBierWanderung	Wiltz, Luxembourg
August 17 August 19	LinuxCon North America	Seattle, WA, USA
August 19 August 21	Linux Plumbers Conference	Seattle, WA, USA
August 19 August 21	KVM Forum 2015	Seattle, WA, USA
August 20 August 21	Linux Security Summit 2015	Seattle, WA, USA
August 20	Tracing Summit	Seattle, WA, USA
August 20 August 21	MesosCon	Seattle, WA, USA
August 21	Unikernel Users Summit at Texas Linux Fest	San Marcos, TX, USA
August 21	Golang UK Conference	London, UK
August 21 August 22	Texas Linux Fest	San Marcos, TX, USA
August 22 August 23	Free and Open Source Software Conference	Sankt Augustin, Germany
August 22	FOSSCON 2015	Philadelphia, PA, USA
August 28 September 3	ownCloud Contributor Conference	Berlin, Germany
August 29	EmacsConf 2015	San Francisco, CA, USA
September 2 September 6	End Summer Camp	Forte Bazzera (VE), Italy
September 10 September 13	International Conference on Open Source Software Computing 2015	Amman, Jordan
September 10 September 12	FUDcon Cordoba	Córdoba, Argentina
September 11 September 13	vBSDCon 2015	Reston, VA, USA
September 15 September 16	verinice.XP	Berlin, Germany
September 16 September 18	X.org Developer Conference 2015	Toronto, Canada
September 16 September 18	PostgresOpen 2015	Dallas, TX, USA
September 19 September 20	WineConf 2015	Vienna, Austria
September 21 September 23	Octave Conference 2015	Darmstadt, Germany
September 21 September 25	Linaro Connect San Francisco 2015	San Francisco, CA, USA
September 22 September 23	Lustre Administrator and Developer Workshop 2015	Paris, France
September 22 September 24	NGINX Conference	San Francisco, CA, USA
September 23 September 25	LibreOffice Conference	Aarhus, Denmark
September 23 September 25	Surge 2015	National Harbor, MD, USA
September 24	PostgreSQL Session 7	Paris, France
September 25 September 27	PyTexas 2015	College Station, TX, USA
September 28 September 30	OpenMP Conference	Aachen, Germany
September 28 September 30	Nagios World Conference 2015	Saint Paul, MN, USA
September 29 September 30	Open Source Backup Conference 2015	Cologne, Germany
September 30 October 2	Kernel Recipes 2015	Paris, France
October 1 October 2	PyConZA 2015	Johannesburg, South Africa
October 2 October 3	Ohio LinuxFest 2015	Columbus, OH, USA
October 2 October 4	PyCon India 2015	Bangalore, India

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