Julian Seward

Valgrind is 20 years old now! On July 27, 2002 Valgrind 1.0 was released. And the initial commit to the code repository was March 22, 2002. But the real birthday of Valgrind might go back as far as the Norse Mythology. Please come and join us for a celebration of (at least) 20 years of Valgrind. A retrospective of the project and (your) ideas for the next 20 years.

Valgrind's Memcheck tool reports various kinds of errors. One of the most important are those where an if-condition or a memory address uses undefined data. Detecting that reliably on optimized code is challenging, and recent compiler development has made the problem worse.

Two years ago, at FOSDEM 2018, I did a talk describing the techniques Memcheck uses to achieve a very low false positive rate. But by 2018 both GCC and Clang were routinely emitting code with branches on uninitialised data. Surprisingly, there are situations where such code is correct. Unfortunately Memcheck assumes that every conditional branch is important and so emits many complaints when this happens.

The worst thing was, this problem couldn't be solved using the bag of tricks we'd accumulated over Memcheck's decade-plus lifetime. Our options didn't look good. But in early 2019 it became clear how to fix this: enhance Valgrind's trace generation machinery to analyse more than one basic block at a time, and use that to recover the source-level &&-expressions, which can then be instrumented precisely. This talk tells the story.

The implementation (appears to!) work. If all goes well, it will ship in the upcoming 3.16 release.

The ongoing work to improve the accuracy of definedness tracking in the face of newer more aggressively optimizing compilers.

Valgrind's Memcheck tool reports various kinds of errors. One of the most important ones are those where an if-conditions or a memory address uses undefined data. To do this, it tracks the definedness of every bit in the process, and "follows" any undefinedness through arithmetic operations (Add, Sub, Mul, Or, Xor, etc).

This tracking is expensive and so Memcheck makes compromises, trading off exactness for speed. That has worked well for many years. However, as compilers become more aggressive, this works less and less well. In particular, Memcheck now often reports false errors in optimised code from GCC 6, Clang 4, and later versions. This is a problem because one of Memcheck's main strengths is the accuracy of its analyses.

In this talk I'll present my ongoing work to improve accuracy of definedness tracking. I'll mostly talk about various examples involving integer addition and comparisons, and will avoid gory details of Memcheck's internals. I'll also show two problems to which I have no solution.

The talk should be accessible to anyone with some familiarity of basic integer arithmetic (add, sub, and/or/xor, etc) and is curious about how undefinedness "flows" through these operations. If you like maths and proving simple theorems, you might enjoy this talk too -- and we'd like to talk to you!

VEX is the JIT at the core of Valgrind. It unpicks blocks of machine code, hands them off to the tool for instrumentation, recompiles the result, and links the instrumented version into the running image. By using a target independent intermediate representation, it insulates tools from the complexity of the underlying instruction sets.

Back in 2003, when the framework was designed, I never dreamt that it would end up supporting X86, ARM, POWER, MIPS, S390 and TILEGX in both 32- and 64-bit variants. From that perspective VEX has been amazingly successful. But the framework is now showing its age. Recent instruction set features (transactional memory, LoadLinked/StoreConditional, wide vectors) have proven difficult to implement. It supports precise memory exceptions only poorly. And perhaps worst, its simplistic compilation pipeline causes it to generate code that is uncompetitive compared to other frameworks, particularly DynamoRIO and PIN.

In this talk I'll outline VEX's structure, then talk about these problems and what can be done about them. And I'd be particularly interested to hear opinions on how much effort, and for which problem areas, should be invested in upgrading it.

For the audience, some background in compiler internals and assembly code programming would be helpful, but is not essential.

Memcheck is probably the most heavily used tool in the Valgrind suite, checking for invalid addresses, undefined values and memory leaks. In this talk I'll look back at the history of the tool, then I'll look forwards at some of the challenges it faces as the hardware and software ecosystem continue to evolve around it. I'll talk a bit about some of the effects of Memcheck on the C++ ecosystem and how it fits into the big picture of making your big C++ app crash-free and reliable.

This talk is aimed at Valgrind (Memcheck!) users and developers. It should be accessible to C/C++/Fortran developers who have used the tool or are thinking of doing so.

Memcheck's performance is significantly limited by the need for the JIT generated code to call a helper function for every memory access. This talk will describe ongoing work to inline the fast cases of these helpers into the generated code, with the goal of getting a significant speedup.

Valgrind's Memcheck tool performs address checking at the byte level and definedness checking at the bit level. Most of the definedness checking code is generated by Valgrind's JIT (VEX) as in-line code. But address checking is done by calling small C helper functions. That means one function call for each memory access to be checked, which is expensive. And it's wasteful because those checks are actually very simple, so the overhead of the calls is significant.

This talk describes ongoing work to inline the fast paths of such helper functions into the generated code. The fast paths deal with the common case -- naturally aligned addresses and fully defined values -- with all other cases being pushed "off-trace" onto cold paths, possibly with helper calls to C land.

Modifying the until-now simple JIT to support the arbitrary control flow this requires would be a big and complex task. Instead we use a system of machine code templates which allow precise control of branching and register use without significantly complicating the JIT. Making the templates architecture-neutral yet capable of generating good straight-line code is an interesting challenge.

This talk will present the basic algorithm, the metadata compression scheme, and the scheme for collecting both stacks of a race. I'd also like to talk about the relationship between this and "traditional" h-b implementations since both schemes have advantages and disadvantages.

Helgrind, one of the Valgrind tools, provides data race detection using a pure happens-before algorithm. Unlike many happens-before implementations, Helgrind does not detect races by creating address-indexed bitmaps and checking them at inter-thread synchronisation points. Instead, Helgrind maintains, for each byte in the address space, two vector timestamps that specify the constraints for future race-free reads and writes to that location. This presents major difficulties in storing so much information, but also makes it possible to provide exact backtraces for both accesses in a race.

This talk does not cover Helgrind's lock-order checking algorithm. Although also interesting, that is a different piece of functionality.