kmemcheck in mainline

First of all, I should say that on April 22, I went to Denmark to give a talk on kmemcheck. I was invited to DIKU (Datalogisk Institut på Københavns Universitet) by Julia Lawall, who held a workshop on Coccinelle (or, more generally, "finding bugs in operating system software"). It was really nice to be there, not (just) because I got a chance to talk about kmemcheck, but because I learned so much from all the other talks! Feel free to check out my slides.

I had asked my university (the University of Oslo) beforehand to sponsor the trip in exchange for a trip report, but I got no reply to my e-mail. I guess they don't see any value in collaboration with universities abroad.

And now, for the news: Yesterday, kmemcheck was merged in mainline Linux! It is quite an incredible feeling after having spent so much time to make it work properly... (Not to mention the rebase marathon that ensued after Linus initially rejected it)

I had also asked Redpill Linpro (a Norwegian/Swedish open source developer) beforehand to sponsor my work on kmemcheck for the summer, but they apparently weren't interested. At least I got a polite reply. (Instead, I got a stipend from Google for working on Jato for the summer, but more on that in a later post!)

REP STOS -- part 2

I finally did it.

I fixed the problem with single-stepping REP STOS (and MOVS) instructions on the P4. (Look in the blog archive to find the original post.)

At first, I wanted emulate the instructions completely. But it wasn't really that easy. My naïve implementation did support different register/data widths. But I soon hit some real show-stoppers. It turned out that the kernel will use REP STOS or MOVS on strings which may not be aligned naturally. This means that memory accesses may now cross a page boundary, which is a big problem. Now we suddenly have to look for page boundaries, and in the case of REP MOVS, we must watch out for both the ESI and EDI registers.

