.png)
3 weeks ago
2
Without subscribers, LWN would simply not exist. Please consider signing up for a subscription and helping to keep LWN publishing.
Paul McKenney gave a remote presentation at Kangrejos 2025 following up on the talk he gave last year about the lifetime-end-pointer-zapping problem: certain common patterns for multithreaded code are technically undefined behavior, and changes to the C and C++ specifications will be needed to correct that. Those changes could also impact code that uses unsafe Rust, such as the kernel's Rust bindings. Progress on the problem has been slow, but McKenney believes that a solution is near at hand.
He began by noting that the obvious way to write an atomic last-in-first-out (LIFO) stack as a linked list in C or C++ invites undefined behavior. Specifically, it can end up creating a pointer that has a valid bit pattern, but an invalid provenance. Imagine that a thread wants to push an item (A) onto a stack; it reads the pointer to the current top of the stack (B), stores that into A's next field, and then uses an atomic compare-and-swap instruction to store the pointer to A as the new top item only if the top-of-stack pointer still points to B.
So far, so good. Now suppose that a second thread concurrently pops an item off of the stack, frees it, allocates a new item (C), and then pushes it to the stack. If the new allocation has a different address, then the first thread's compare-and-swap operation will fail, and it will know to retry. But what if the memory allocator, seeing that a piece of memory of the right size has just been freed, gives the same memory back to use for the new item? In that case, the first thread's compare-and-swap operation will succeed, because the pointer to B and the pointer to C are bitwise identical. As far as the actual CPU is concerned, nothing has gone wrong. But according to the C abstract machine, even though the pointer to C and the pointer to B have the same bits, they have different provenance information. This makes the dangling pointer to B (which has been freed) a "zombie pointer", any use of which is undefined behavior. Currently, compilers aren't taking advantage of this particular piece of undefined behavior, but McKenney wants to get out ahead of the problem by agreeing on a solution ahead of time.
Importantly, it's not really possible to change all of the code that works this way, because there are so many open-coded atomic LIFO stacks or equivalent pieces of code spread throughout almost every nontrivial multithreaded project, McKenney said. The first implementation of this kind of stack is unknown, but it probably dates to the 1960s. There was at least one implementation in the 1970s that referred to the technique as being generally known.
Last year, Davis Herring's "angelic provenance" proposal looked as though it would help, but the C++ committee found examples of some code where angelic provenance would "invalidate some really important optimizations". Herring's proposal would add a new rule requiring that when an integer is cast to a pointer (or, if McKenney's separate proposal is adopted, when a pointer is loaded from an atomic type), if there is any choice of pointer provenance that the compiler could make that will prevent the program from having undefined behavior, the compiler has to pick that option.
Technically, the requirement is that there is no happens-before relationship between the angelic choice and the object's creation. So if the object were being created in a separate thread, and the creation might occur after the choice, but the threads are not synchronized, so the compiler cannot prove that will be the case, the compiler will still be required to consider that object's provenance.
The modified rule would only require the compiler to consider the provenances of objects that already exist at the time of the operation (but see the sidebar for more information). This is both simpler for compiler authors to implement, and avoids problems with obtaining a pointer to an object before it is actually allocated. McKenney's additional proposal would make angelic provenance work for LIFO stacks by treating any loads through an atomic type as though the loaded pointers were just converted from an integer, so the angelic provenance rule would apply and the obvious way to implement an atomic LIFO stack would be defined behavior ... almost.
In C and C++, any operation with an invalid pointer isn't guaranteed to produce a sensible result. So, while reading a pointer value from an atomic variable for the LIFO stack no longer causes a problem (with the above proposals), writing the pointer value in the first place could be optimized out. So the final piece needed for the existing LIFO stacks to work would be a requirement that when writing an invalid pointer, the actual bits of the pointer are written to the destination, even if the provenance information is no longer usable.
All together, there is "not all that much" work to get all these changes through the committee. "There's less heartburn on current proposals than there has been in the past."
Ryhl raised a question that had come up when considering implementing analogous proposals in Rust — wouldn't the new rules prevent angelic choices from being reordered relative to "demonic" choices? Specifically, there are certain operations, such as memory allocation, where the compiler is allowed to assume that the operation goes as badly as possible for the program being optimized. Therefore, if the program is incorrect in those cases, it's incorrect overall. While Rust doesn't have the same undefined behavior rules as C, programmers writing unsafe Rust still need to uphold various invariants, and so might run into this. She shared this example Rust code from Ralf Jung demonstrating the problem:
fn nondet() -> bool { let b = Box::new(0); ptr::from_ref(&*b).to_addr() % 3 == 0 } let a1 = 0; let a2 = 1; let a1addr = ptr::from_ref(&a1).to_exposed_addr(); let a2addr = ptr::from_ref(&a2).to_exposed_addr(); let b: bool = nondet(); // demonic non-det choice let x = ptr::from_exposed_addr(a1addr); // picks provenance of a1 or a2 let y = if b { x } else { x.with_addr(a2addr) }; let _val = *y;In this example, nondet() is a demonic choice (because the compiler knows that a newly allocated heap item could be located anywhere, so for the purposes of determining whether the function might be malformed, it can assume that the location is whatever would cause undefined behavior) and ptr::from_exposed_addr() would be an angelic choice under the proposed rules around integer-to-pointer conversions. The difference between the "exposed" functions and their unexposed variants is an artifact of Rust's experimental exposed-provenance model — when casting an integer to a pointer, only "exposed" provenances can be considered to become the provenance of the pointer. Taken together, this means that the compiler would be required to pick whichever provenance for x (out of a1addr and a2addr) makes the program valid, given its assumptions about b. Ryhl's point was that currently, reordering the assignment to x above the call to nondet() is permitted, since x doesn't depend directly on the value. But that optimization would be invalid under the proposed rules, because then the demonic choice could always pick whatever value makes the answer picked by the angelic choice invalid, and the program would break.
The conservative solution would be to require the compiler to avoid reordering angelic and demonic choices relative to each other, but that could prevent local optimizations such as moving assignment to a variable out of a loop. It's unknown what the practical performance impacts or knock-on effects of a requirement like that would be.
McKenney initially thought the example was broken as-is, until Gary Guo clarified that in Rust, one can have a pointer with an address that points outside the memory of its associated provenance, as long as it is not dereferenced. This is helpful because it allows for valid pointer arithmetic between more objects. That's not how it works in C or C++, so McKenney hadn't considered the problem. But once it was explained, he was thoroughly enthusiastic about the choice to allow pointers to be used in this way.
He complimented the Rust folks for allowing arbitrary pointer arithmetic, which is work that he has put off trying to get through the C++ committee. "I haven't thought about that, because I wanted to only fight one dinosaur in C++ at a time." He acknowledged that the example raised further problems, though, and commented that it would be exciting future work. Hopefully, by Kangrejos next year, he will have a satisfying answer. If the current proposals do get through the C and C++ committees, those languages will likely run into an analogous problem if they ever attempt to loosen the rules around pointer arithmetic.
