Hi,

I skipped the public announcements for versions 5 and 6, but here is 7 :)

General description: kmemcheck is a patch to the linux kernel that
detects use of uninitialized memory. It does this by trapping every
read and write to memory that was allocated dynamically (e.g. using
kmalloc()). If a memory address is read that has not previously been
written to, a message is printed to the kernel log.

Changes since v4 (rough list):
- SLUB parts were broken-out into its own file to avoid cluttering the main
   SLUB code.
- A rather lot of cleanups, including removing #ifdefs from arch code.
- Some preparation in anticipation of an x86_64 port.
- Make reporting safer by using a periodic timer to inspect the error queue.
- Fix hang due to page flags changing too early on free().
- Fix hang due to kprobes incompatibility.
- Allow CONFIG_SMP, but limit number of CPUs to 1 at run-time.
- Add kmemcheck=0|1 boot option.
- Add /proc/sys/kernel/kmemcheck for run-time enabling/disabling.


These patches apply to Linus's v2.6.25-rc8. The latest patchset can also be
found here: http://folk.uio.no/vegardno/linux/kmemcheck/

(I will try to submit this for inclusion in 2.6.26, and testing and feedback
is of course very welcome!)

I would like to thank the following people, who provided patches or helped
in various ways:

Ingo Molnar
Paul McKenney
Pekka Enberg
Pekka Paalanen
Peter Zijlstra
Randy Dunlap


Kind regards,
Vegard Nossum
--

(reply to an e-mail of one month ago)

Hello Vegard,

It's a bit late but I finally found out about your announcement of
kmemcheck version 7. Are you familiar with the patch that adds support
to Valgrind for User Mode Linux ? I'm not sure what the best approach
is -- letting the kernel do its own checking like kmemcheck or extend
Valgrind such that it supports UML. Anyway, the techniques applied in
Valgrind may be useful for kmemcheck too, such as the algorithms used
in Valgrind to compress the memory state information.

See also:
http://www.mail-archive.com/user-mode-linux-devel@lists.sourceforge.net/msg05602.html

Bart.
--

It's better to do it with the native kernel so you can "valgrind" all 
the interesting driver code.
--

That's right. This is the paper I was referring to that details how to
minimize the memory consumption when tracking state information:
http://www.valgrind.org/docs/shadow-memory2007.pdf

Bart.
--

Hi!

On Sat, May 10, 2008 at 1:04 PM, Bart Van Assche

Yes, I have learned of it not so long ago, around January or so. I
wanted to stop kmemcheck development back then, but Ingo and Pekka
convinced me that it could still be useful :-)

