Comment by nkurz | Hacker News Reader

Comment by nkurz | Hacker News Reader

Parent Full thread

Maybe this is the right place to ask a meta-question on malloc that I've been wondering about.

Are there any malloc implementations that try work more cooperatively with the virtual memory system? The systems I've looked into seem to duplicate a lot of what the kernel and hardware are already doing. They don't seem to really distinguish between actively mapped memory and allocated but untouched memory.

With a 64-bit system, malloc could internally just reserve some vast logical address space and let the kernel fault pages in as needed. Instead of having a single frontier, you might have thousands of arenas used for different slab sizes, each being automatically extended as needed. Each arena would have a maximum waste up the 4KB page size, but on modern systems this seems unlikely to ever add up to a real burden.

You'd still need record keeping for allocations within a slab, but the page table itself would be the authoritative record for the arenas themselves. All the pieces for this approach seem fairly straightforward. The only major thing lacking (I think) is an efficient userspace way to request the unmapping of a page that is no longer needed.

Is there research into this approach? What key terms should I be searching for?

Edit:

I think this discussion may be about the same approach that I'm wondering about: http://caml.inria.fr/mantis/view.php?id=6101

And this paper touches on a lot of the same issues, although coming at it from the direction of modifying the hardware: http://research.cs.wisc.edu/multifacet/papers/isca13_direct_...

You don't need to have a single frontier, and IIRC no one does these days. A stack of slabs per "arena" suffices, and the extra cost is only a read from a cacheline you'll soon need anyway. It looks like jemalloc uses a tree of "runs" for that.

I don't know exactly what you're imagining, but I don't see how you can pass this off to the kernel. You need a slab which has free memory. How do you know where to find it? You could write a nasty new syscall to ask the kernel for a ZFOD page(s), and then cry because your program is slow.

Also, unless your slabs are huge and your allocator is being used to fuel some kind of pre-caching, faulting pages is going to be suboptimal. You incur at least twice as many mode switches: one for the mmap call, one for each faulting page. I've measured this, and it gets pretty expensive. I'm kind of dubious about the performance of schemes which stray from the principle of "allocate what you actually need; free it when you don't."

The bottom line is that a slab allocator should be solving a different, mostly less general problem than the kernel. It needs finer granularity and it's optimizing for common block sizes that are small enough to fit into slabs of known sizes. So it should optimize for allocating page chunks in a small subset of possible sizes (namely, the slab size(s)), while the kernel should be worried about unbounded, oddly-sized page chunks.

I toyed with scalable allocators for a course a few years back. It's a little embarassing, but if you want to see what the costs actually are: http://www.andrew.cmu.edu/user/apodolsk/418/finalreport.html

You can do lockfree slab allocators pretty easily, so the game in scalable malloc is really about avoiding inter-CPU cacheline sharing and fitting your data structures into per-CPU caches. Slabs happen to be really good for that, for non-obvious reasons.

It certainly wouldn't be the first time that I've suggested something ridiculous. One easy explanation for the lack of papers I can find is that the idea is so obviously useless that no one has written about it!

That said, it just seems unlikely that the best solution for 32-bit systems with limited virtual address space and slow interrupt generating system calls is also the best solution for 64-bit systems with practically-limitless virtual address space and fast hardware-supported syscall/sysenter.

And I think what I'm suggesting is roughly analogous to what's being done in Azul's (successful?) C4 garbage collection: provide fast userspace for per-process page table manipulation, and offload as much as possible to the hardware: http://www.azulsystems.com/sites/default/files/images/c4_pap...

But I'm definitely too fuzzy about some of the key concepts to suggest anything particularly coherent at this point. I'll check out your writeup, and try to learn more. Thanks!

jemalloc works much like what you're describing. The one missing piece in terms of userland/kernel cooperation is that jemalloc aggressively discards dirty unused pages because it doesn't know whether other processes need those pages. If the kernel were to communicate the severity of memory pressure to userland, it would be possible to more intelligently rate-limit the purging.

Reply on news.ycombinator.com