dotnet / dotnet/dotnet-api-docs
Thread-safety implications of using EqualityComparer<TValue>.Default in ConcurrentDictionary
- Dominant language
- C#
- Stars
- 949
- Forks
- 1.7k
- Avg merge
- 3d 27m
- Merged PRs (30d)
- 49
Description
Hi. Some time ago I posted [an issue](https://github.com/dotnet/runtime/issues/84163) about the performance implications of using the default `TValue` comparer internally in the [`ConcurrentDictionary`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2) 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` 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`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2.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`, 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`:
```C#
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
public class Program
{
class Genome : Queue, IEquatable
{
public bool Equals(Genome other) => this.SequenceEqual(other);
}
public static void Main()
{
ConcurrentDictionary 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:
```none
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.b__3()
at System.Threading.Thread.StartCallback()
```
[Online demo](https://dotnetfiddle.net/cCBoTa).
This looks to me like a valid/intended use of the `ConcurrentDictionary` collection, but I might be wrong.
I experimented with the [`ImmutableDictionary`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutabledictionary-2) as well, expecting to be unaffected from this issue, but to my surprise it is affected as well ([demo](https://dotnetfiddle.net/SvYnls)). This collection also makes calls to the `EqualityComparer.Default.Equals` when it is updated atomically with the [`ImmutableInterlocked.AddOrUpdate`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutableinterlocked.addorupdate) API. At least the immutable dictionary is equipped with the [`WithComparers`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutabledictionary-2.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.
Contributor guide
Assessment
This issue has not been assessed yet.