running UserModeLinux under Valgrind(memcheck)

Patches have been developed which enable UserModeLinux for i686 to run under the memcheck tool of Valgrind on i686. Thus it is possible to check dynamically the memory accesses made by a running Linux kernel against memcheck's model of allowed behavior. This work was supported by Google Inc.

The combined patches are at "alpha" quality. They have memchecked an entire trivial session (boot UML, login, halt), and have identified a couple specific problems in kernel code. The steps necessary to reach "beta" quality (a motivated kernel developer can get useful results) have been outlined and are being pursued.

The goods:
15KB http://bitwagon.com/valgrind+uml/valgrind-3.3.0-2007-12-27.patch.gz
60KB http://bitwagon.com/valgrind+uml/uml-2.6.22.5-2007-12-27.patch.gz

Current status and updates will be maintained on the [coming] web page
http://bitwagon.com/valgrind+uml/index.html

As a convenience for when the official sites are not responding, here are copies of the original unpatched software that is required:

  4MB  http://bitwagon.com/valgrind+uml/valgrind-3.3.0.tar.bz2
 45MB  http://bitwagon.com/valgrind+uml/linux-2.6.22.5.tar.bz2
103MB  http://bitwagon.com/valgrind+uml/FedoraCore5-x86-root_fs.bz2

Approximately 2.5GB of disk space is required to play.

Motivated in part by the difficulty of tracking down the causes of "Conditional jump or move depends on uninitialised data", the patches include a new *optional* mode for memcheck: --complain-asap=yes. In this mode, memcheck issues a complaint immediately for any load from memory that contains uninitialized bits. This gives a very early notice of potential trouble. It also squawks for uninitialized holes in structures or bitfields, conditions which later become ignored or "don't care", certain compiler optimizations for speed, etc. The intent is to reduce the blizzard of "false positive" complaints by using the glibc-audit patches to provide a "quiet" glibc, by making the holes in kernel structures explicit (and filling them), by writing suppressions for known cases, by and further enhancing this new mode of memcheck.

On the UML side, there is a significant technical issue: the semantics of kmalloc+kfree do not match the semantics of malloc+free. The kernel slab allocator caches and re-issues identified objects, which accumulate state and retain it throughout execution, including from kfree to kmalloc. In contrast, a region that is passed to free() loses both its contents and its identity. Also, size is an important parameter to malloc, but is implicit to kmalloc. The initial patches finesse these issues (for instance: by supplying the size as trailing parameter to kmalloc, and by noticing that SLAB_POISON ==> free()), but there will be significant discussion and work in resolving the differences.

John Reiser, [email protected]

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

John Reiser wrote

Hi John,

I applied your patch against a vanilla 3.3.0 and with both gcc 4.2 and a recent gcc 4.3 snapshot I get the following compilation failure on Linux x86-64 (Centos 5)

if gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../coregrind -I.. -I../coregrind/amd64 -I../coregrind/linux -I../coregrind/amd64-linux -I../include -I../VEX/pub -DVG_PLATFORM="\"amd64-linux\"" -DVGA_amd64=1 -DVGO_linux=1 -DVGP_amd64_linux=1
-DVG_LIBDIR="\"/usr/local/valgrind-3.3.0-asap/lib/valgrind"\" -m64
-fomit-frame-pointer -O2 -g -Wmissing-prototypes -Wall -Wshadow -Wpointer-arith -Wstrict-prototypes -Wmissing-declarations -fno-strict-aliasing -Wno-long-long -Wno-pointer-sign -Wdeclaration-after-statement -fno-stack-protector -MT libcoregrind_amd64_linux_a-syswrap-linux.o -MD -MP -MF ".deps/libcoregrind_amd64_linux_a-syswrap-linux.Tpo" -c -o libcoregrind_amd64_linux_a-syswrap-linux.o test -f 'm_syswrap/syswrap-linux.c' || echo './'m_syswrap/syswrap-linux.c; \
then mv -f ".deps/libcoregrind_amd64_linux_a-syswrap-linux.Tpo"
".deps/libcoregrind_amd64_linux_a-syswrap-linux.Po"; else rm -f ".deps/libcoregrind_amd64_linux_a-syswrap-linux.Tpo"; exit 1; fi m_syswrap/syswrap-linux.c: In function ‘vgModuleLocal_do_fork_clone’:
m_syswrap/syswrap-linux.c:338: error: ‘VexGuestArchState’ has no member named ‘guest_EAX’
m_syswrap/syswrap-linux.c:340: error: ‘VexGuestArchState’ has no member named ‘guest_ESP’
m_syswrap/syswrap-linux.c:349: warning: implicit declaration of function ‘letgo_vex_x86_linux’
make[3]: *** [libcoregrind_amd64_linux_a-syswrap-linux.o] Error 1 make[3]: Leaving directory `/tmp/Work/valgrind-3.3.0/coregrind' make[2]: *** [all] Error 2
make[2]: Leaving directory `/tmp/Work/valgrind-3.3.0/coregrind'

