Project Suggestions

This page gives a list of Valgrind projects that people might like to try. They range from quite easy hacking projects to research-level problems. If you plan to try one of these projects, you should subscribe to valgrind-developers list, and also write to it to let us know you are doing the project (just in case someone else is working on it), and you can ask questions there also.

Please note that we are very conservative about adding new features. Only features that are useful to many users, and that do not adversely affect the maintainability or correctness of the code base in adverse ways are likely to be accepted. If you want to implement a feature not mentioned on the following list, please ask on the valgrind-developers list if it is likely to be incorporated before starting.

Also, please understand that there is no guarantee that code you write will be incorporated into Valgrind. It depends on a number of factors: how well written it is, how important are the issues it addresses, how does it affect the code base's structure, and so on. Such is the nature of all free software projects. However, if you consistently submit high quality patches, you may be granted write access to the repository. This is how most of the current developers got involved with Valgrind.

Documentation

Using Valgrind in an Automated Test Suite

Various people have managed to set up an automated test suite that uses Memcheck, and automatically reports if Memcheck finds any errors. This usually relies on the VALGRIND_COUNT_ERRORS client request, but it is not totally straightforward. It would be great to have a section in the manual that describes how to do this well. This would be best written by someone who has actually set up such a test suite.

Software Infrastructure

Improving the Performance Testing Suite

We have a growing suite of performance benchmarks in the perf/ directory, which would benefit from more programs. We have a mix of two kinds of programs:

1. Real programs. Ones like the SPEC2000 benchmarks would be ideal, but they are not free.

2. Artificial programs that stress performance-critical subsystems. For example bug report #105039 has an example program that does many malloc and free calls, and has many heap blocks live at one time. This exposed a performance bug in Valgrind's heap allocator.

The programs should be fairly small (preferably a few thousand lines at most). Any new programs added should add something to the suite that the current programs don't provide. Programs showing performance bugs (ie. cases where Valgrind does very badly) are particularly welcome. (Added August 27, 2005; updated December 15, 2005)

Performance regression testing

We currently have some scripts to run the regression tests nightly on a range of machines. This is very useful for spotting correctness regressions. Equally useful would be an automated system for spotting performance regressions (or improvements).

It would be nice to have scripts to run the performance benchmarks every night. The nightly measurements should be kept and ideally there would be a system for producing graphs that show the performance changes over time. You'd have to specify somehow where the previous measurements would be stored, perhaps that would be a command line argument to the script.

The scripts in nightly/ for doing the nightly regression tests would be the right place to start on this. (Added August 27, 2005; updated December 15, 2005)

Regression test brittleness

Valgrind's regression test suite (run with "make regtest") is extremely useful. The scripts in nightly/ are used on various test machines to determine if regressions are introduced. Unfortunately, some of the tests are too brittle -- they fail on some machines because of slight configuration differences. On the eight test machines we use, we see up to about 10 or 15 failures that should not happen due to these differences.

Improving things will require either additional expected output files (the *.stderr.exp* and *.stdout.exp* files in the tests/ directories), or more clever output filters (the filters have names like filter_stderr). If you attempt to improve the filters, you should be careful not to remove so much information that the test becomes weaker. (Added August 27, 2005)

Regression test gaps

The regression tests are great, but they have some gaps. For example:

• The test memcheck/tests/x86/scalar.c is a very thorough test for Memcheck's checking of system call arguments. We would like similar tests for the other platforms (AMD64, PPC32).

• Memcheck and Nulgrind (aka "none") have a good number of tests each. The other tools have very few. Adding more salient tests would be useful.

Fixing these gaps is not very hard, just tedious. (Added August 27, 2005; updated November 15, 2005)

Unit regression tests

The regression tests are good system-level tests, but we have almost no unit testing, which is bad. We would like to pull out individual Valgrind modules into test harnesses. These can then be tested like normal programs, using normal testing tools, such as gcov (for test coverage) and Valgrind itself.

The test memcheck/tests/oset_test.c is one unit test we have. It tests the m_oset module. It uses some preprocessing hacks to replace calls to Valgrind-internal functions with calls to the standard versions, eg. calling printf() instead of VG_(printf)(). memcheck/tests/vgtest_ume.c is another one, although it has some oddities that make it not such a good example.

