Valgrind meets UML

After some hacking on valgrind (and help from Jeremy Fitzhardinge and Julian Seward), I got it to run the kernel, in the form of UML.

I don't have a long list of bugs to report because I'm still trying to drive the noise level down by teaching valgrind about how the kernel does business.

As a result, I have some questions that I'd appreciate advice on.

You teach it things by putting declarations in the code about what level of access is permitted for a region of memory. So,

	VALGRIND_MAKE_WRITABLE(ptr, len);
	VALGRIND_MAKE_READABLE(ptr, len);

tells valgrind that the region [ ptr, ptr + len ) is open for business, and

	VALGRIND_MAKE_NOACCESS(ptr, len);

tells it that it's not.

First question - is sticking something (not necessarily the VALGRIND_* things) in the code acceptable? I personally don't see a problem with it, although I would do something like BUFFER_RW(ptr, len), which would expand into the first pair of declarations if CONFIG_VALGRIND was enabled, and nothing if it's not.

Which leads to the next question - where to put CONFIG_VALGRIND? UML is the only form of the kernel which valgrind will deal with any time soon, so it's reasonable for it to be in the UML config only. However, the memory access declarations are going to be sprinkled around generic code, so that suggests putting it in the generic config someplace, just conditional on UML (which suggests putting it back in the UML-only config :-).

I think there would also need to be a CONFIG_VALGRIND_INCLUDE which points to wherever the valgrind headers are installed.