This is a very, very cool feature. Any way you can split that patch out from the patchset?

Cheers,

Michael

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Nice!

Did you find anything needing fixing besides the ubd and random drivers reading uninitialized stuff and the random bytes that UML uses to communicate with itself being uninitialized?

I did a quick scan of the UML patch, and didn't see any unexpected fixes there.

Any problem with supporting these sorts of allocation models in valgrind? Not all the world is malloc and free (although maybe 99% is).

Can we pass the allocation size through a valgrind annotation rather than add the parameter to kmem_cache_alloc?

Jeff

Work email - jdike at linux dot intel dot com

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

The web page http://bitwagon.com/valgrind+uml/index.html
now exists with news, history, commentary, scripts, links on getting User Mode Linux for i686 to run under memcheck on i686.

A standalone patch http://bitwagon.com/valgrind+uml/mc_main-asap.patch
to valgrind-3.3.0 implements "--complain-asap=yes" independently of the other changes. See http://bitwagon.com/glibc-audit/glibc-audit.html
about getting a "quiet" glibc.

John Reiser, [email protected]

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

You refer to kmalloc and kfree as keeping object state intact between kfree and kmalloc, thus not being semantically the same as malloc and free. However, this is true of kmem_cache_alloc and kmem_cache_free, not kmalloc and kfree.

Object contents are destroyed between kfree and kmalloc.

As far as kmem_cache_alloc and kmem_cache_free are concerned, would it work to say that they are like malloc and free, except that if there's a constructor, it is always called before kmem_cache_alloc returns?

Jeff

Work email - jdike at linux dot intel dot com

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Jeff Dike responded:

It looks more complicated to me.

When include/linux/slab.h is in view, then I trace
(where indentation indicates logical call [inline, or physical call]):
kmalloc include/linux/slab.h

    __kmalloc   mm/slab.c
      __do_kmalloc  mm/slab.c
        __cache_alloc   mm/slab.c
          __do_cache_alloc   mm/slab.c
            ____cache_alloc   mm/slab.c
              cpu_cache_get   mm/slab.c

When include/linux/slab_def.h is in view, then I trace:
For a size that is constant at compile time [very often the case], then I trace:

kmalloc include/linux/slab_def.h
kmem_cache_alloc mm/slab.c
__cache_alloc mm/slab.c
<<and continues as in first case above>>

If the size is non-constant at compile time, then I trace:

kmalloc include/linux/slab_def.h
__kmalloc mm/slab.c
<<and continues as in first case above>>

My tracking of kfree is much simpler:
kfree mm/slab.c
__cache_free mm/slab.c

The net effect is that the slab allocator always calls __cache_alloc, thus re-using a kfree()d object and its accumulated contents.

The slab allocator is by far the most used case. slub and slob have not yet been used during my explorations, as far as I can tell.

Under DEBUG, then cache_init_objs() in mm/slab.c does not call the ctor if SLAB_POISON. Under no-DEBUG, then cache_init_objs() always calls the ctor. So here is an exception to the proposed rule, and quite different *semantics* for DEBUG versus no-DEBUG. Also, cache_init_objs is not the allocator, but only the initial condition.

Under DEBUG, then cache_alloc_debugcheck_after() in mm/slab.c calls the ctor if SLAB_POISON. Under no-DEBUG, then cache_alloc_debugcheck_after() is a no-op. Again, a difference in *semantics* between DEBUG and no-DEBUG.