The reason is of course that pages are tracked one by one, and if we cross over to a new page, we have to make sure that it is also marked present (P flag) in the page tables before touching it. Two consecutive pages are also not guaranteed to have consecutive shadow-memory pages (in fact, that's very unlikely), so we should also take care of changing shadow-memory pointers upon hitting a page boundary. But still, that is not so easy when we have a single write that can cross the boundary.

I thought about this for a long while and I came up with a scheme that would work: We can allow a REP MOVS/STOS run to cross at most one page boundary. Then we only need to keep track of at most two pages at the same time (or four pages for REP MOVS), and if we hit this limit, then we can return to the code and simply wait for a new page fault to restart where we left off.

But still it was not quite that easy. Emulating the memory accesses in effect means that we do them from the page fault handler. The kernel got through the boot sequence and a bit into userspace. But then it would BUG on a test that wanted irqs to be enabled. After a bit of debugging, I found (to my great horror) that copy_to_user() was using REP MOVS to move data from the kernel into userspace. This is of course not safe, when we consider that the userspace page might not even be present in the page tables. Because now we were making a write from the kernel (in fact, from the page fault handler itself) to userspace, causing a new page fault, and then calling into various memory subsystem functions to allocate a new page for userspace. All of this with interrupts disabled, which is forbidden. (I believe that this is also the reason why copy_to_user() cannot be used in atomic contexts. Who can confirm?)

We absolutely cannot emulate the instruction by doing the write from the page fault handler. So what can we do?

Well, all is not lost. I am rather proud of my little hack, too. This is what I wrote (in my great excitement) to Ingo Molnar:

Instead of emulating the _whole_ REP MOVS/STOS, we only emulate the REP part. That is, on #PF, we increment %eip by one, which means that when the #PF returns, it will execute just a normal MOVS/STOS instruction (and give is the #DB straight afterwards). Now, in the #DB, we check the flag that says "was this really a REP instruction?" and if it was, we start counting down %ecx and rewinding %eip each time until %ecx is 0. Each time we return to the original instruction and let the CPU execute it natively. When %ecx is 0, we turn off single-stepping and hide the pages again.

The great thing is that it actually works. With this (rather small) patch, I am able to boot my P4 and get exactly the same error reports that I get on my Pentium Dual-Core laptop.

This also prompted me to start fixing the numerous false positive warnings that occur because kmemcheck is reporting eagerly. Most prominent of these are the bitfield operations, which load a multiple of 8 bits at a time, even though just one of the bits are actually used. The solution is to explicitly initialize the whole bitfield at once just after the struct has been allocated. Yes, this means that we won't be able to detect errors in the use of uninitialized bitfields, but this has always been true and is a result of the combination of the x86 architecture and the way we detect memory accesses.

And this is the current status: 0 errors reported during kernel initialization, 3 errors reported during userspace initialization, 0 errors while transferring a 4 MiB bzImage over SSH. Compare that to the ~2400 errors this would give us a month ago. This time I believe that we are truly ready for mainline. It will be interesting to see if anybody will try it out or review the patches, however...

Single-stepping a REP STOS...

I've recently made a startling discovery that explains a LOT about how kmemcheck has been working (or not) on one of my machines.

Yesterday I added the kmemcheck hooks into the DMA API, which means that we should now not give any false-positive errors about DMA-able memory. The patch was essentially a one-liner, since the rest of the DMA API deals with whole pages only (and they come straight from the page allocator, so they're not tracked anyway).

But still I was getting a huge amount of errors from sysfs code. This puzzled me for many hours. The code was apparently okay. In fact, the allocation in question was explicitly being zeroed out (it was calling kzalloc()), so it shouldn't have been possible to even find any use of uninitialized memory in it. I added some code to dump the memory along with the shadow dump, and it showed that the array was indeed being zeroed, but not marked initialized.

Because memset() is such a common operation (and needs to be fast), I've written a custom memset() function that checks whether the target memory is being tracked or not; if it is, we don't have to take any page fault at all, but we can simply zero the memory and set the initialization status to "initialized" at the same time.

I suspected my custom memset() of being in error. So I commented it out. And the result was even more startling; I now got a kmemcheck error on just about every memory access...

Something had to be wrong with the built-in memset. This is its definition:

static inline void * __memset_generic(void * s, char c,size_t count)
{
     int d0, d1;
     __asm__ __volatile__(
             "rep\n\t"
             "stosb"
             : "=&c" (d0), "=&D" (d1)
             :"a" (c),"1" (s),"0" (count)
             :"memory");
     return s;
}

(Source code taken from the Linux Kernel. This code is licensed under the GNU GPL version 2.)

Taking a new look at the first kmemcheck error reported, I got another clue. The kzalloc() allocation was uninitialized except for the very first byte!

I wrote a short program for userspace which called the above function and single-stepped it with gdb on my two machines, one P4 3.0 GHz, and one Pentium Dual-Core 1.47 GHz. To my great surprise, the P4 skipped the whole REP STOS construct in one go, while the Dual-Core got a trap for each repetition of the STOS.

This is very grave news for kmemcheck. I had tested it on my Dual-Core earlier and thought that it would behave the same for all CPUs; there's not a word about single-stepping REP instructions in the Intel's System Development Manuals that I could find, anyway.

There are basically two solutions to the problem:

1. Black-list the models that don't single-step each repetition
2. Emulate the instruction (i.e. no single-stepping at all for the REP instructions)

And neither of them is particularly attractive.

But I have started working on instruction emulation to see how far I can get.

I've also contacted Intel and asked for more information about the peculiarity.

I only hope that there are not more unpleasant surprises like this...


Vegard


PS: I have written a (32-bit) userspace program that backs up my suspicions. Compare these outputs:

$ ./a.out
processor       : 7
cpu family      : 6
model           : 15
model name      : Intel(R) Xeon(R) CPU           E5320  @ 1.86GHz

Counted 1000 REP STOS instructions (expected 1000).

$ ./a.out
processor       : 1
cpu family      : 15
model           : 6
model name      : Intel(R) Pentium(R) 4 CPU 3.00GHz

Counted 55 REP STOS instructions (expected 1000).