Detecting kernel memory leaks

Posted Jun 22, 2006 9:34 UTC (Thu) by flewellyn (subscriber, #5047)
Parent article: Detecting kernel memory leaks

That algorithm is strikingly similar to tricolor marking, an incremental garbage collection
algorithm invented by Djkstra.

Which brings to mind the question: should the kernel folks just bite the bullet and implement an
in-kernel GC? This patch is halfway there already.

Detecting kernel memory leaks

Posted Jun 23, 2006 4:40 UTC (Fri) by cpeterso (guest, #305) [Link] (1 responses)

I remember reading a LKML comment by Linus that he would never add a garbage collector to the kernel. Maybe one day, he'll eat those words. :-) I definitely think it's worth investigating, especially given these new memleak patches.

Detecting kernel memory leaks

Posted Jun 24, 2006 11:59 UTC (Sat) by nix (subscriber, #2304) [Link]

net/unix/garbage.c already contains a mark-and-sweep garbage collector: garbage collection is a requirement for AF_UNIX socket handling unless you like DoSes (which are easy: a program sets up an AF_UNIX socket, opens it itself but does not go into accept(), sends the socket's filehandle along the socket, closes both ends, and quits. Oops. One handle leaked, unless you detect the filehandles in transit along the the AF_UNIX socket, which means mark-and-sweep collection given that these fhes may be the fhes of other sockets which may themselves have filehandles in transit along them...)

Detecting kernel memory leaks

Posted Jul 27, 2006 8:49 UTC (Thu) by cmarinas (subscriber, #39468) [Link] (8 responses)

Indeed, the algorithm is pretty close to a garbage collection one, only that it doesn't try to free the orphan blocks.

Apart from the technical difficulties of a complete garbage collector in the kernel (big overhead, SMP systems, "stop the world scanning", pointer aliasing - see the container_of workaround in kmemleak), I am personally against it as it would make people lazier in dealing with memory resources.

Detecting kernel memory leaks

Posted Jun 18, 2009 16:55 UTC (Thu) by proski (subscriber, #104) [Link]

Actually, I'd rather see driver developers worry about aspects specific to the drivers rather than about memory. If the kernel starts consuming too much memory, the biggest users can be found and modified to use less memory.

Detecting kernel memory leaks

Posted Jun 25, 2009 12:18 UTC (Thu) by epa (subscriber, #39769) [Link] (6 responses)

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.

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).