(The link is http://bitwagon.com/valgrind+uml/index.html)

I guess the main disadvantages of using kmemcheck over valgrind-memcheck are:
 - kmemcheck can only warn eagerly, whereas memcheck will wait until
the uninitialized bits are actually used. This means that kmemcheck
will report many false positives. (We have some workarounds but this
is obviously not perfect.)
 - kmemcheck can only warn for dynamic memory, whereas kmemcheck I
believe will also work for local variables, static variables, etc.

It would be interesting to compare the output of kmemcheck vs. the

Thanks. I have actually seen the paper before, but not read all of it.
From a quick glace, it seems that the optimizations described there
apply to the tracking of individual bits within a byte, but since we
are tracking by byte granularity (as opposed to bit granularity), it
also seems irrelevant to kmemcheck. (I am not saying that it isn't
interesting, however.)

Currently, we are using a full byte for each shadowed byte. Since we
actually only use two bits out of eight, we could save three fourths
compared to what we use today.

However, memory usage doesn't seem to be much of a problem. I actually
think it might be worth saving the CPU cycles that are needed for the
lookups/bit operations (memory is cheap, cycles aren't). How is the
speed of Valgrind+UML, does anybody know? Isn't there a problem that
Valgrind will have to emulate all the userspace programs as well?
That, I believe, would make the Valgrinded system painfully slow to
work with. I have no benchmarks or profiler results to refer to, but
kmemcheck at least boots to full userspace+X and is still quite
usable.


Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was...
[ message continues ]

The speed of Valgrind+UML is the same as the speed of valgrind
on any application.  On a 2GHz box it took about 2.5 minutes
to reach "login:" from a cold boot of UML (includes udev, etc.)
So if normal boot takes 15 seconds, then that's a factor of 10
slowdown: slow for interactivity, yet bearable for checking.
The memory-intensive portions (linear search, pointer chasing,
etc.) can be slower still, but loops that concentrate on
register arithmetic or conditional branching go faster.
There is almost no system wait time: normal device delays (disk,
network) get totally overlapped by CPU usage for grinding :-)

I'd like to have both kmemcheck and valgrind+UML, and use them
differently.  Run kmemcheck all the time on a box or two as
"background trolling" for infrequent cases.  Use valgrind+UML
for interactivity and programmable flexibility when hunting
specific bugs, or when hardware cannot be dedicated.

-- 
John Reiser, jreiser@BitWagon.com
--

No, I think valgrind+uml deliberately lets usermode code run directly on 
the cpu, not under valgrind.  Having the option to run everything under 
Valgrind would be interesting, since it would allow you to trace 
uninitialized values crossing the user-kernel boundary (both ways) 
indicating either usermode or kernel bugs (also user to user via the 
kernel, such as via a pipe).

I've thought about, but not actually implemented, running valgrind as a 
Xen guest, and then running a sub-guest under it, allowing you to run an 
entire virtual machine under Valgrind.  I think people have done vaguely 
similar stuff with qemu.

    J

--

It can be done either way.  Grinding userspace code as well is more
uniform, as there's no need to say "this clone should not be followed,
as it will become a UML process".  On the other hand, not grinding
processes means you don't need to figure out how to get the valgrind
engine into your processes.

			Jeff

-- 
Work email - jdike at linux dot intel dot com
--

One easy way to force valgrind into a process is for load_elf_binary()
in fs/binfmt_elf.c to force a PT_INTERP which loads memcheck via
true user-mode calls, then chains to the original PT_INTERP.

-- 
John Reiser, jreiser@BitWagon.com
--

Keep in mind that a reduction in memory usage may reduce the number of
cache misses, and that the improved caching behavior may outweigh the
extra CPU cycles needed for the bit operations.

Bart.
--

I don't think that's true. valgrind can only detect uninitialized 
local variables in one special case (first use of the stack region).
But as soon as you reuse stack which is pretty common it won't 
be able to detect the next uninitialized use in a stack frame. 

Luckily the compilers do a reasonable job at detecting them at build time.

And static/global variables are never uninitialized in C.

-Andi
--

It tracks changes to the stack pointer, and any memory below it is 
considered uninitialized.  But, yes, if you mean that if you use the 
variable (or slot) once in a function, then again later, it will still 
be considered initialized.  But that's no different from any other memory.

    J
--

But it does not invalidate anything below the stack pointer as soon

What I meant is e.g. 

	f1();
	f2();

both f1 and f2 use the same stack memory, but f2 uses it uninitialized,
then I think valgrind would still think it is initialized in f2 from the
execution of f1. It would only detect such things in f1 (assuming there
were no other users of the stack before that)

In theory it could throw away all stack related uninitizedness on each
SP change, but that would be likely prohibitively expensive and also
it might be hard to know the exact boundaries of the stack.

BTW on running a test program here it doesn't seem to detect any uninitialized
stack frames here with 3.2.3. Test program is http://halobates.de/t10.c 
(should be compiled without optimization) 

-Andi

--

Yeah, as soon as the stack pointer changes, everything below it is 
invalidated (except if the stack-pointer change was actually determined 

No, it won't.  If the stack pointer goes up then down between f1 and f2, 
then f2 will get fresh values.

The big thing Valgrind hasn't traditionally helped with is overruns of 

No, its not all that expensive compared the overall cost of valgrind and 
the amount of diagnostic power it provides.  Determining stack 
boundaries has always been a bit fraught.  Typically a stack switch has 
been determined heuristically by looking for a "large" change in stack 
pointer, but there's a callback to specifically mark a range of memory 
as a stack, so that movements into and out of a stack can be determined 
as a switch (added specifically to deal with small densely packed stacks 

Hm, I'd expect it to.  Oh, your test program doesn't use the value.  
Valgrind doesn't complain about uninitialized values unless they 
actually affect execution (ie, a conditional depends on one, you use it 
as an address for a dereference, or pass it to a syscall).

The attached version emits errors as I'd expect:

$ valgrind t10
==30474== Memcheck, a memory error detector.
==30474== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==30474== Using LibVEX rev 1804, a library for dynamic binary translation.
==30474== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==30474== Using valgrind-3.3.0, a dynamic binary instrumentation framework.
==30474== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==30474== For more details, rerun with: -v
==30474== 
f1 set y to 1
==30474== Conditional jump or move depends on uninitialised value(s)
==30474==    at 0x8048420: test (t10.c:22)
==30474==    by 0x8048451: main (t10.c:29)
==30474== 
==30474== Use of uninitialised value of size 4
==30474==    at 0xB5C5B6: _itoa_word (in /lib/libc-2.8.so)
==30474==    by 0xB5FF90: vfprintf (in /lib/libc-2.8.so)
==30474==    by 0xB6769F: printf (in /l...
[ message continues ]

The valgrind+uml patches added a callback, "I am switching stacks >NOW<."
If possible then it is better to tell an interpreter what is happening,
rather than requiring that the interpreter [try to] figure it out.

-- 
John Reiser, jreiser@BitWagon.com
--

Hm, I never particularly liked that approach because unless you do the 
whole thing in assembly it was never certain that there wasn't a 
basic-block break between them (ie, atomic with respect to valgrind).  
For the kernel that may be possible, but I was thinking of the general 

Matter of taste really, but I tend to disagree.  If you say something 
like "addresses A-B, C-D, E-F are stacks", then the stack pointer 
changing from the range A-B to C-D is a pretty clear indication of stack 
switch, regardless of the mechanism you use to do it.  Of course, an 
explicit hint prevents an accidental push/pop of 32k onto an 8K stack 
from being considered a stack switch, but unless you actually know where 
the stacks are, you can't warn about it or prevent it from 
validating/invalidating a pile of innocent memory.

    J
--

It might in theory, but at least it doesn't for my test program.

-Andi
--

If you'd read a tiny bit further down my mail, you'd have seen my 
explanation of why your test program isn't testing what you think it is, 
and a variant which does.

    J
--

As long as the compiler is not told to optimize the compiled code,
Valgrind's memcheck tool is able to detect uninitialized local
variables. Valgrind a.o. tracks all updates of the stack pointer. If
the stack pointer is increased, the memory range between the old and
the new stack pointer is marked as undefined. This works as long as
gcc doesn't optimize away individual stack pointer updates. (I'm one
of the Valgrind developers.)

Bart.
--

From d3844118edba5548cce8d27a78bb15b8d6aded66 Mon Sep 17 00:00:00 2001
From: Vegard Nossum <vegard.nossum@gmail.com>
Date: Fri, 4 Apr 2008 00:54:48 +0200
Subject: [PATCH] slub: add hooks for kmemcheck

With kmemcheck enabled, SLUB needs to do this:

1. Request twice as much memory as would normally be needed. The bottom half
    of the memory is what the user actually sees and uses; the upper half
    contains the so-called shadow memory, which stores the status of each byte
    in the bottom half, e.g. initialized or uninitialized.
2. Tell kmemcheck which parts of memory that should be marked uninitialized.
    There are actually a few more states, such as "not yet allocated" and
    "recently freed".

If a slab cache is set up using the SLAB_NOTRACK flag, it will never return
memory that can take page faults because of kmemcheck.

If a slab cache is NOT set up using the SLAB_NOTRACK flag, callers can still
request memory with the __GFP_NOTRACK flag. This does not prevent the page
faults from occuring, however, but marks the object in question as being
initialized so that no warnings will ever be produced for this object.

Signed-off-by: Vegard Nossum <vegardno@ifi.uio.no>
Acked-by: Pekka Enberg <penberg@cs.helsinki.fi>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
  include/linux/gfp.h      |    3 +-
  include/linux/slab.h     |    7 +++
  include/linux/slub_def.h |   17 ++++++++
  kernel/fork.c            |   15 ++++---
  mm/Makefile              |    3 +
  mm/slub.c                |   36 ++++++++++++-----
  mm/slub_kmemcheck.c      |   99 ++++++++++++++++++++++++++++++++++++++++++++++
  7 files changed, 161 insertions(+), 19 deletions(-)
  create mode 100644 mm/slub_kmemcheck.c

diff --git a/include/linux/gfp.h b/include/linux/gfp.h
index 164be9d..0faeedc 100644
--- a/include/linux/gfp.h
+++ b/include/linux/gfp.h
@@ -50,8 +50,9 @@ struct vm_area_struct;
  #define __GFP_THISNODE	((__force gfp_t)0x40000u)/* No fallback, no policies */
  #defin...
[ message continues ]

From caf2b1b7198bd4e0d690555be389a3444523162d Mon Sep 17 00:00:00 2001
From: Vegard Nossum <vegard.nossum@gmail.com>
Date: Fri, 4 Apr 2008 00:53:23 +0200
Subject: [PATCH] x86: add hooks for kmemcheck

The hooks that we modify are:
- Page fault handler (to handle kmemcheck faults)
- Debug exception handler (to hide pages after single-stepping
   the instruction that caused the page fault)

Also redefine memset() to use the optimized version if kmemcheck
is enabled.

Signed-off-by: Vegard Nossum <vegardno@ifi.uio.no>
Acked-by: Pekka Enberg <penberg@cs.helsinki.fi>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
  arch/x86/kernel/cpu/common.c |    7 +++++++
  arch/x86/kernel/entry_32.S   |    8 ++++----
  arch/x86/kernel/traps_32.c   |   16 +++++++++++++++-
  arch/x86/mm/fault.c          |   25 +++++++++++++++++++++----
  include/asm-x86/string_32.h  |    8 ++++++++
  5 files changed, 55 insertions(+), 9 deletions(-)

diff --git a/arch/x86/kernel/cpu/common.c b/arch/x86/kernel/cpu/common.c
index a38aafa..040c650 100644
--- a/arch/x86/kernel/cpu/common.c
+++ b/arch/x86/kernel/cpu/common.c
@@ -634,6 +634,13 @@ void __init early_cpu_init(void)
  	nexgen_init_cpu();
  	umc_init_cpu();
  	early_cpu_detect();
+
+#ifdef CONFIG_KMEMCHECK
+	/*
+	 * We need 4K granular PTEs for kmemcheck:
+	 */
+	setup_clear_cpu_cap(X86_FEATURE_PSE);
+#endif
  }

  /* Make sure %fs is initialized properly in idle threads */
diff --git a/arch/x86/kernel/entry_32.S b/arch/x86/kernel/entry_32.S
index 4b87c32..54f477c 100644
--- a/arch/x86/kernel/entry_32.S
+++ b/arch/x86/kernel/entry_32.S
@@ -289,7 +289,7 @@ ENTRY(ia32_sysenter_target)
  	CFI_DEF_CFA esp, 0
  	CFI_REGISTER esp, ebp
  	movl TSS_sysenter_sp0(%esp),%esp
-sysenter_past_esp:
+ENTRY(sysenter_past_esp)
  	/*
  	 * No need to follow this irqs on/off section: the syscall
  	 * disabled irqs and here we enable it straight after entry:
@@ -767,7 +767,7 @@ label:						\
  	CFI_ADJUST_CFA_OFFSET 4;		\
  	CFI_REL...
[ message continues ]

From bb63a1de75a67ecd88c962c2616f0ab4217f27fe Mon Sep 17 00:00:00 2001
From: Vegard Nossum <vegard.nossum@gmail.com>
Date: Fri, 4 Apr 2008 00:51:41 +0200
Subject: [PATCH] kmemcheck: add the kmemcheck core

General description: kmemcheck is a patch to the linux kernel that
detects use of uninitialized memory. It does this by trapping every
read and write to memory that was allocated dynamically (e.g. using
kmalloc()). If a memory address is read that has not previously been
written to, a message is printed to the kernel log.

Signed-off-by: Vegard Nossum <vegardno@ifi.uio.no>
Acked-by: Pekka Enberg <penberg@cs.helsinki.fi>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
  Documentation/kmemcheck.txt  |   93 +++++
  arch/x86/Kconfig.debug       |   47 +++
  arch/x86/kernel/Makefile     |    2 +
  arch/x86/kernel/kmemcheck.c  |  893 ++++++++++++++++++++++++++++++++++++++++++
  include/asm-x86/kmemcheck.h  |   30 ++
  include/asm-x86/pgtable.h    |    4 +-
  include/asm-x86/pgtable_32.h |    6 +
  include/linux/kmemcheck.h    |   27 ++
  include/linux/page-flags.h   |    6 +
  init/main.c                  |    2 +
  kernel/sysctl.c              |   12 +
  11 files changed, 1120 insertions(+), 2 deletions(-)
  create mode 100644 Documentation/kmemcheck.txt
  create mode 100644 arch/x86/kernel/kmemcheck.c
  create mode 100644 include/asm-x86/kmemcheck.h
  create mode 100644 include/linux/kmemcheck.h

diff --git a/Documentation/kmemcheck.txt b/Documentation/kmemcheck.txt
new file mode 100644
index 0000000..9d359d2
--- /dev/null
+++ b/Documentation/kmemcheck.txt
@@ -0,0 +1,93 @@
+Technical description
+=====================
+
+kmemcheck works by marking memory pages non-present. This means that whenever
+somebody attempts to access the page, a page fault is generated. The page
+fault handler notices that the page was in fact only hidden, and so it calls
+on the kmemcheck code to make further investigations.
+
+When the investigations are completed, kme...
[ message continues ]