LWN: Comments on "Detecting kernel memory leaks"

The LWN kernel page leaps from strength to strength :-)

alexs — 2010-06-09T07:46:09+00:00

whilst the article is about an analysis tool for fixing the sources
a bigger part of the comments talk about "fixing" in a live system.
these are two different shoes.

if you are already pretty close having a 100% sane system
then close the gap and make yourselves happy with the result
instead of "inventing" risky and costly nearly-random effect generators.

having no clue about the root problem wont buy you much benefit in successfully resolving it.

Detecting kernel memory leaks

epa — 2009-06-29T07:40:21+00:00

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

Detecting kernel memory leaks

nix — 2009-06-29T06:56:48+00:00

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

dlang — 2009-06-29T00:10:34+00:00

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

epa — 2009-06-28T23:29:51+00:00

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

nix — 2009-06-27T13:08:26+00:00

'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

dlang — 2009-06-27T00:24:26+00:00

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

Detecting kernel memory leaks

epa — 2009-06-25T12:18:29+00:00

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

proski — 2009-06-18T16:55:48+00:00

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

cmarinas — 2006-07-27T08:49:54+00:00

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

cmarinas — 2006-07-27T08:41:26+00:00

(a bit late with replying but I only saw the article now)

There is no need to re-introduce the bugs found by Coverity as kmemleak managed to find some real leaks (I think about 4-5 at the moment - ACPI, i386 setup, SE Linux and a case of vfree used instead of vunmap in the ARM code) which Coverity wouldn't have been able to see because of the code complexity.

Coverity, however, can find potential leaks before they actually happen since it does a static analysis of the code.

Detecting kernel memory leaks

liljencrantz — 2006-07-19T15:55:11+00:00

Slabs are a performance hack to make some allocation patterns faster. This is completely different from halloc, which is a method for making memory deallocation significantly less cumbersome for the programmer. Both have the potential to waste less time and memory, but that is mainly a possible byproduct in the case of halloc.

Notifiers would work as a replacement for the halloc callback functions, but the result would be wordier and need more changes on existing code.

Detecting kernel memory leaks

nix — 2006-06-24T12:01:31+00:00

The need for the registration function is mostly obviated by notifiers, AIUI. The halloc() function is rendered unnecessary by the slab allocator (that's what slabs are, blocks of memory containing many potential objects of the same type, initialized from a template and allocatable at lightning speed.)

Detecting kernel memory leaks

nix — 2006-06-24T11:59:12+00:00

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

cpeterso — 2006-06-23T04:40:13+00:00

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.

The LWN kernel page leaps from strength to strength :-)

xoddam — 2006-06-23T01:37:08+00:00

Many thanks to all contributors. A stack of interesting leads from these
articles (not to mention the comments). More, more, don't stop!

Detecting kernel memory leaks

liljencrantz — 2006-06-22T13:11:52+00:00

One way to avoid some memory leaks is to have better ways to specify memory lifetimes.

The traditional memory allocation lifetimes are:

* 'the life of the current function' for allocations on the stack
* 'until I manually free this memory' for allocations on the heap
* 'when the number of users hits zero' for reference counting

All of these are very usable in and taken together they can be quite versatile.

There is however one other allocation model that I often find very useful; namely to say 'this piece of memory here is needed as long as that piece of memory over there is needed'. The Samba people use this allocation strategy using a function called talloc. I have written my own implementation (halloc) which is a bit different from talloc:

* You can register functions to be called when a specific piece of memory is free'd. That means you can call free on memory not allocated using halloc when a halloc'd piece of memory is freed, which makes using halloc together with libraries and functions not specifically written for halloc much easier.

* Halloc overallocates memory, and uses the extra memory to fullfill smaller memory allocations. That means that doing lots and lots of very small memory allocations very close to free, both in memory usage and CPU time. In fish (http://roo.no-ip.org/fish) only one quarter of all calls to halloc actually result in an underlying call to malloc.

Most of the time, the scope of a halloc allocation is still a single functions lifetime. The major difference, however, is that you can specify _which_ function. You can send along a context as a parameter to another function, and all the memory allocations performed by the called function will use the supplied context as allocation scope. This takes C a huge step closer to the ease of use of automatically garbage collected languages when it comes to memory handling.

At least that has been my experience.

Detecting kernel memory leaks

simlo — 2006-06-22T09:56:52+00:00

Hmm, why not just "port" the Boehm-Demers-Weiser conservative garbage collector (http://www.hpl.hp.com/personal/Hans_Boehm/gc/) to kernel space?
I have previously used it - as a garbage collector, not only as leak detector - in userspace with great success.

Detecting kernel memory leaks

mingo — 2006-06-22T09:39:14+00:00

yep, even in its current (very) limited testing kmemleak found a real ACPI memory leak, with some more suspected ACPI leaks being analyzed.

We should also note that prior Coverity checking clean-sweeped some of the 'easy' memory-leaks, artificially reducing the visible efficiency of this GPL-ed tool.

(It could be tested by intentionally re-introducing some of the Coverity fixes but that's hard and laborous because not all Coverity fixes are identified as such and the code might have changed meanwhile.)

Detecting kernel memory leaks

flewellyn — 2006-06-22T09:34:05+00:00

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

kleptog — 2006-06-22T08:58:42+00:00

The question ofcourse is: has it found anything yet?