Thread-safety implications of using EqualityComparer<TValue>.Default in ConcurrentDictionary

[theodorzoulias]

Hi. Some time ago I posted an issue about the performance implications of using the default TValue comparer internally in the ConcurrentDictionary<TKey,TValue> collection. Recently I discovered that there is a thread-safety implication as well, so I would like to report it. The issue emerges under these conditions:

1. The TValue is a mutable type, and implements the IEquatable<T> interface or overrides the object.Equals method.
2. The Equals implementation depends on mutable fields of the type.
3. A TValue instance is mutated on one thread, while a concurrent AddOrUpdate operation runs on another thread.

In this case the Equals might see the TValue instance in a transitional/invalid state, and throw an exception (or other undefined behavior).

Below is a demonstration of this issue. The TValue is a Genome class that derives from the Queue<char>, and compares itself with other Genome instances with the SequenceEqual method. Two threads are using the AddOrUpdate to replace Genome instances in the dictionary, and then they take an exclusive lock on the returned Genome instance and mutate it. The result is an InvalidOperationException:

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

public class Program
{
    class Genome : Queue<char>, IEquatable<Genome>
    {
        public bool Equals(Genome other) => this.SequenceEqual(other);
    }

    public static void Main()
    {
        ConcurrentDictionary<int, Genome> dictionary = new();
        Thread[] threads = Enumerable.Range(1, 2).Select(i => new Thread(() =>
        {
            while (true)
            {
                Genome genome = dictionary.AddOrUpdate(1, _ => new(), (_, _) => new());
                lock (genome) genome.Enqueue('A');
            }
        })).ToArray();
        Array.ForEach(threads, t => t.Start());
        Array.ForEach(threads, t => t.Join());
    }
}

Output:

Unhandled exception. System.InvalidOperationException: Collection was modified; enumeration operation may not execute.
   at System.Collections.Generic.Queue`1.Enumerator.MoveNext()
   at System.Linq.Enumerable.SequenceEqual[TSource](IEnumerable`1 first, IEnumerable`1 second, IEqualityComparer`1 comparer)
   at System.Linq.Enumerable.SequenceEqual[TSource](IEnumerable`1 first, IEnumerable`1 second)
   at Program.Genome.Equals(Genome other)
   at System.Collections.Concurrent.ConcurrentDictionary`2.TryUpdateInternal(TKey key, Nullable`1 nullableHashcode, TValue newValue, TValue comparisonValue)
   at System.Collections.Concurrent.ConcurrentDictionary`2.AddOrUpdate(TKey key, Func`2 addValueFactory, Func`3 updateValueFactory)
   at Program.<>c__DisplayClass1_0.<Main>b__3()
   at System.Threading.Thread.StartCallback()

Online demo.

This looks to me like a valid/intended use of the ConcurrentDictionary<TKey,TValue> collection, but I might be wrong.

I experimented with the ImmutableDictionary<TKey,TValue> as well, expecting to be unaffected from this issue, but to my surprise it is affected as well (demo). This collection also makes calls to the EqualityComparer<TValue>.Default.Equals when it is updated atomically with the ImmutableInterlocked.AddOrUpdate API. At least the immutable dictionary is equipped with the WithComparers method, that allows to customize the valueComparer that is used internally by the collection.

I should clarify that the above example is contrived. I haven't been personally affected by this issue.

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

[eiriktsarpalis]

This looks like a variation on dotnet/runtime#84163, so I don't think there is much we could do that wouldn't be a breaking change. FWIW mutable types and optimistic transactions don't mix in my experience, I would probably have switched the example to use an immutable queue as its value type.

[theodorzoulias]

FWIW mutable types and optimistic transactions don't mix in my experience, I would probably have switched the example to use an immutable queue as its value type.

Using an ImmutableQueue<T> or ConcurrentQueue<T> as TValue doesn't reproduce the issue. The issue emerges only if the TValue is mutable and non-thread-safe. As long as the developer synchronizes all accesses to the mutable TValue instances, I would expect that the overall usage pattern should be safe.

[stephentoub]

As long as the developer synchronizes all accesses to the mutable TValue instances, I would expect that the overall usage pattern should be safe.

But in the example the developer is not doing so. The dev is calling AddOrUpdate, which needs to do a comparison, and is concurrently mutating the value that needs to be compared. It's no different than if you replaced the AddOrUpdate with a direct call to SequenceEqual or to the value's Equal, outside of the custom lock on the instance that's protecting the mutation but not the read.

So I'm not sure what this issue is trying to achieve. Are you asking for the docs to be more explicit about AddOrUpdate comparing the value?

[theodorzoulias]

So I'm not sure what this issue is trying to achieve. Are you asking for the docs to be more explicit about AddOrUpdate comparing the value?

Mr. Toub the purpose of this issue is to raise awareness that AddOrUpdate's hidden dependency on the EqualityComparer<TValue>.Default has thread-safety implications, on top of the already known performance implications. That's something I didn't know a couple of days ago, and I assumed that neither Microsoft was aware of it, so I reported it. What should be done about this issue is honestly none of my business. Since changing the implementation of the ConcurrentDictionary<TKey,TValue> has been ruled out, I guess that enhancing the documentation with more detailed guidance is the next logical alternative, but I am not asking for it, neither I am willing to contribute to it. I think that I've done my part by reporting the issue.

[stephentoub]

Thanks. Making the docs more explicit about AddOrUpdate needing to compare the values would be fine.