Merging lock elision into glibc

Glibc, the GNU C library, is a foundational free software project, and one that has served its important role for well over two decades. Recently, though, it has undergone a shift in its development model, with an increase in contributions from volunteers outside of the core team of committers. That sort of change can bring about strife, but it can also inspire important new features. The latter is certainly true—and the former might also be true—with the case of lock elision, which is set to be included for the first time in the just-frozen 2.18 branch. 2.18 will enable developers to test the glibc implementation of lock elision for some lock types but not others—primarily since there is not full consensus within the project on how to enable such experimental new features.

Lock elision, in general, is a technique for speeding up multi-threaded programs that may contend for the same lock. As more and more cores become available, synchronization between threads becomes increasingly expensive. One way to avoid the synchronization overhead is to use transactional memory instead. A memory transaction buffers all of the possible results of an operation; in the common case where nothing interrupts the operation, the transaction is committed, but if something does interfere, the transaction can be rolled back atomically.

For locks, this means that multiple threads can acquire locks on the same object, and if they are modifying different parts of the object, both transactions ought to succeed. For example, one thread can acquire a lock on an object (say, tablefoo), update the row it is interested in (tablefoo(N)), then release the lock. Meanwhile, a different thread can also acquire a lock on tablefoo for the purpose of updating tablefoo(M). Using memory transactions, both threads can afford to be conservative about locking the whole object, but cavalier about updating the part of the object they need—most of the time, both transactions will go through; only when both threads try to update tablefoo(N) is there a collision, at which point one transaction must be rolled back.

But the real trick is that, in this common case where the two threads do not collide, the locks themselves are unnecessary. If the program is smart enough to recognize this, acquiring and releasing the locks can simply be skipped. This is lock elision. Unfortunately, up until recently, real-world implementations of transactional memory (almost always in software) have been too slow to offer a real advantage over manipulating the locks in the traditional manner. That changed, however, with the debut of Intel's Transactional Synchronization Extension (TSX), a hardware implementation of transactional memory for the Haswell generation of CPUs. Consequently, building TSX support into the lock implementations of common libraries would allow existing programs to take advantage of lock elision speed-ups without even recompiling.

Intel's Andi Kleen has been working on a TSX-based lock elision implementation for glibc, which he wrote about back in January 2013. The 14-part patch set has been through many iterations, but in late June the deadline was fast approaching for the glibc 2.18 freeze, and the status of the patches was still a matter of debate.

The patch set adds elision capabilities to both POSIX thread (pthread) mutexes and read/write locks (rwlocks), and uses an adaptive algorithm to decide when to elide locks in a given code path. Essentially, the algorithm keeps track of whether each mutex succeeds at eliding a lock, and if it fails, elision is suspended for a period of time. Not all lock variants are supported; in particular, locks are never elided for recursive mutexes. Elision is automatically attempted when the CPU supports transactional memory, but developers can also explicitly enable or disable it in their code. Kleen's patch set also offers two environment variables, GLIBC_PTHREAD_MUTEX and GLIBC_PTHREAD_RWLOCK, which users can use to explicitly enable or disable each flavor of elision when starting a program.

Lock down?

The general consensus on the libc-alpha mailing list was that the mutex patches (patches 1 through 5, plus 7) were ready for inclusion. However, there was less agreement on the other patches, for three reasons. First, the glibc team was wary of the rwlock patches due to a disagreement over how to interpret the POSIX standard. According to the standard, a "normal" (i.e., non-recursive, non-errorcheck, non-timed) mutex is required to deadlock if the owner of the lock attempts to re-lock it while already holding the lock. However, if the lock in question is elided, this required deadlock does not occur. It is certainly debatable whether or not avoiding a deadlock is really a bad thing (after all, deadlocks are bugs), but the glibc project decided to follow the standard to the letter, and elide only non-"normal" mutexes.

But what is not clear from the specification is whether or not the same behavior is required for rwlocks. Carlos O'Donell has contacted the Austin Group to ask for clarification; if the official answer is that rwlocks are required to deadlock on re-locks, then the rwlock patches for glibc will not be merged as-is.

