Array#map is vulnerable to concurrent mutation

[straight-shoota]

Array#map(&) yields each element to transform it in the block. If the block performs mutating operations on the array, it can lead to invalid memory access or corrupted data.
The same applies to Array#map_with_index, and I mean both when I refer to #map.

This is discussed as an example in https://forum.crystal-lang.org/t/safety-guarantees-of-stdlib-data-structures/7364

A simple reproduction of an example with data corruption:

ary = [1, 2, 3]

ary.map do |e|
  ary.pop if e == 1
  e
end # => [1, 2, 0]

The cause is that Array#map expects size to be static during its runtime. While this is generally a reasonable expectation, it's impossible to exclude that the block mutates the array's size.

Array#map is an optimized override. The base implementation of Enumerable#map does not have this bug because it does not assume any size. It grows the buffer on demand.

The easiest solution is to drop the implementation of Array#map in order to fall back to Enumerable#map. We can still optimize a bit by using the current size as size hint because usually it's gonna be stable.

[yxhuvud]

Actually modifying an array while iterating it has very few if any actual use cases (or the issues would have shown up a lot earlier). Could it be considered to instead simply forbid modifying the array during iteration? I feel it would be a shame to pay a performance price for something that isn't really how people normally use the thing.

One way to implement that would be to use an rw_lock, though perhaps with a variant that raises if it fails to grab the write lock immediately.

Upside: Would cost a lot less performance as it is only done once per iteration
Downside: would use a tiny bit more memory.
Downside: Would disallow actually doing code like that. Not much of a downside.
Downside: The cost of element deletion would be slightly higher.

Thoughts?

[straight-shoota]

This is definitely worth considering.
But it's hard to see a net positive effect on performance because the scope is much larger than affecting just #map.

Such a protection must cover all operation that can potentially invalidate the buffer range. That's most mutating methods on Array except those that only perform substitution. And probably these methods are used magnitudes more often than #map.

[ysbaddaden]

As outlined by @BlobCodes, Java throws a ConcurrentModificationException exception when it detects a concurrent iterate/mutate situation (no guarantee: it's a best effort).

[crysbot]

This issue has been mentioned on Crystal Forum. There might be relevant details there:

https://forum.crystal-lang.org/t/safety-guarantees-of-stdlib-data-structures/7364/17

[straight-shoota]

The mention of ConcurrentModificationException has brought me to this previous thread: https://forum.crystal-lang.org/t/raise-if-containers-accessed-while-being-changed/3937

[straight-shoota]

Golang detects concurrent modification on map. It does so using a single bit flag. Interestingly it's not even atomic, so one should call it "best effort" as well I suppose.

https://github.com/golang/go/blob/635c2dce04259f2c84aeac543f0305b3e7c8ed7b/src/internal/runtime/maps/map.go#L231-L235

[straight-shoota]

Considering that both Go and Java have a protection mechanism to detect concurrent modifications in generic data structures, the trade-off seems to be worthwile.

A major benefit is of course that it also triggers at least for some types of parallel modifications. So it would have a relevant effect thread safety, to error gracefully instead of ending up with corrupted data or a segfault.

[straight-shoota]

Digging a bit into the mechanisms in Go and Java it turns out their implementations - and apparently purposes - are quite different.

Go uses a boolean flag which indicates whether a modification is currently happening. It's set via XOR which according to the doc comment should make it likely that if two fibers both try to mutate simultaneously, both notice the collision.
Detection is not a safe guarantee though, just a high probability. I'm not sure why it's not an atomic, but probably to avoid the overhead and the XOR solution is considered good enough.

This protects the integrity of the data structure itself, but not any assumptions about structural stability as would be necessary for the #map use case.

Java on the other hand uses a variable modCount to count structural modifications. It bumps every time the structure of the collection changes (e.g. items added or deleted). Iterators over the collection hold a reference to the modCounter at its creation time and compare it to the current value on each iteration step. A difference means the collection was modified since the iterator's creation and thus it becomes invalid and errors upon access. This mechanism would also fit for the #map use case.

I suppose this could also be used to detect simultaneous modifications, at least after the fact: Before a method does a structural modification, it takes a snapshot of the current modCount. If it differs after applying the change, there has been concurrent modification and the data can be corrupted. It's unclear what should happen then, though. The damage is done and "just" raising an exception won't prevent other fibers from seeing an invalid state. The only safe course of action is to exit the program🤷
According to Java documentation modCount is only used to ensure iterators are in sync.

It might be possible to combine both approaches into a single variable, a modification counter where one bit indicates whether someone is currently writing. 🤔

[oprypin]

Thanks for the description of approaches in Go and Java. They sound nice.

I think the approaches that detect concurrent modification after the fact are just fine.
Their goal isn't to prevent any bug from happening even once, it's to prevent them from being unnoticed and shipped to users.
The expected action isn't to try to recover from the error, it's to go back to the source code and rework it.