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
Jeff Dike wrote:
> 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.
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]
[email protected] said:
> Implementors of allocators can have bugs in the valgrind declarations
> they add. An "independent" check based on documented
> externally-visible behavior can help.
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.
> Nested allocators (inner allocator grabs a large region, outer
> allocator performs sub-allocations of small pieces from the large
> region) can be troublesome.
And are another reason for implementing a globally correct description.
Jeff
Jeff Dike wrote:
> [email protected] said:
>
>>Implementors of allocators can have bugs in the valgrind declarations
>>they add. An "independent" check based on documented
>>externally-visible behavior can help.
>
>
> 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.
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]
[email protected] said:
> 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.
This is likely what will happen anyway. It will likely generate noise
from inside the allocators until they are described.
> In particular, do
> not valgrind allocators at first.
This isn't possible without performing surgery on valgrind. It has no idea
what's considered an allocator and what's not.
> 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.
Nonsense. They aren't going to be that complicated, and they don't change
very often anyway.
Jeff
On Fri, 2002-12-20 at 18:49, Jeff Dike wrote:
> [email protected] said:
> > 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.
>
> This is likely what will happen anyway. It will likely generate noise
> from inside the allocators until they are described.
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.
> > 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.
>
> Nonsense. They aren't going to be that complicated, and they don't change
> very often anyway.
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
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]
[email protected] said:
> 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".
What are you talking about?
There are no atomicity problems between UML and valgrind.
Jeff
[email protected] said:
> 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.
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
Jeff Dike wrote:
> [email protected] said:
>
>>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".
>
>
> What are you talking about?
>
> There are no atomicity problems between UML and valgrind.
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.
[email protected] said:
> But in the abstract, and more importantly in the mind of the
> maintainer of a lock-free SMP allocator
"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.
> who is trying to allow
> simultaneous allocation and valgrind of the allocator,
There is no "allowing" simultaneous allocation and valgrind of the allocator.
> then such atomicity problems are real.
Bullshit, there are no such atomicity problems.
> If nothing else, then such a maintainer will invent his own VALGRIND_*
> usage to express simultaneous {allocator, valgrind} state transitions
> precisely.
A maintainer will invent valgrind primitives to express concepts that valgrind
doesn't know about?
> to express simultaneous {allocator, valgrind} state transitions
> precisely.
There are no simultaneous allocator and valgrind state transitions.
You really need to acquire a clue from somewhere.
Jeff
On Sat, 2002-12-21 at 06:40, John Reiser wrote:
> 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".
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