Second, the definition of "normal" for mutexes is not a simple affair. The POSIX standard in fact requires specific behavior of "normal" mutexes (such as the deadlock-on-re-lock behavior mentioned above). But the standard also allows for a different type of mutex termed "default" mutexes, in which the implementation is allowed more freedom of behavior. In previous versions of glibc, PTHREAD_MUTEX_NORMAL and PTHREAD_MUTEX_DEFAULT were defined to be identical. Kleen's patch set splits them, in order to allow "default" mutexes to be elided. Technically, not deadlocking on re-lock would violate the standard, even though not deadlocking because the lock had been elided would often be seen as a preferable outcome. But splitting PTHREAD_MUTEX_NORMAL and PTHREAD_MUTEX_DEFAULT could be seen as an ABI change, and, even though it would not affect old binaries, several in the project (such as Roland McGrath) felt that more consideration is needed before making the split, since it would be difficult to reverse after the fact.

Finally, there was also a lack of consensus about whether or not environment variables are ultimately the most appropriate mechanism with which to tune optional runtime features like lock elision. In addition to the coarse-grained enable-or-disable-elision functionality of the new environment variables, Kleen's patch set also adds several parameters that can be used to tune the behavior of the adaptive algorithm. Some would prefer adding a "tunables" API, while others see no problem with adding new environment variables under a well-known namespace (namely, GLIBC_) as long as there is sufficient discussion. Plus, since the elision algorithm is brand-spanking-new, with little or no testing outside of the confines of the glibc project, it is still possible that the algorithm itself could undergo a major overhaul before it is ready for real-world use. Offering tunable parameters is one way for real-world tests to help refine the algorithm, but if users become dependent on the specifics exposed, swapping in a different algorithm later becomes trickier.

Testing is a related matter, albeit one not currently holding up inclusion of the lock elision patch set. IBM's Dominik Vogt has been testing the patch set on the company's System z platform, which is the only other widely available processor architecture to offer its own implementation of hardware transactional memory. So far, his tests have produced as many questions as answers (in part because he is still working his way through the internal processes required to publicly release the test suite as free software). But in the long term, providing a test suite is a vital step for the project—doubtless in coming years there will be more processor architectures to add their own implementations of transactional memory.

Friends of the library

O'Donell declared glibc frozen for 2.18 on July 2, after Kleen checked in the approved mutex patches. As of press time, the project was still waiting to hear back from the Austin Group for clarification on the rwlock deadlock-on-re-lock question, and it appears that decisions on the normal/default split, tunables, and other patches may get deferred until later. O'Donell has assembled the contributor input on the tunables question in a page on the project's wiki. That discussion is expected to take longer than anyone wishes to keep glibc 2.18 in freeze.

Apart from the technical details of adding lock elision, Kleen's work to add the feature to glibc can be seen as a case study of the project's new, consensus-driven development style. For many years, development was overseen by Ulrich Drepper, who earned a reputation as a prickly gatekeeper past whom few outside contributions ever made it to land in the codebase. Other longtime project members (including McGrath) formed a "steering committee" to try and work around the practical problems that arose from Drepper's management style. But Drepper left the project in 2010, and in March 2012, McGrath announced that the steering committee had voluntarily dissolved, to make way for a more open, community-driven model.

Kleen's lock elision patch set, coming as it does largely from outside, is proof that the hard-to-persuade gatekeeper model is indeed gone. In practice, the glibc community arrived at rough consensus on the patch set in a series of epic-length list threads, and it could certainly be argued that the eventual consensus was incomplete. In fact, O'Donell was even a bit apologetic toward Kleen about how difficult the process had been, encouraging him to stick around and continue to contribute. Or, as he put it in a separate message, "We haven't merged something of this complexity in a long time. Please bear with us as we get better with the process."

But, ultimately, at least part of the mutex lock elision implementation has been merged, which might not have happened at all if one project manager were to have made the call in isolation. The consensus model still defers greatly to the experienced contributors (like McGrath), but that is certainly appropriate. In the end, patches were merged, with more or less full agreement, and the remaining issues are largely debates about the long term impact of the implementation—not vehement opposition.