C++ already gives us a tool for pointer zapping
C++ already gives us a tool for pointer zapping
Posted Oct 16, 2024 7:07 UTC (Wed) by comex (subscriber, #71521)In reply to: C++ already gives us a tool for pointer zapping by NYKevin
Parent article: Zapping pointers out of thin air
https://github.com/rust-lang/unsafe-code-guidelines/issue...
But even if LLVM never optimized pointer comparisons, you would still be in trouble. The problem is alias analysis. The compiler is always tracking which pointers can legally alias which other pointers, and if it thinks pointer A can’t alias pointer B, then it can reorder accesses to A with respect to accesses to B. And it assumes that a freshly malloced pointer doesn’t alias with any other pointer not derived from it. Suppose pointer A is freshly malloced, and pointer B was previously freed, but you did a pointer comparison (which was not optimized) and it turns out that A and B have the same address. So you expect to be able to, say, write a value to pointer A and then read the same pointer back from pointer B. But oops, the compiler assumes that the write and the read don’t alias and switches their order!
This behavior can be justified by pointer zapping or by provenance. But if you wanted to get rid of the behavior instead of justifying it, then you would need the compiler to stop assuming that new allocations don’t alias. Either the compiler has to disable that optimization entirely, or it has to detect that you did the pointer comparison and conditionally disable it. But conditionally disabling it is a lot harder than it sounds, since e.g. the comparison might be hidden behind a function call, or it might even have been optimized away. And disabling it entirely… well, if it were just about heap allocations, you would get a small but measurable loss in optimization potential. But to be fully consistent you would probably need to also disable it for *stack* allocations, and that might be quite a bit worse.
Admittedly, it’s hard to be sure how bad the performance loss would be, because nobody has actually tried to write an optimizer that’s as aggressive as possible while still being formally sound under some sort of limited-provenance model.
The ‘fun’ thing is that this particular type of alias analysis issue essentially never occurs in real programs. And yet it’s extremely difficult to formally rule out without adding relatively-invasive provenance rules. And if you don’t formally rule it out, then it can probably be exploited from safe Rust code. And so we end up with the provenance rules.
Posted Oct 16, 2024 7:24 UTC (Wed)
by NYKevin (subscriber, #129325)
[Link]
1. We can statically prove that the pointers have the same address and overlapping or identical provenances. Fold it to true.
(3) sounds weird, but it probably happens fairly often (if both pointers are known to be valid-or-else-UB-happened, if both pointers came from the same array as in a simple for loop, etc.). Meanwhile, if we're in case (4), then I find it hard to believe that we're really losing much performance from the optimization barriers anyway. And (4) is pessimistic anyway. If you can prove that one of the pointers is valid-or-else-UB-happened, you probably don't need to insert a provenance barrier for that pointer at all. The set of optimizations we're losing here looks really, really small to me, but maybe I just don't understand how compilers work.
On CHERI-with-rich-pointer-comparison, you can replace both (3) and (4) with "We can't statically prove either (1) or (2). Emit a comparison instruction," since in that case the hardware will already DTRT anyway. For that matter, you can *also* do that in any implementation which does not have provenance, since it is semantically equivalent to inserting provenance barriers "everywhere."
Posted Oct 17, 2024 13:52 UTC (Thu)
by epa (subscriber, #39769)
[Link] (2 responses)
Posted Oct 17, 2024 18:35 UTC (Thu)
by notriddle (subscriber, #130608)
[Link] (1 responses)
Isn't the real problem nowadays TLB and cache utilization? Because it seems like this would result in severe fragmentation.
Posted Oct 18, 2024 18:05 UTC (Fri)
by Wol (subscriber, #4433)
[Link]
I understand behind the scenes malloc allocates a big area, which it hands out in small bits. If that big area is an entry in the page table, and especially if the programmer can hint to malloc that "these are long lived, these are short lived, these are small, these are large", it's then easy to move/consolidate all this in ram (copy, update the page table, you're done), and malloc can just drop the arena and not re-use the arena's logical address when it's all freed.
Cheers,
C++ already gives us a tool for pointer zapping
2. We can statically prove that the pointers do not have the same address, or have non-overlapping provenances. Fold it to false.
3. We can statically prove that if the pointers have the same address, then they also have overlapping or identical provenances. Emit a comparison instruction.
4. We can't statically prove any of the above. Insert provenance barriers for both operands, which only apply prospectively to these exact variables (i.e. calling functions don't have to know we did this unless we return one of the pointers, in which case we were already in the business of more complicated escape analysis anyway), and then emit a comparison instruction.
C++ already gives us a tool for pointer zapping
C++ already gives us a tool for pointer zapping
C++ already gives us a tool for pointer zapping
Wol