// HACKER NEWS — CYBERSECURITY
Static Allocation, Constant Work
Memory Safety’s Hardest Problem
named something I’d hit but couldn’t articulate.
Your case is a pointer into one union variant surviving a write of a different
variant, so live typed pointers end up reading bytes that belong to something
else now.
Last year I wrote a limit-order matching engine and shipped a use-after-free: a
cancelled order was released back to the pool while it was still linked into its
price level, so the next allocation handed that memory to a new order and the
stale link kept resolving. I’d filed it under “I was careless with lifetimes.”
After your post I’m not sure that’s what it was. A recycling pool looks like a
tagged union where the tag is “which generation of object currently lives in
this slot,” and nothing in the type system tracks it. Is that a fair reading, or
does the pool case stay genuinely easier because generational indices actually
solve it and the union case has no equivalent?
Yes, object pools are an interesting case to think about, as they clarify the
relation between memory safety and more general correctness.
First, consider the case where no object pool is used, and we malloc and
free order objects. In this case, the logical error of use-after-free turns
into physical type confusion, and can easily lead to arbitrary code execution
and the like. If you have two objects of different types sharing the same
memory location, a user-controlled integer in one object might be a function
pointer in the other: an exploitable goto primitive
Now, what happens if we introduce an object pool which stores a list of “dead”
objects of type T? Logical use-after-free is still possible, but its physical
effect is now different — we still get aliasing of memory, but there’s no type
confusion. You can’t necessarily fiddle with an integer and change a function
pointer, unless you additionally hit the hard case, where the object in question
stores an inline enum. Assuming that doesn’t hapen, you get a perfectly defined,
deterministic behavior, even if you are not happy about the result.
This suggests an interesting solution for hardening code, which I’ve learned
from Fil. If your allocation function is typed
(it takes a T comptime parameter or runtime type witness, rather than a
runtime type-erased size and alignment), 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 (rare object
types do not matter, popular object types will have a lot of intra-type re-use),
you might actually gain in memory locality, and solve most of type confusions.
Again, inline enums break this, but, curiously, if you always heap allocate enum
variants, then this works again. Fil-C can’t use this, because C allocator’s
interface is untyped, but someone else could :P
But this is academic. How do we avoid the bugs? Generational indexes are a
popular remedy, but I have never used them, so I don’t have any non-common
knowledge insights about this pattern. Instead, I will share another pair of tricks
from TigerStyle.
I have only a vague understanding of what an order matching engine is, but I
suspect these tricks might help there
https://www.youtube.com/watch?v=GRJtYwneG2Q&t=1823s
This is the pool idea, taken to its logical conclusion. We specify the maximum
number of orders we are willing to work with at startup, and never go beyond
that. So, you might start the program as