(Note that when this test runs, the Valgrind built in the tree is actually running and testing part of its own code! Which is quirky but fine in practice.)

Some modules will be more amenable to this approach than others; the fewer other modules a module depends on, the easier it is. m_oset is a case in point, as it only imports 5 pub_core_* header files. Other files in coregrind/ that would be good candidates include:

• m_debuglog.c
• m_execontext.c
• m_hashtable.c (the test would be very similar to m_oset.c's),
• m_libc{assert,base,file,mman,print,proc,signal}.c
• m_mallocfree.c (a test for this would be particularly helpful)
• m_stacktrace.c
• m_syscall.c

The following would be more challenging, but perhaps still doable:

• m_stacks.c
• m_translate.c
• m_transtab.c
• m_ume.c (maybe use vgtest_ume.c as a starting point, but beware that this file will change signficantly soon)

As well as redirecting Valgrind-internal functions to glibc equivalents, stubs for various functions would need to be written for many of these, as is standard for unit tests.

The coverage (as measured by gcov) should be as high as possible. The coverage for m_oset.c's test is over 99%.

Just fitting these tests into the existing regression test framework means that they will only be run under Valgrind. It might also be worthwhile to introduce a new type of regression test that should also be run natively; this native run could use gcov to determine the test coverage. (Added August 27, 2005)

Coding

Bug fixes

Bug fixes are always welcome. Please consult the Bugzilla page for the current bug list. Bear in mind that choosing the right bugs to fix is an art, and it may be worth consulting the developers list before throwing a lot of effort at fixing something very obscure. Patches should be submitted to the relevant Bugzilla page. (Added August 27, 2005)

Improving Performance

Everyone wants Valgrind tools to be faster. Contributions that improve performance are welcome, but they are hard to find. Now that Valgrind can self-host, you can use Cachegrind to profile Valgrind tools, which is a good starting point. (We don't know of any other freely available tools which can profile Valgrind tools.)

Supporting custom allocators

Valgrind has two client requests, VALGRIND_MALLOCLIKE_BLOCK and VALGRIND_FREELIKE_BLOCK that are intended to support custom allocators. But they don't work very well. In particular, if you try to hand out pieces of memory that came from a malloc() call, they don't work. You could write new requests (give them different names) that avoid these problems. You should test it with one or more real custom allocators to make sure it suffices; the problems with the existing requests stem from the fact that they weren't tested in this way. The *MEMPOOL* client requests are there for pool-based custom allocators. Looking at them may be instructive. This is a fairly straightforward project. (Added August 27, 2005)

New tool: resource alloc/dealloc checker

Memcheck detects memory leaks and file descriptor leaks. There are other resource allocators that have alloc/dealloc functions. Some examples: malloc/free, fopen/fclose, open/close, XOpenDisplay/XCloseDisplay, etc. It would be nice to check them for leaks in an extensible fashion.

The tool would have a configuration file where you name the alloc/dealloc function pairs. Those examples all follow the following pattern in their type signatures:
token alloc(...)
... dealloc(token t)
You'd need a way to handle cases where alloc() fails (eg. open() returns -1). You might also need to handle some slight variations on the above (eg. an extra arg to the dealloc function). You'd implement it in Valgrind using function wrapping to know when the alloc/dealloc functions are called. (Added March 30, 2007; idea from Brant Gurganus)

Incremental debug info reading

When a code segment is loaded Valgrind mmaps the entire file into memory and reads the debug info all in one hit. If the code segment is big (eg. 300MB) the mmap will fail and no debug info will be read for that segment. It would be nice if the debug info reader was more incremental. This project will require an understanding of ELF formats, and to a lesser extent, debugging formats (DWARF, stabs). The place to start looking is m_debuginfo/symtab.c, in the function VG_(read_seg_symbols)(). That code is not very pretty, and could do with a clean-up anyway. (Added September 13, 2005)

Preserving debugging information

Currently, Valgrind unloads debugging information for shared objects when they are unloaded with dlclose(). If the shared object has a memory leak, the stack trace for Memcheck's error message at termination will be missing entries, which makes fixing the leak difficult. This is described in bug report #79362.

One way to fix this would be to change things so that Valgrind records source-level information for stack traces, rather than code addresses. It is not entirely clear how to do this in a way that avoids unnecessary debug information lookups, and nor how to avoid increasing the amount of memory used. An implementation would help clarify the problem and show if this approach is feasible. This project is of intermediate difficulty. (Added August 27, 2005)

Ports to new platforms

If you are interested in porting Valgrind to a new platform, please read porting priorities statement. Note that porting is a big task and requires a great deal of knowledge about the targeted operating system and architecture. (Added August 27, 2005)

Research

Memcheck V-bit verification

Nobody has ever properly tested how reliably Memcheck tracks definedness (V bits) through complicated integer operations, nor whether all shadow memory load/store operations work right when you take into account all permutations of operation size, alignment and endianness. It would be useful to have a more formal idea of the properties of the scheme. (An interesting case: there are two forms of V bit computation for addition, an exact one that Memcheck uses in certain crucial cases, and an approximation one that is used most of the time.)

Cryptographic algorithms -- which do a lot of bit twiddling and have very long chains of dependent computations -- might be a good starting point (you could run a crypto algorithm with completely defined input, then run it gain with one undefined bit in the input, etc). The Memcheck USENIX paper describes Memcheck's operations in some detail. This could be a relatively easy, yet interesting, starter project, suitable for an advanced project for an undergraduate student. (Added August 27, 2005)

Characterising the kernel interface

The interface between Valgrind and the OS kernel is complex and important. System calls, signals, threads and memory layout are all involved. A document that carefully described all the interactions would be very useful, and might lead to improvements in the implementation. This would not be easy, but would be a great way to learn about OS kernels and Valgrind's internals. (Added August 27, 2005.)

Cryptographic snooping

Since a Valgrind tool can see every operation performed by a program, it is conceivable that a tool might be able to analyse some kind of cryptographic program as it runs to extract certain secret information, such as a key. This may not be true at all, but it's an intriguing thought. Assuming there is some truth to it, this might make a good research project for an honours undergraduate or Masters student, and could well be publishable if done well. (Added August 27, 2005)

Detecting dangerous floating point inaccuracies

Floating point arithmetic is difficult to get right. It is easy to write programs whose outcome depend on incorrect assumptions about levels of precision. One could imagine a tool that tracks this precision somehow, eg. by tracking each floating point value with a plus/minus, and then complains if the program does an operation that relies on more precision than is present.

The exact details of how this would work remain unclear. It would require a good knowledge of how floating point arithmetic works. Also, Vex only provides 64-bit floating point accuracy, when x86 machines provide 80-bit floating point values; this would complicate things further.

This is a challenging project that might be suitable for part of a Masters or PhD project. It would definitely be publishable if done well. (Added August 27, 2005)

A better memory profiler

Many memory profilers exist that can tell you how much memory your program uses; the Valgrind tool Massif is one example. Other profilers can tell you about the cache utilisation of a program; Cachegrind is an example.

What other kinds of information about memory use might be useful? How else does memory use affect program performance? Perhaps measuring memory bandwidth use in some way would be useful -- does the program access memory in an even fashion, or is it bursty? When one part of a program writes values in memory and another part reads them, that area of memory can be thought of as a communication channel between the two fragments of code. Is it possible to construct a tool which measures these through-memory communication rates between parts of a program?

Can a tool identify inefficient uses of memory, such as copying values around unnecessarily? Perhaps a tool that measures page faults and helps programmers avoid them would be useful.

The first step is to identify what information a programmer would like to know to improve a program's memory usage. This is harder than it sounds. Analysing large programs that use memory intensively would be a good starting point. The next step is to work out how a tool can provide this information, or a good approximation of it, reasonably efficiently.

This is all quite speculative, but I think there is a new kind of memory profiler waiting to be invented, and Valgrind would provide an excellent platform for developing it. These questions could form part of a Masters or PhD project. It would certainly be publishable if done well. (Added August 27, 2005)