The article is a bit more subtle than the title suggests:
Smart pointers don’t solve iterator invalidation.
Iterator invalidation is a very hard problem. GC’d languages can have memory-safe iterator invalidation problems that cause surprising behaviour. If you have a tree of buckets and deletion causes a bucket to be disconnected from the tree, then your iterator can keep holding a reference to that bucket but now can’t find the next bucket and will do the wrong thing.
You could implement memory-safe but not mutation-safe iterators in C++ in a few ways. For example, imagine if std::vector used a std::shared_ptr to its underlying buffer and represented iterators as a std::shared_ptr to the same buffer and an index. Insertion may cause the buffer to be reallocated but you will keep iterating over the range.
I have never been a fan of how C++ uses iterators. They are disconnected from the underlying type. Objective-C’s fast enumeration protocol is interesting. You pass the collection a structure for storing iteration state (which includes a buffer for storing objects) and it populates this with a pointer to a buffer, a length, and a pointer to mutation state. Normally this is implemented by a version counter in the collection that is incremented on mutations that would invalidate iterators. Iteration is a thing that collections do, rather than iterators being a thing that visits a collection.
Rust solves this by preventing mutation of the data structure while iterators exist. I can’t remember the details, but I think this also precludes some safe operations (for example, in C++ it’s fine to mutate elements, swap elements around, or replace an element in a collection it just isn’t safe to change the shape of the collection itself).
Swift, I believe, solves this by making most collections immutable CoW, so you can mutate a CoW copy of a collection during iteration and that’s fast, but you can never modify the original collection (though you can then replace the old collection with your new CoW copy and free the old one, which may or may not involve actually freeing any memory).
It’s pretty cool how many things lifetimes + borrowing fix from general rules.
Rust doesn’t have anything special for iterators. It fixes the problem by having lifetimes (the iterator can’t outlive the collection) and shared-immutable vs exclusive-mutable access. While the iterator borrows for shared access, you can’t move or mutate the collection. When iterator borrows mutably, it gets exclusive access. Mutable iterators can hand out mutable references, so you can still swap elements while you iterate, in some cases.
Locked MutexGuard borrows from Mutex<T>, and you borrow &T from the MutexGuard. It naturally ensures that the mutex can’t be destroyed while anything has a lock on it, and bare &T reference can’t be used after the mutex is locked again. This works even tough Rust-the-language has no idea what locks are.
There’s even wacky Cell magic you can use to modify elements while you iterate over the collection, even if the collection itself doesn’t use Cell (playground link):
let mut v = vec![1, 1, 1, 1, 1];
let slice = Cell::from_mut(&mut v[..]).as_slice_of_cells();
for (i, e) in slice.into_iter().enumerate() {
for j in i..slice.len() {
slice[j].set(slice[j].get() * 2);
}
print!("{} ", e.get());
}
println!();
That prints “2 4 8 16 32”. I could totally imagine &Cell<T> being a first-class Rust reference type, in the same way that &pinned T might be someday. It’s not at all clear to me that it would actually be worth its weight as a feature, but I think it’s neat.
This is pretty neat! But it relies on the fact that you can borrow Vec as just a plain slice, right? So you can use as_slice_of_cells.
For a more complex collection like a tree, I think you would either have to make the Cell part of the datastructure or to extend Cell with a as_tree_of_cells function. Or maybe some advanced GhostCell shenanigans?
Yeah some sort of cast from &mut Collection<T> to &Collection<Cell<T>>. I’m not sure how to make that generic. The expensive approach that works today is to build a whole new collection of references:
let mut set1 = BTreeMap::new();
for i in 0..10 {
set1.insert(i, i);
}
let mut set2 = BTreeMap::new();
for (&i, val) in &mut set1 {
set2.insert(i, Cell::from_mut(val));
}
Rust solves this by preventing mutation of the data structure while iterators exist. I can’t remember the details, but I think this also precludes some safe operations
Rust has two separate problems to worry about here. The first is whether resizing a collection might invalidate iterators, as in C++. The second is whether iterators could be used to violate the no-mutable-aliasing rules in any way. I think the second thing ends up being a stricter requirement than the first thing in most (all?) cases. It can be confusing because mutable aliasing violations “feel” safe, in that they are mostly legal in C/C++, but they are genuinely unsound in Rust, because of all the no-alias annotations the compiler passes to LLVM.
You can disentangle the mutability of the collection itself from the mutability of the values inside by adding interior mutability -so Collection<Cell<T>> or Collection<Mutex<T>> for example. Then, you can borrow and iterate over the collection immutably but get mutable access to its element from the iterator.
Yes- though those two things are intertwined, because the no-mutable-aliasing rule is the very same mechanism that prevents you from resizing the vector while iterating over it.
If you had a more relaxed rule that just tried to prevent iterator invalidation, but it didn’t prevent you from getting mutable aliases to its elements, you could turn around and use a Vec<Vec<T>> to invalidate an iterator into an inner Vec.
Maybe we should add Iterator management as a third (fourth?) hard thing in computer science.
I keep running into it (just last week in fact) as part of implementing notifications: this object has a list of observers, and when its state changes it has to iterate that list and call all the observers. Only it’s entirely possible that one of those callbacks will remove the observer from my list. Plus this has to be thread-safe…
(Note that invalidating the Iterator won’t help here. It has to be possible to add/remove observers in a re-entrant call during iteration. I’ve taken to copying the list and iterating the copy, but that has some undesirable behaviors with multiple threads, to wit, an observer can be called after it’s been removed.)
It’s very common in C++ to implement something that’s really an ad-hoc monad for these things: iterate over a collection and build a list of changes that you want to apply, then apply the changes. Haskell programmers probably laugh at us.
Or the crazy erase(remove_if( pattern where it moves all of the “don’t need to be erased” elements to the start of the list and returns an iterator to the first element to remove… and if you happen to forget that you have to call it like foo.erase(remove_if(…), foo.end()) and accidentally call foo.erase(remove_if(…)) you end up calling a valid overload of erase() that doesn’t at all do what you expect…
I feel like iterator difficulties are mostly tied to concurrent access/write problems. It is all in the same “context” but in fact, you can see how it “leaks”.
Some llvm data structures utilize DebugEpochBase to detect mismatching iterators with the parent container.
While the message is simpler than libstdc++’s -D_GLIBCXX_DEBUG , it is quite ok.
This is a fundamental lifetime error, it is not something that hardening could find. Even a debug build that was not constrained to ABI or source compatibility would basically be dependent on an iterator that stored a reference to the target vector and checked on every use that the vector had not changed.
For view types like span and string_view it’s because there’s no way to know the origin of a buffer.
Hardening APIs is a best effort to mitigate the harm given the triviality of errors otherwise, but it can’t fix core language problems like inadequate object lifetime management.
I understand. I was just pointing out that I’d filed it given -D_GLIBCXX_DEBUG did find one particular case (and I don’t like it when people don’t cross-link), but I’d forgotten that libc++‘s equivalent doesn’t break ABI.
I certainly didn’t make any claims about it fixing core language problems, either. I did say “one of the examples” for a reason but perhaps wasn’t explicit enough.
Sorry I didn’t realise the libstdc++ equivalent permitted abi breakage which does let you catch some cases not possible under the libc++ hardening model.
I was explaining why libc++ didn’t (and couldn’t) catch that issue and hence it wasn’t a “bug” under the libc++ model of hardening.
I’m sorry if I came over harsher than I intended to :(
Thanks! By the way, do you have any idea about the ASan footnote? I’m quite surprised that it doesn’t see the dangling lock_guard issue. It does see it if I call ->unlock() by hand.
When you call ->unlock by hand, you’re essentially calling pthread_mutex_unlock(nullptr). That is guaranteed to crash, and this is what ASAN reports: a crash inside libpthread.
When you use the lock_guard, the address of the mutex is passed directly to pthread_mutex_lock/unlock, and is not reloaded. So depending on your memory allocator whatever pthread_mutex_unlock does, which ASAN doesn’t have visibility into, won’t crash.
TSan works because presumably it replaces regular pthreads by its own instrumentation around it.
The article is a bit more subtle than the title suggests:
Smart pointers don’t solve iterator invalidation.
Iterator invalidation is a very hard problem. GC’d languages can have memory-safe iterator invalidation problems that cause surprising behaviour. If you have a tree of buckets and deletion causes a bucket to be disconnected from the tree, then your iterator can keep holding a reference to that bucket but now can’t find the next bucket and will do the wrong thing.
You could implement memory-safe but not mutation-safe iterators in C++ in a few ways. For example, imagine if
std::vectorused astd::shared_ptrto its underlying buffer and represented iterators as astd::shared_ptrto the same buffer and an index. Insertion may cause the buffer to be reallocated but you will keep iterating over the range.I have never been a fan of how C++ uses iterators. They are disconnected from the underlying type. Objective-C’s fast enumeration protocol is interesting. You pass the collection a structure for storing iteration state (which includes a buffer for storing objects) and it populates this with a pointer to a buffer, a length, and a pointer to mutation state. Normally this is implemented by a version counter in the collection that is incremented on mutations that would invalidate iterators. Iteration is a thing that collections do, rather than iterators being a thing that visits a collection.
Rust solves this by preventing mutation of the data structure while iterators exist. I can’t remember the details, but I think this also precludes some safe operations (for example, in C++ it’s fine to mutate elements, swap elements around, or replace an element in a collection it just isn’t safe to change the shape of the collection itself).
Swift, I believe, solves this by making most collections immutable CoW, so you can mutate a CoW copy of a collection during iteration and that’s fast, but you can never modify the original collection (though you can then replace the old collection with your new CoW copy and free the old one, which may or may not involve actually freeing any memory).
It’s pretty cool how many things lifetimes + borrowing fix from general rules.
Rust doesn’t have anything special for iterators. It fixes the problem by having lifetimes (the iterator can’t outlive the collection) and shared-immutable vs exclusive-mutable access. While the iterator borrows for shared access, you can’t move or mutate the collection. When iterator borrows mutably, it gets exclusive access. Mutable iterators can hand out mutable references, so you can still swap elements while you iterate, in some cases.
Locked
MutexGuardborrows fromMutex<T>, and you borrow&Tfrom theMutexGuard. It naturally ensures that the mutex can’t be destroyed while anything has a lock on it, and bare&Treference can’t be used after the mutex is locked again. This works even tough Rust-the-language has no idea what locks are.There’s even wacky
Cellmagic you can use to modify elements while you iterate over the collection, even if the collection itself doesn’t useCell(playground link):That prints “2 4 8 16 32”. I could totally imagine
&Cell<T>being a first-class Rust reference type, in the same way that&pinned Tmight be someday. It’s not at all clear to me that it would actually be worth its weight as a feature, but I think it’s neat.This is pretty neat! But it relies on the fact that you can borrow
Vecas just a plain slice, right? So you can useas_slice_of_cells.For a more complex collection like a tree, I think you would either have to make the
Cellpart of the datastructure or to extendCellwith aas_tree_of_cellsfunction. Or maybe some advancedGhostCellshenanigans?Yeah some sort of cast from
&mut Collection<T>to&Collection<Cell<T>>. I’m not sure how to make that generic. The expensive approach that works today is to build a whole new collection of references:Rust has two separate problems to worry about here. The first is whether resizing a collection might invalidate iterators, as in C++. The second is whether iterators could be used to violate the no-mutable-aliasing rules in any way. I think the second thing ends up being a stricter requirement than the first thing in most (all?) cases. It can be confusing because mutable aliasing violations “feel” safe, in that they are mostly legal in C/C++, but they are genuinely unsound in Rust, because of all the no-alias annotations the compiler passes to LLVM.
You can disentangle the mutability of the collection itself from the mutability of the values inside by adding interior mutability -so
Collection<Cell<T>>orCollection<Mutex<T>>for example. Then, you can borrow and iterate over the collection immutably but get mutable access to its element from the iterator.Yes- though those two things are intertwined, because the no-mutable-aliasing rule is the very same mechanism that prevents you from resizing the vector while iterating over it.
If you had a more relaxed rule that just tried to prevent iterator invalidation, but it didn’t prevent you from getting mutable aliases to its elements, you could turn around and use a
Vec<Vec<T>>to invalidate an iterator into an innerVec.Very true. My favorite example of this is using an enum, because you don’t even need heap allocation to do it: https://stackoverflow.com/a/67608729/823869
Maybe we should add Iterator management as a third (fourth?) hard thing in computer science.
I keep running into it (just last week in fact) as part of implementing notifications: this object has a list of observers, and when its state changes it has to iterate that list and call all the observers. Only it’s entirely possible that one of those callbacks will remove the observer from my list. Plus this has to be thread-safe…
(Note that invalidating the Iterator won’t help here. It has to be possible to add/remove observers in a re-entrant call during iteration. I’ve taken to copying the list and iterating the copy, but that has some undesirable behaviors with multiple threads, to wit, an observer can be called after it’s been removed.)
It’s very common in C++ to implement something that’s really an ad-hoc monad for these things: iterate over a collection and build a list of changes that you want to apply, then apply the changes. Haskell programmers probably laugh at us.
Or the crazy
erase(remove_if(pattern where it moves all of the “don’t need to be erased” elements to the start of the list and returns an iterator to the first element to remove… and if you happen to forget that you have to call it likefoo.erase(remove_if(…), foo.end())and accidentally callfoo.erase(remove_if(…))you end up calling a valid overload oferase()that doesn’t at all do what you expect…Not that I’ve been burned before…
I feel like iterator difficulties are mostly tied to concurrent access/write problems. It is all in the same “context” but in fact, you can see how it “leaks”.
Whenever I see this sort of discussion, I’m reminded of Manish Goregaokar’s The Problem With Single-threaded Shared Mutability from 2015… though it references earlier things like Niko Matsakis’s On the connection between memory management and data-race freedom from 2013.
Some llvm data structures utilize
DebugEpochBaseto detect mismatching iterators with the parent container. While the message is simpler than libstdc++’s -D_GLIBCXX_DEBUG , it is quite ok.FWIW, I filed https://github.com/llvm/llvm-project/issues/128627 based on libc++’s hardening/debug machinery not finding one of the examples.
This is a fundamental lifetime error, it is not something that hardening could find. Even a debug build that was not constrained to ABI or source compatibility would basically be dependent on an iterator that stored a reference to the target vector and checked on every use that the vector had not changed.
For view types like span and string_view it’s because there’s no way to know the origin of a buffer.
Hardening APIs is a best effort to mitigate the harm given the triviality of errors otherwise, but it can’t fix core language problems like inadequate object lifetime management.
I understand. I was just pointing out that I’d filed it given
-D_GLIBCXX_DEBUGdid find one particular case (and I don’t like it when people don’t cross-link), but I’d forgotten that libc++‘s equivalent doesn’t break ABI.I certainly didn’t make any claims about it fixing core language problems, either. I did say “one of the examples” for a reason but perhaps wasn’t explicit enough.
Sorry I didn’t realise the libstdc++ equivalent permitted abi breakage which does let you catch some cases not possible under the libc++ hardening model.
I was explaining why libc++ didn’t (and couldn’t) catch that issue and hence it wasn’t a “bug” under the libc++ model of hardening.
I’m sorry if I came over harsher than I intended to :(
Thanks! By the way, do you have any idea about the ASan footnote? I’m quite surprised that it doesn’t see the dangling lock_guard issue. It does see it if I call ->unlock() by hand.
When you call ->unlock by hand, you’re essentially calling pthread_mutex_unlock(nullptr). That is guaranteed to crash, and this is what ASAN reports: a crash inside libpthread.
When you use the lock_guard, the address of the mutex is passed directly to pthread_mutex_lock/unlock, and is not reloaded. So depending on your memory allocator whatever pthread_mutex_unlock does, which ASAN doesn’t have visibility into, won’t crash.
TSan works because presumably it replaces regular pthreads by its own instrumentation around it.
Oh of course. And yep, if I save the raw pointer before I reset(), it behaves just like the lock_guard.
I’ll update the sidenote to link to your comment :)
From what I understood, it is found by ASan, this is good enough for me.
ASan missed the last one! See sidenote 5. I really want to understand why.
I wonder if it’s because TSan affects the mutex implementation so the use-after-free disappears in a non-TSan build?