The SLUB allocator
The SLUB allocator
Posted Apr 12, 2007 18:29 UTC (Thu) by rwmj (subscriber, #5474)Parent article: The SLUB allocator
I'm yet again left thinking what would happen if the kernel devs actually thought about proper garbage collection.
Rich.
Posted Apr 12, 2007 21:43 UTC (Thu)
by flewellyn (subscriber, #5047)
[Link] (1 responses)
Posted Apr 12, 2007 23:57 UTC (Thu)
by rwmj (subscriber, #5474)
[Link]
Rich.
Posted Apr 12, 2007 23:58 UTC (Thu)
by bronson (subscriber, #4806)
[Link] (1 responses)
Posted Apr 13, 2007 9:36 UTC (Fri)
by nix (subscriber, #2304)
[Link]
(You *need* proper garbage collection handling cycles if you implement AF_UNIX sockets with fd passing, or any bugger can DoS you grotesquely.)
Posted Apr 19, 2007 10:20 UTC (Thu)
by jfj (guest, #37917)
[Link] (2 responses)
I mean, why do: close the file descriptor, but leave the memory for the GC.
GC collection would then have to traverse the entire object space and kill all the caches for good! Just free the damn thing when you're there.
Posted Jul 5, 2010 11:14 UTC (Mon)
by marcH (subscriber, #57642)
[Link] (1 responses)
So can I have both please?
Posted Apr 22, 2007 22:50 UTC (Sun)
by RareCactus (guest, #41198)
[Link]
Things that are good practice for sysadmins writing perl scripts or programmers writing Java or COBOL "business logic" are not good practice for kernel hackers.
Garbage collection is about managing memory lazily. It will always hold on to memory longer than equivalent non-GC code would. It will trash the data cache by rummaging through things unecessarily.
Traditional garbage collection algorithms like mark and sweep and generational GC tend to require the system to come to a "stop" while the garbage collector thread scans through everything. It should be obvious to anyone that this is unacceptable for a kernel, especially on a multi-core system. There are some newer algorithms that mitigate this behavior somewhat, at the cost of even worse performance.
The kernel is about efficiency. Yes, even in 2007. It's about writing code that everyone will use. It's about spending 2x the time to get a 10% speedup. It's about scaling up to 4, 8, 16 CPUs, and down to a 50 MHz antique.
The kernel manages many other resources besides memory: things like network connections, file descriptors, IRQs, hardware stuff. malloc() might make your head spin, but it's not as hard to write as the TCP stack.
Userspace can and should move more and more to high-level languages with garbage collection, first-class functions, the whole nine yards. I like Ruby, myself. And there are certain resources in the kernel that might benefit from a GC-like approach. But memory is not one of them.
R/C
Posted Jan 12, 2009 9:52 UTC (Mon)
by Blaisorblade (guest, #25465)
[Link]
But it doesn't apply in kernel space, apart from existing usage of manual refcounting, for several reasons:
- GCs depend on wasting memory space. A copying GC needs twice the space actually used by the application, by definition (one would use it just for the young generation of a generational GC, though). Refcounting uses exactly the needed space, no more, no less.
Even kmalloc is implemented on top of that: allocation sizes are rounded up mostly to the next power of 2, with a few exceptions. A 700-byte object will actually use 1024 bytes. See include/linux/kmalloc_sizes.h for the actual existing sizes.
- All the discussion argues about automatic refcounting. That means incrementing refcounts on each function call because you are pushing parameters on the operand stack. No kidding - CPython is like that. Multithreaded CPython was 2x slower because of atomic refcounts and locks around name lookups, and that was CPython 1.5.2 IIRC. Nowadays the rest is more optimized (even if it still hugely sucks), so the same slowdown (for the same number of refcounts) would have a given impact.
Now, the kernel obviously does not use refcounting like that. If they can live without recursive locks, they can also avoid incrementing a refcount in a thread which already owns a reference.
SSHHHHH! You can't say that word around C programmers! They get all twitchy and start to yell incoherently.The SLUB allocator
Yeah .. funny, but that actually happened, recently.The SLUB allocator
What kind? The kernel already has reference counting. If you're advocating mark & sweep... Well, go ahead and give it a shot! It might be a good master's thesis, but I'm not sure it would ever be better than the slightly buggy manual mess that we have now. :)The SLUB allocator
It's already there: net/unix/garbage.c.The SLUB allocator
One problem with GC is that resources are not freed As Soon As Possible. For memory that may be a win, but there are other things: File descriptors, inodes, locks, etc. These things Must be freed as soon as possible, and no you can't do that periodically every time GC is triggered. So since the code is there, it is also better to free the memory as well.The SLUB allocator
The SLUB allocator
> I'm yet again left thinking what would happen The SLUB allocator
> if the kernel devs actually thought about proper
> garbage collection.
> Rich.
The SLUB allocator
- a recent paper argued that a GC needs to use 5x the used memory to be faster than manual allocations, so that the cost of a scavenging (which is always big, even with generations) is paid infrequently enough. That's not an option in kernel.
- incremental/real-time GC (which do not stop execution) are much slower if fine tuned, and extremely hard to get right.
- kernel devs are extremely concerned about cache impact, even because they'd like to leave the caches for app usage as much as possible. And any GC which is not refcounting is notoriously bad about locality.
- when you work in a dynamic language and already have a VM, you might as well implement a GC, but here there is no VM whatsoever.
- All that is with general purpose memory allocators. The kernel makes extensive use of the SLAB/SLUB interface instead of kmalloc(), and that allocates fixed-size objects.