6 ms·

Solving the ABA Problem in Rust with Tagged Pointers

41 points by todsacerdoti 2y ago

Phelinofist 2y ago
Can't the ABA problem circumvented quite easily by making the shared state immutable? Every modification will create a new instance, like so (in JAVA): class State { private int value; private String anotherValue; State(int value, String anotherValue) { this.value = value; this.anotherValue = anotherValue; } State changeValue(int newValue) { return new State(newValue, anotherValue); } // same for anotherValue } AtomicReference<State> state = new AtomicReference<>(new State(1, "a"); State oldState; State newState; for(;;) { oldState = this.state.get(); newState = oldState.changeValue(2); if(this.state.compareAndSet(oldState, newState)) { break; } } Since object identity is used for comparison, and every transition is a new object, the ABA problem cannot happen because - even if the state are equal - the comparison will fail.
- whizzter 2y ago
  In Java if you hold an reference to an "old" object then that will be kept alive until all references are exhausted, thus an identity comparison comparing pointers will never succeed as long as someone holds an reference (that is compared to). In languages with more manual management, the pointer itself if used can be reused and succeed in bad cases (though from my cursory knowledge of Rust this seems to indicate quite a bit of unsafe behaviours).
- wat10000 2y ago
  The problem isn’t the mutability of the State object, but the mutability of the pointer to it. Your approach works in Java, but it only works if you have a garbage collector that can ensure the memory is not freed until there are no extant pointers to it, or you never free the objects. The ABA problem occurs when one writer reads the old pointer, another writer swaps out the pointer and frees the old object, a third writer allocates a new object that happens to be placed at the exact same location as the first one, then the first writer does its compare-and-swap.
- gpderetta 2y ago
  In any language with GC, a lot of complex concurrency problems become much simpler (but of course now you have to deal with the GC).
amluto 2y ago
The tagged pointer example says, in the safety notes: > Pointer Dereferencing: Pointers are only dereferenced after successful CAS operations I think a rather stronger argument should be needed. But the code doesn’t even follow what the notes say: let current = self.head.load(Ordering::Acquire); if current.ptr.is_null() { return None; } let next = unsafe { (*current.ptr).next }; No CAS. And this sure looks wrong — the current head could be popped and freed before being dereferenced. edit: put the correct code in. Thanks, LegionMammal978
- LegionMammal978 2y ago
  Those lines don't actually dereference anything, except for (*new_node) which is owned by the function. Immediately following them is the CAS to ensure that current is still at self.head. If it gets deallocated, then the CAS fails, and it tries again with the new self.head.
  - amluto 2y ago
    Whoops, I pasted entirely the wrong code! let current = self.head.load(Ordering::Acquire); if current.ptr.is_null() { return None; } let next = unsafe { (*current.ptr).next }; On the one hand, one might say “well, it’s fine if we read the wrong value here if the old head was popped in the mean time”, but it’s still UB, and it can even segfault if the old head is freed and unmapped.
    - empath75 2y ago
      Miri does catch a problem here: > error: Undefined Behavior: memory access failed: expected a pointer to 8 bytes of memory, but got 0x2f5f40[noalloc] which is a dangling pointer (it has no provenance) --> src/main.rs:263:33 | 263 | let next = unsafe { (*current.ptr).next }; | ^^^^^^^^^^^^^^^^^^^ memory access failed: expected a pointer to 8 bytes of memory, but got 0x2f5f40[noalloc] which is a dangling pointer (it has no provenance) | = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html https://doc.rust-lang.org/nightly/reference/behavior-conside... for further information = note: BACKTRACE on thread `unnamed-2`: = note: inside `LockFreeStack::pop` at src/main.rs:263:33: 263:52
LegionMammal978 2y ago
The slotmap crate [0], which stores an unordered object list in a Vec with persistent indices, implements a similar tagging scheme to avoid ABA problems. It's neat to see how this can be applied to raw pointers as well. [0] https://docs.rs/slotmap/latest/slotmap/ https://docs.rs/slotmap/latest/slotmap/
drivebyhooting 2y ago
For 32bit or 64bit tagged pointer is there a big risk of version overflow?
- convolvatron 2y ago
  oh certainly. this is one of those slightly unsatisfactory consistency stories where its not a closed answer, its just arbitrarily unlikely that a conflict will arise. we've already got a _really_ small window where one thread has the old pointer and the other thread frees it, it goes through the heap, and is assigned the same address as the old version. now exponentiate the likelihood of that happening with the size of the tag space.
  - gpderetta 2y ago
    You just need to make it less likely than random RAM corruption:)
  - amluto 2y ago
    > we've already got a _really_ small window where one thread has the old pointer and the other thread frees it, it goes through the heap, and is assigned the same address as the old version Plenty of allocator implementations will do this, very efficiently, almost deterministically reusing the same address, if you free and then allocate something of similar size.
- Someone 2y ago
  There’s a risk, but far from a big one. You’d need exactly 2³² or even 2⁶⁴ pointer updates (or a multiple of it) between the time you read the pointer and the time you try writing it for running into problems. That’s not likely to be a problem even on a 1000-core CPU. So, technically, this isn’t solving the ABA problem, it’s just hiding it very, very well.