I would also appreciate suggestions on what sort of memory access state table to implement, and where best to put the declarations. What I'm not clear on is what sort of access a buffer should have when it's in the care of the allocator (i.e. it's free). If the allocator sticks information temporarily in the buffer, then that needs to be stated.

There are also some non-obvious places where this could be used.
- VALGRIND_MAKE_READABLE could be used to enforce read-only data when an rwlock is taken for reading
- it could also be used whenever there's an interface that hands out read-only objects, and writing them is done under that interface.

So, it's not only the memory allocators that can make use of this. We'll get the best use of this if other subsystem maintainers figure out what rules they have and whether valgrind can be used to enforce them.

Jeff

Probably there will be some benefits, at least for a while, if valgrind for UML "knows" the kernel allocators like valgrind for applications "knows" malloc+free. Implementors of allocators can have bugs in the valgrind declarations they add. An "independent" check based on documented externally-visible behavior can help.

Nested allocators (inner allocator grabs a large region, outer allocator performs sub-allocations of small pieces from the large region) can be troublesome.

Implementing a four-state status {-, W, RW, RO} might be much more work, because some accounting schemes are oriented naturally towards only three states {-, W, RW}. Also, there are contenders for two additional states: watchpoints for READ and WRITE, such as "any read of a back-pointer of this doubly-linked list", etc.

John Reiser, [email protected]

The problem is that valgrind is going to look under the covers of the kernel allocators and see the externally-visible requirements being violated.

Either you implement a globally correct description, which includes the externally visible description as a subset, or you somehow tell valgrind not to complain about stuff inside the allocator.

The second sounds complicated, and anyway hides bugs in the allocator.

And are another reason for implementing a globally correct description.

Jeff

I suggest that useful partial progress can be made sooner by identifying the allocators, telling valgrind about them and their external semantics, and having valgrind trust them. In particular, do not valgrind allocators at first. Waiting for the globally correct description can take a long time, perhaps about as long as waiting for the authors of device drivers to update to a new device I/O model. Also, the globally correct description is necessarily time
dependent: it changes while the allocator is active, and describing it correctly at that level of detail can be hard, or at least tedious.

Not valgrinding allocators still will reveal plenty of problems. Those will help provide motivation for implementing descriptions that are more detailed, eventually even globally correct at every instant. Then you can turn valgrind loose on the allocators themselves.

John Reiser, [email protected]

This is likely what will happen anyway. It will likely generate noise from inside the allocators until they are described.

This isn't possible without performing surgery on valgrind. It has no idea what's considered an allocator and what's not.

Nonsense. They aren't going to be that complicated, and they don't change very often anyway.

Jeff

It probably won't be the allocators which generate warnings. The main problem will be that newly allocated memory will still be considered initialized by its previous owner. Also, if UML allocates memory using mmap, all memory will be considered to be initialized.

Doing a few base-level allocators first (get_free_page, kmalloc) will find lots of problems, then you can start refining to the more specialized allocators.

J

What I was doing was having kfree and free_pages set the freed object to noaccess. Presumably, that tells valgrind to consider the memory uninitialized.

Presumably, that will also cause errors from inside the allocator if it touches that memory at all before it's allocated again.

Jeff

In order to prevent races between valgrind for UML and kernel allocators which valgrind does not "know", then the VALGRIND_* declarations being added to kernel allocators should allow for expressing the concept "atomically change state in both allocator and valgrind". One example might be
VALGRIND_STORE_AND_UPDATE(ptr, value, n, ranges)
with semantics

	struct vg_update {
		void const *addr;  /* valgrind itself never changes the contents */
		unsigned length;
		enum {vg_na, vg_w, vg_rw, vg_ro} new_state;
	} *ranges;

	valgrind_lock();
	*ptr = value;
	valgrind_update(n, ranges);  /* ranges should not overlap */
	valgrind_unlock();

In general there is a need for such a primitive for each kind of atomic operation performed by an allocator: on x86, anything with an explicit or implicit LOCK prefix (INC, DEC, ADD, SUB, AND, OR, XOR, BTR, BTS, BTC, XADD, XCHG, CMPXCHG are the most likely). Of course, most actual allocators already use an explicit software lock which in some cases can subsume the valgrind lock. But there are lockless allocators; a circular buffer between consumer and producer is the simplest. Also, there are allocators which use a hardware device as part of the lock: UART FIFO, circular buffer with hardware on one side, SCSI command queue, etc.

John Reiser, [email protected]

What are you talking about?

There are no atomicity problems between UML and valgrind.

Jeff

If so, then you are fortunate. But in the abstract, and more importantly in the mind of the maintainer of a lock-free SMP allocator who is trying to allow simultaneous allocation and valgrind of the allocator, then such atomicity problems are real. The VALGRIND_* statements should allow the conscientious and meticulous maintainer to express the correct semantics, even though the current implementation of valgrind for UML might not [have to] take advantage of all of the properties of such a precise description. If nothing else, then such a maintainer will invent his own VALGRIND_* usage to express simultaneous {allocator, valgrind} state transitions precisely.

John Reiser, [email protected]

This is gibberish. You have no idea what you're talking about.

"lock-free SMP"? This is very nearly a self-contradiction. If you'd bother looking at the allocators, guess what you'll see? You'll see locking.

There is no "allowing" simultaneous allocation and valgrind of the allocator.

Bullshit, there are no such atomicity problems.

A maintainer will invent valgrind primitives to express concepts that valgrind doesn't know about?

There are no simultaneous allocator and valgrind state transitions.

You really need to acquire a clue from somewhere.

Jeff

Valgrind doesn't sit on the side and observe the kernel. A better way of viewing it is as a synthetic CPU which does a lot more error checking than a typical CPU. Valgrind itself is running all code, so there is no scope for Valgrind and the kernel to get out of sync. You can view the VALGRIND_* declarations as being extensions to the instruction set.

If UML were "SMP" (ie, multithreaded), then Valgrind would emulate all the CPUs and their concurrency; at most you'd need to use the normal synchronisation mechanisms to control the sequencing of the VALGRIND_* directives with respect to allocators running on other CPUs/in other threads.

On the other hand, if you view the directives that Jeff is proposing as a more general set of directives for any tool to use to instrument the kernel, then you might need to thinking about things in more detail. On the other hand, that smacks of over-design unless there's something which can make immediate use of such hooks now (and therefore guide the design).

Putting the VALGRIND_* hooks (or some thin sugar wrapping) in now in the appropriate places will mark where any further work should be done, so should be enough for now.

J