Static Allocation, Constant Work
22 points by cgrinds
22 points by cgrinds
Attempting to allocate just one more Order could cause kernel’s OOM killer to terminate the entire order matching engine, losing the other million orders, or, better yet, to kill the supervisor process so that you can’t even restart.
Static allocation gives you piece of mind.
This gives the misleading impression that the kernel's OOM killer would not later kill a program that had allocated its memory statically. This is false because the kernel has no notion of which program might be misbehaving when it comes to memory reservation or even if any program is misbehaving at all. All the OOM killer knows is that the system is OOM and it is free to kill any program on the system, including one that followed the advice given here. You need the entire system to be following this discipline in order to have this peace of mind, so this advice should not be interpreted as generalizable, even setting aside all the usual reasons why full static allocation might be a bad idea for most programs.
Memory locking exists.
Some operating systems (e.g. embedded) don't have overcommit.
Overcommit is configurable, it can be turned off.
At least on Linux, you can disable overcommit. https://www.kernel.org/doc/Documentation/vm/overcommit-accounting
Doesn't he acknowledge this in exactly what you quoted?
or, better yet, to kill the supervisor process so that you can’t even restart.
I guess you could argue it still doesn't give you full peace of mind, but I feel like we shouldn't ignore an important technique to improve reliability compared to the extremely common case of runaway memory allocation. If you're running one critical process on an EC2 machine, and you set your static allocation to utilize ~80 to 90% of the total available memory on the host, your chances of OOM effectively drop to zero.
This suggests an interesting solution for hardening code, which I’ve learned from Fil. If your allocation function is typed […] you can write an allocator that uses type-segregated pools internally. This will be somewhat less memory efficient, as the allocator won’t be able to re-use freed memory of objects of type U for objects of type T, but the memory overhead will probably be small […] you might actually gain in memory locality, and solve most of type confusions
Type-segregated allocators are usually cited back to the slab allocator in the Solaris 2.4 kernel in the mid 1990s. Since then it has been completely normal in unix-like kernels. (Arguably it’s a generalization of mbufs.) wikipedia usenix
In untyped userland C-style allocators, size-class based allocation gives you many of the advantages of typed allocation. The advantage of size-class allocation (compared to trad / glibc mixed allocators) is there’s much less fragmentation of the kind where large blocks get broken up into uselessly small pieces and never coalesced; the disadvantage is underfilled pages devoted to size classes with low usage.
The advantage of typed slab allocation is that the size classes perfectly match the structure sizes, pages are perfectly type stable, and it’s easy to implement per-subsystem memory quotas. Bonwick’s paper probably lists more things I have forgotten.
Bonwick’s paper probably lists more things I have forgotten.
One major thing you left out, which I'm sure I remember from Bonwick's paper, is that when you're recycling objects rather than memory you can have the objects hang on to resources. A userland example would be recycling a dynamic array by setting the length to 0 while retaining the buffer pointer and capacity. I bet Bonwick's example is less potentially problematic by being bounded in size (so you don't have the high-watermark issues, which require a more complex policy in a robust system), but the dynamic array example should get the idea across.