damon_dam 2y ago
A much better solution to the ABA problem is to use load-linked and store-conditional instructions [1] on platforms where they are available (ARM, RISC-V, etc.) Unfortunately x86 is not one of them. That's when CMPXCHG16B on x86-64 comes in handy, as per the linked article. But if you're going to write library code in 2025, it should at least support x86 and ARM. Which brings up a more interesting argument IMO: platform fragmentation. Rust has approximately 1.5 advantages over C/C++. To displace them in a reasonable time, it probably needed 4 or 5. Its most significant contribution for the foreseeable future is platform fragmentation. [1] https://en.wikipedia.org/wiki/Load-link/store-conditional https://en.wikipedia.org/wiki/Load-link/store-conditional
- explodingwaffle 2y ago
  Who says you can’t make a library that does both? Rust makes it pretty easy to conditionally compile code based on architecture. It could even be possible to make some sort of “ABA primitive” and use that for these sort of data structures. This could well exist: I’ve not looked. These sorts of things really aren’t that common in my experience. On LR/SC: to any atomics experts listening, isn’t it technically “obstruction-free” (as per the Wikipedia definitions at least) rather than lock-free? (though in practice this makes basically no difference and still counts as lock-free in the C++ (and Rust) sense) Just something that stuck out last time I got sucked into this rabbit hole.
  - damon_dam 2y ago
    > Who says you can’t make a library that does both? Of course you can. I just meant that the linked article didn't. > On LR/SC: to any atomics experts listening, isn’t it technically “obstruction-free” (as per the Wikipedia definitions at least) rather than lock-free? The better criterion IMO is loop-free, which makes it a little easier to understand. Consider the following spin-locking code (with overabundant memory barriers): do { p = *a; } while (p == 0x1 || !atomic_compare_and_swap(p, 0x1, a)); memory_barrier(); // do stuff that looks at *p q->next = p; memory_barrier(); atomic_store(q, a); Here's the equivalent LL/SC version: do { p = ll(a); memory_barrier(); // do stuff that looks at *p q->next = p; memory_barrier(); } while (!sc(q, a)); The pointer-tagging version is also obviously not loop-free. Which is faster, in which cases, and by how much? The oversimplified answer is that LL/SC is probably slightly faster than spin-locking on most platforms and cases, but pointer-tagging might not be.
catlifeonmars 2y ago
What was surprising to me here is that two threads share the same stack. Is this a rust thing or is this common in programming languages?
- wrs 2y ago
  This is about “stack”, the general purpose data structure, not “stack”, the place in memory you put local variables.

41 points by todsacerdoti 2y ago

Can't the ABA problem circumvented quite easily by making the shared state immutable? Every modification will create a new instance, like so (in JAVA): class State { private int value; private String anotherValue; State(int value, String anotherValue) { this.value = value; this.anotherValue = anotherValue; } State changeValue(int newValue) { return new State(newValue, anotherValue); } // same for anotherValue } AtomicReference<State> state = new AtomicReference<>(new State(1, "a"); State oldState; State newState; for(;;) { oldState = this.state.get(); newState = oldState.changeValue(2); if(this.state.compareAndSet(oldState, newState)) { break; } } Since object identity is used for comparison, and every transition is a new object, the ABA problem cannot happen because - even if the state are equal - the comparison will fail.

whizzter 2y ago
In Java if you hold an reference to an "old" object then that will be kept alive until all references are exhausted, thus an identity comparison comparing pointers will never succeed as long as someone holds an reference (that is compared to). In languages with more manual management, the pointer itself if used can be reused and succeed in bad cases (though from my cursory knowledge of Rust this seems to indicate quite a bit of unsafe behaviours).
wat10000 2y ago
The problem isn’t the mutability of the State object, but the mutability of the pointer to it. Your approach works in Java, but it only works if you have a garbage collector that can ensure the memory is not freed until there are no extant pointers to it, or you never free the objects. The ABA problem occurs when one writer reads the old pointer, another writer swaps out the pointer and frees the old object, a third writer allocates a new object that happens to be placed at the exact same location as the first one, then the first writer does its compare-and-swap.
gpderetta 2y ago
In any language with GC, a lot of complex concurrency problems become much simpler (but of course now you have to deal with the GC).

amluto 2y ago

The tagged pointer example says, in the safety notes: > Pointer Dereferencing: Pointers are only dereferenced after successful CAS operations I think a rather stronger argument should be needed. But the code doesn’t even follow what the notes say: let current = self.head.load(Ordering::Acquire); if current.ptr.is_null() { return None; } let next = unsafe { (*current.ptr).next }; No CAS. And this sure looks wrong — the current head could be popped and freed before being dereferenced. edit: put the correct code in. Thanks, LegionMammal978

LegionMammal978 2y ago
Those lines don't actually dereference anything, except for (*new_node) which is owned by the function. Immediately following them is the CAS to ensure that current is still at self.head. If it gets deallocated, then the CAS fails, and it tries again with the new self.head.
- amluto 2y ago
  Whoops, I pasted entirely the wrong code! let current = self.head.load(Ordering::Acquire); if current.ptr.is_null() { return None; } let next = unsafe { (*current.ptr).next }; On the one hand, one might say “well, it’s fine if we read the wrong value here if the old head was popped in the mean time”, but it’s still UB, and it can even segfault if the old head is freed and unmapped.
  - empath75 2y ago
    Miri does catch a problem here: > error: Undefined Behavior: memory access failed: expected a pointer to 8 bytes of memory, but got 0x2f5f40[noalloc] which is a dangling pointer (it has no provenance) --> src/main.rs:263:33 | 263 | let next = unsafe { (*current.ptr).next }; | ^^^^^^^^^^^^^^^^^^^ memory access failed: expected a pointer to 8 bytes of memory, but got 0x2f5f40[noalloc] which is a dangling pointer (it has no provenance) | = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html https://doc.rust-lang.org/nightly/reference/behavior-conside... for further information = note: BACKTRACE on thread `unnamed-2`: = note: inside `LockFreeStack::pop` at src/main.rs:263:33: 263:52

LegionMammal978 2y ago

The slotmap crate [0], which stores an unordered object list in a Vec with persistent indices, implements a similar tagging scheme to avoid ABA problems. It's neat to see how this can be applied to raw pointers as well. [0] https://docs.rs/slotmap/latest/slotmap/ https://docs.rs/slotmap/latest/slotmap/

drivebyhooting 2y ago

For 32bit or 64bit tagged pointer is there a big risk of version overflow?

convolvatron 2y ago
oh certainly. this is one of those slightly unsatisfactory consistency stories where its not a closed answer, its just arbitrarily unlikely that a conflict will arise. we've already got a _really_ small window where one thread has the old pointer and the other thread frees it, it goes through the heap, and is assigned the same address as the old version. now exponentiate the likelihood of that happening with the size of the tag space.
- gpderetta 2y ago
  You just need to make it less likely than random RAM corruption:)