Altogether: the slab ctor is called once per object; except if DEBUG and SLAB_POISON, when kfree() is considered to destroy the old object and kmalloc is considered to create a new object (yet the two objects occupy identical address space.) In the case of no-DEBUG slab, then the ctor is never called as a result of calling kmalloc.

So kmalloc+kfree is distinctly different in semantics from malloc+free, at least as implemented by slab, the most common case.

Now, in my patches, I CHANGED the semantics of slab __cache_alloc so that it calls the ctor always, ignoring both no-DEBUG and SLAB_POISON. If there is a ctor, then this makes kmalloc+kfree closer to malloc+free. But if there is no ctor, then things are murky again. Should the result of kmalloc() be marked as if it were returned from malloc() or not? [I.e., are the contents undefined or defined?]
At least some clients act that way (under DEBUG and SLAB_POISON), and in general it would be simpler for memcheck if it were so. The patch acts as if it *is* so:

        VALGRIND_MALLOCLIKE_BLOCK(objp, size, 0, 0);

In particular, the contents are considered to be undefined. [Then the ctor, if it exists, defines some or all.]

Obviously this is open for corrections, debate, and better understanding! I had difficulty understanding what I observed, and still I search ... The existing patches are the result of trial-and-error to find something which could survive for a complete session of boot+login+halt while respecting at least some intent of memcheck. But probably I missed an important point or two. In particular, I'm confused by allocations which return a "page": either "struct page *", or a "char *" with an aligned group of char of size PAGE_SIZE in the virtual address space. Help?

John Reiser, [email protected]

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

You're paying way too much attention to the implementation.

The rules are simple:
1 - kmalloc and kfree and just like malloc and free - an object's
contents are destroyed between kfree and kmalloc
2 - kmem_cache_alloc and kmem_cache_free are just like malloc and
free, except that an object may come out of kmem_cache_alloc partially initialized

There is another requirement on kmem_cache_free - that an object be passed in in the same initialization state as the constructor would create. You can interpret this as state being preserved between kmem_cache_free and kmem_cache_alloc, which is how it is actually implemented, or as the constructor always being called before kmem_cache_alloc returns. The second makes it look more like malloc and free.

Yes, kmalloc implements its size buckets as kmem_cache_alloc slabs. So what? If you look at /proc/slabinfo, the size-n slabs you see belong to kmalloc. But that's an implementation detail that has nothing to do with the contract you make when calling kmalloc.

Right now, it's configurable, and the default configuration uses slab.

No, there is no semantic difference here, only a difference in when the objects are constructed depending on slab poisoning. When poisoning is in effect, the objects are constructed as late as possible. When it's not, they are contructed earlier.

No, these two supposed semantics differences combine to make no semantic difference.

The kmalloc slabs have no constructor, so of course no constructor is called as a result of calling kmalloc.

No, they are identical.

__cache_alloc is an implementation detail - you don't describe it to valgrind any more that you would describe some internal malloc function. You need to describe kmalloc/kfree and kmem_cache_alloc/kmem_cache_free, which are both fairly close (kmalloc/kfree being identical) to malloc/free.

Undefined.

Examples? I don't know what exactly you're referring to, nor what the problem is.

Jeff

Work email - jdike at linux dot intel dot com

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

I think he means how to handle the following from include/linux/gfp.h in valgrind:

    struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);
    unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);

    void __free_pages(struct page *page, unsigned int order);
    void free_pages(unsigned long addr, unsigned int order);

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Oh yeah, good point.

The unsigned long ones are easy - they are addresses disguised as numbers.

You have to tell valgrind somehow that the object size is

	(1 << order) * PAGE_SIZE

About the struct page ones - I see two possibilities.

1 - You communicate to valgrind somehow that there is a mapping between the page struct and the virtual address it represents. There is a is no page_to_virt (although there is a virt_to_page), but one would be easy to add. For UML, it amounts to
uml_physmem + (page - mem_map) * PAGE_SIZE

2 - You can insist that UML defines WANT_PAGE_VIRTUAL which, if I'm reading the code correctly, will set page->virtual to the address represented by the page. Valgrind then somehow has to know how to reach into the page struct and get the address.

Jeff

Work email - jdike at linux dot intel dot com

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel