GoKawiilStatic Allocation, Constant Work
In reply to this email:
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
Static Allocation The first one is: No dynamic memory allocation after initialization 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 $ order-engine --orders-max=1_000_000 and then one of the first lines in its main function would be : const orders: []Order = try gpa.alloc(Order, cli_args.orders_max); If, at runtime, more than orders_max requests come in, the surplus requests are rejected. Someone might object: “But what if I actually have some spare memory for one more order? Wouldn’t it be a good idea to at least try to handle it?” My rejoinder would be “Well, what if you don’t?”. Systems operating at capacity without strict limits fail catastrophically. 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 peace of mind. The system might fail to start if you don’t have enough memory, but, if it did start, you can be rest assured that it would handle overload gracefully, continuing to render the service while you are provisioning a beefier machine.