- amluto 2y ago
  > we've already got a _really_ small window where one thread has the old pointer and the other thread frees it, it goes through the heap, and is assigned the same address as the old version Plenty of allocator implementations will do this, very efficiently, almost deterministically reusing the same address, if you free and then allocate something of similar size.
Someone 2y ago
There’s a risk, but far from a big one. You’d need exactly 2³² or even 2⁶⁴ pointer updates (or a multiple of it) between the time you read the pointer and the time you try writing it for running into problems. That’s not likely to be a problem even on a 1000-core CPU. So, technically, this isn’t solving the ABA problem, it’s just hiding it very, very well.

damon_dam 2y ago

A much better solution to the ABA problem is to use load-linked and store-conditional instructions [1] on platforms where they are available (ARM, RISC-V, etc.) Unfortunately x86 is not one of them. That's when CMPXCHG16B on x86-64 comes in handy, as per the linked article. But if you're going to write library code in 2025, it should at least support x86 and ARM. Which brings up a more interesting argument IMO: platform fragmentation. Rust has approximately 1.5 advantages over C/C++. To displace them in a reasonable time, it probably needed 4 or 5. Its most significant contribution for the foreseeable future is platform fragmentation. [1] https://en.wikipedia.org/wiki/Load-link/store-conditional https://en.wikipedia.org/wiki/Load-link/store-conditional

explodingwaffle 2y ago
Who says you can’t make a library that does both? Rust makes it pretty easy to conditionally compile code based on architecture. It could even be possible to make some sort of “ABA primitive” and use that for these sort of data structures. This could well exist: I’ve not looked. These sorts of things really aren’t that common in my experience. On LR/SC: to any atomics experts listening, isn’t it technically “obstruction-free” (as per the Wikipedia definitions at least) rather than lock-free? (though in practice this makes basically no difference and still counts as lock-free in the C++ (and Rust) sense) Just something that stuck out last time I got sucked into this rabbit hole.
- damon_dam 2y ago
  > Who says you can’t make a library that does both? Of course you can. I just meant that the linked article didn't. > On LR/SC: to any atomics experts listening, isn’t it technically “obstruction-free” (as per the Wikipedia definitions at least) rather than lock-free? The better criterion IMO is loop-free, which makes it a little easier to understand. Consider the following spin-locking code (with overabundant memory barriers): do { p = *a; } while (p == 0x1 || !atomic_compare_and_swap(p, 0x1, a)); memory_barrier(); // do stuff that looks at *p q->next = p; memory_barrier(); atomic_store(q, a); Here's the equivalent LL/SC version: do { p = ll(a); memory_barrier(); // do stuff that looks at *p q->next = p; memory_barrier(); } while (!sc(q, a)); The pointer-tagging version is also obviously not loop-free. Which is faster, in which cases, and by how much? The oversimplified answer is that LL/SC is probably slightly faster than spin-locking on most platforms and cases, but pointer-tagging might not be.

catlifeonmars 2y ago

What was surprising to me here is that two threads share the same stack. Is this a rust thing or is this common in programming languages?

wrs 2y ago
This is about “stack”, the general purpose data structure, not “stack”, the place in memory you put local variables.