Expressivity Gap: concurrent ABA-safe stack (atomics + provenance = pain)

[RalfJung]

Alice Ryhl brings up the following data structure: a concurrent stack where all elements can only be popped at once.

Stack declaration:

static STACK_TOP: AtomicPtr<Elem>;

struct Elem {
    next: *mut Elem,
}

Push:

let elem = malloc();
elem.next = STACK_TOP.load(Acquire);
while let Err(new_next) = STACK_TOP.cas(elem.next, elem, AcqRel) {
    elem.next = new_next;
}

Pop all:

let next = STACK_TOP.swap(null);
while !next.is_null() {
    let curr = next;
    next = curr.next;
    use(curr);
    free(curr);
}

This can run into ABA situations in push if, between the load and the cas, the stack gets popped, freed, new elements get pushed, and they re-use the same address. Then STACK_TOP will contain an Elem whose next points to the right element but still uses the provenance of the old element. Adding any code between the load and the cas cannot fix this since the new element might bet allocated after all of that code runs, and from_exposed_addr cannot "grab" a provenance that does not even exist yet.

IMO what should be done here is that next should be declared to have type usize, and one just passes the pointers through exposed_addr/from_exposed_addr when they enter/leave the stack. However some people seem to consider it very important that the stack uses a normal pointer type and can be used in the rest of the code without being aware that there are concurrency shenanigans going on. I am not sure why that is so important, given in particular that I think this will at best be an utter nightmare to specify, but here are some options I have seen or thought of:

1. I have seen a proposal to fix this for C++ with some sot of operation that "refreshes the provenance of a pointer and every other pointer reachable through it". That operation sounds like a nightmare for program verification since it can change state that is very far away from where that operation happens; we don't currently have any operation that reaches transitively through pointers and I think that kind of locality is important.
2. Make it so that from_exposed_addr actually works here. For instance, rather than angelically guessing the provenance when from_exposed_addr get called, we could generate a fresh symbolic provenance and gather constraints on how that provenance is used, and then raise UB when the constraints become unsatisfiable. (This is basically the "udi" part of PNVI-ae-udi.) Unfortunately I have no great idea how to do this with a complex aliasing model.
3. Introduce a kind of provenance that has the following effect: when doing a load through a pointer with such provenance, all provenance that was loaded is refreshed by passing the pointer through |p| from_exposed_addr(p.exposed_addr()), and the loaded provenance also recursively obtains this effect. However, now loads through such pointers cannot be DCE'd, since they have the side-effect of exposing some provenance, so this doesn't seem practical either.

So to me (2) is the only realistic option I have seen so far -- which conveniently would also get rid of angelic choice again, if we can make it work...

[Darksonn]

However some people seem to consider it very important that the stack uses a normal pointer type and can be used in the rest of the code without being aware that there are concurrency shenanigans going on.

The swap establishes a happens-before to anyone who touched any element in the linked list we got from pop_all, so my intuitive feeling is that we should end up with a linked list that isn't involved in concurrency shenanigans anymore.

[RalfJung]

Yeah you don't have to worry about race conditions, I agree.

ABA is still a problem though. Fundamentally the issue is that cas on pointers is a rather weak operation -- it checks that the addresses are still the same, but cannot check the provenance. Load-link / store-conditional could actually give us a better semantics here where the CAS is guaranteed to fail if there was any write between the load and the store, including a write that changed the provenance but not the address...

But without LLSC, all we got is this weak signal that the address didn't change, and that's unfortunately insufficient to avoid ABA issues in the Abstract Machine. The stack is not involved in concurrency shenanigans any more, but it is involved in provenance shenanigans. We can either do something global that has an unbounded effect (hard to reason about, both for program verification and optimizations), or we acknowledge that the stack is still a "strange stack" and indicate that to the compiler each time we access next.

[Diggsey]

I think there is another class of solutions (or at least variations on 1.) which involve making CAS special:

When a CAS operation succeeds, "refresh" the provenance on all pointers with the address involved in the CAS (it doesn't matter if it's the source or destination address since they're the same if the CAS succeeded).

[Diggsey]

Out of curiosity, does a CAS on CHERI take into account the permissions on the pointer?

[RalfJung]

"refresh" the provenance on all pointers with the address involved in the CAS

As in, scan the entire memory of everything and update provenance? That's even worse than an intrinsic to "refresh provenance of everything reachable". I don't consider such non-local actions to be acceptable. They also interact poorly with other parts of Rust, e.g. you might be refreshing (as in, changing) the provenance of pointers stored behind shared references, thus violating the immutability of shared references.

[Diggsey]

Also with (3) it's not obvious to me why the effect needs to be recursive?

Surely the following code is valid if such an erase_provenance() operation existed:

let elem = malloc();
elem.next = erase_provenance(STACK_TOP.load(Acquire));
while let Err(new_next) = STACK_TOP.cas(elem.next, elem, AcqRel) {
    elem.next = erase_provenance(new_next);
}

(Where erase_provenance() creates a pointer whose provenance is "refreshed" on load)

[Darksonn]

Your erase_provenance is essentially what I suggested originally on zulip. The problem is that it needs to be able to choose a provenance that doesn't exist yet (because the call to malloc hasn't happened yet).

[RalfJung]

