Detecting kernel memory leaks [LWN.net]

Detecting kernel memory leaks

Posted Jun 25, 2009 12:18 UTC (Thu) by epa (subscriber, #39769)
In reply to: Detecting kernel memory leaks by cmarinas
Parent article: Detecting kernel memory leaks

The trouble with garbage collection in languages such as C, which allow casting pointers into other data types, is that you can't be sure what is a pointer and what isn't. A block of memory might contain values which appear to be pointers and stop the garbage collector freeing some blocks. This is just bad luck, and on a 64-bit system would have to be very bad luck, except for the fact that the kernel accepts data from untrusted user space. There would be all sorts of interesting DoS attacks based on getting the kernel to store some binary data which looks like pointers and exhausting the system memory.

to post comments

Detecting kernel memory leaks

Posted Jun 27, 2009 0:24 UTC (Sat) by dlang (guest, #313) [Link] (5 responses)

given that a pointer is a 32 bit or 64 bit value, please explain what 'looking like a pointer' means.

Detecting kernel memory leaks

Posted Jun 27, 2009 13:08 UTC (Sat) by nix (subscriber, #2304) [Link]

'Looking like a pointer' = 'has a value which makes it likely to be a
pointer and not a number with some other meaning'.

There are many tricks you can use: value pointing to a writably-mapped
region of the application's address space (very effective on x86-64, of
course), alignment on platforms where that matters...

Detecting kernel memory leaks

Posted Jun 28, 2009 23:29 UTC (Sun) by epa (subscriber, #39769) [Link] (3 responses)

By 'looking like a pointer' I mean 'likely to confuse the garbage collector into thinking it is a pointer to addressable memory'. That then causes any allocated space at that address not to be freed.

Detecting kernel memory leaks

Posted Jun 29, 2009 0:10 UTC (Mon) by dlang (guest, #313) [Link] (2 responses)

if a garbage collector is looking at random bytes and trying to guess if they are pointers or not it's going to guess wrong a lot of the time.

I don't think it's even a requirement that pointers be word aligned in memory, so you would have to look at every 4 byte sequence and calculate if it could be a pointer or not.

that's a _lot_ of calculations to waste your time on, even if you had a chance of being right 100% of the time.

Detecting kernel memory leaks

Posted Jun 29, 2009 6:56 UTC (Mon) by nix (subscriber, #2304) [Link]

The garbage collector doesn't have to do that everywhere, but on the C
stack, it does. It can often rely on alignment requirements because humans
cannot dictate the layout of the stack: only the compiler can. (On many
architectures, e.g. SPARC, they're hard requirements anyway.)

Detecting kernel memory leaks

Posted Jun 29, 2009 7:40 UTC (Mon) by epa (subscriber, #39769) [Link]

if a garbage collector is looking at random bytes and trying to guess if they are pointers or not it's going to guess wrong a lot of the time.

Exactly. Which is why C is not an ideal language for a garbage-collection runtime. More high-level languages provide guarantees of what's a pointer and what isn't, so the GC doesn't have to guess.

Garbage collection in C and C++ can still be useful and fast, but it can never be 100% correct. This may not matter for many applications, but for programs like the kernel which need to be highly secure and must cope with untrusted user input (which could easily contain 32-bit or 64-bit ints carefully chosen to look like pointers), I suspect it does.

I wonder if there is a subset of C which provides the minimal guarantees needed to make garbage collection safe and complete. The main thing would be not to cast pointers to ints and back, nor to allow casting between pointers to things of different sizes, nor arbitrary pointer arithmetic (though arrays could still be provided).