(Where erase_provenance() creates a pointer whose provenance is "refreshed" on load)

Ah true, it doesn't have to be recursive since we can apply it to all relevant pointers when putting them into the list.

elem itself should also get that treatment though.

Your erase_provenance is essentially what I suggested originally on zulip. The problem is that it needs to be able to choose a provenance that doesn't exist yet (because the call to malloc hasn't happened yet).

It's not quite what you proposed, or at least not what I understood you proposed. The idea with this kind of "deeply erased" pointer is that doing a load through this pointer refreshes the provenance of the pointers it loads. So we never need to make a choice that picks a future allocation.

However, now each load becomes a possible "expose", which kills this proposal immediately -- that's a too big side-effect for a load.

[Darksonn]

True, it's not entirely the same.

[Diggsey]

elem itself should also get that treatment though.

Why would elem need that treatment? Its provenance is never in doubt.

Imagine we had a magic defer_provenance_until_cas() operator which could be applied to the result of a load to split that load into two components:

1. Load the address
2. At the next CAS operation, also load the provenance for (1) and apply it everywhere the loaded address was used, in the same atomic operation as the CAS so there is no race.

let elem = malloc();
elem.next = defer_provenance_until_cas(STACK_TOP.load(Acquire));
while let Err(new_next) = STACK_TOP.cas(elem.next, elem, AcqRel) {
    elem.next = defer_provenance_until_cas(new_next);
}

I think this code would clearly be valid without needing any special treatment for elem. I would argue that erase_provenance is equivalent to this magic operator.

However, now each load becomes a possible "expose", which kills this proposal immediately -- that's a too big side-effect for a load.

Perhaps with a small tweak it doesn't need to be an "expose" though:

let elem = malloc();
elem.next = erase_provenance(STACK_TOP.load(Acquire));
loop {
    match STACK_TOP.cas(elem.next, elem, AcqRel) {
        Ok(prev) => {
            expose_addr(prev);
            break;
        }
        Err(new_next) => {
            elem.next = erase_provenance(new_next);
        }
    }
}

Now the expose is an explicit part of the algorithm, so loading a pointer with a "cleared provenance" doesn't require exposing the address of that pointer, it only requires the "from_exposed_addr" part.

[Diggsey]

I have just realised that this does introduce a race condition if the pointer is loaded before the previous address is exposed, so exposing the address would have to be an atomic part of the CAS operation, rather than something done explicitly as part of the algorithm.

I think the above example is still useful to explain what I'm suggesting though.

[comex]

Out of curiosity, does a CAS on CHERI take into account the permissions on the pointer?

On Morello at least, the manual says the capability has to be bitwise identical for CAS to succeed, which I'd assume means the entire 129 bits including address, metadata, and valid bit (tag).

In other words, in practice, this kind of stack should 'just work' on CHERI… as long as you use pointer types. Which makes me skeptical of the idea of recommending usize instead.

However, even on CHERI this would be a problem from an Abstract Machine perspective, since even two bitwise-identical capabilities may not have the same abstract provenance. (If I understand correctly, the original example wouldn't work as-is, because a CHERI allocator isn't supposed to reuse memory before tag-GC clears the valid bits of all dangling pointers. But I think you can encounter a similar problem without involving the allocator?)

Which makes me also skeptical of solutions that rely on expose_addr and from_exposed_addr, whether implicitly or explicitly, because those primitives don't exist on CHERI.

But perhaps the Abstract Machine could add some sort of weaker equivalent of expose_addr/from_exposed_addr that only works for capabilities that are already fully equal from a hardware perspective?

[RalfJung]

Why would elem need that treatment? Its provenance is never in doubt.

I was thinking it's needed in preparation for the next push. But maybe that's not actually the case.

apply it everywhere the loaded address was used

That's a frighteningly global operation. How is "address was used" even defined? It's an integer, it doesn't have provenance, so we can't determine where this value has flowed.

I wonder though... instead of "everywhere it was used", at least for this particular operation we'd actually just have to put it in one place: elem.next. So what if the CAS took a mutable pointer to the "current" value for the comparison, and then it atomically does this

• Compare the address of the new value with the address stored in STACK_TOP.
• If they are inequal, return Err.
• If they are equal, then take the provenance of the pointer stored in STACK_TOP and store it behind that pointer.

This would ensure that right after a successful CAS, the value in STACK_TOP (which did not change) and the value in elem.next would indeed be fully equal (equal address and equal provenance). So I think it completely fixes this particular algorithm?

However I am concerned that this is fixing a special case instead of a larger problem. That said, the fact that this ensures "after CAS the two values are momentarily equal" does seem like more than just a band-aid.

[RalfJung]

However I am concerned that this is fixing a special case instead of a larger problem. That said, the fact that this ensures "after CAS the two values are momentarily equal" does seem like more than just a band-aid.

I was told there are more examples in https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1726r5.pdf, but I have not yet taken a closer look.

[chorman0773]

I have seen a proposal to fix this for C++ with some sot of operation that "refreshes the provenance of a pointer and every other pointer reachable through it". That operation sounds like a nightmare for program verification since it can change state that is very far away from where that operation happens; we don't currently have any operation that reaches transitively through pointers and I think that kind of locality is important.

This sounds like std::launder, which was added in C++17.