Make LINQ safe to use on all collections that can be safely enumerated

[mikernet]

I figured I would start a discussion about this before creating an issue for it. As far as I know, adding DIMs to the BCL is something that may happen in the future but a conservative "wait for now" approach is being taken here since it is a relatively new feature that may have unintended consequences. Is this still the case?

The Problem

The BCL currently has 1 collection that is safe to enumerate over but NOT safe to call LINQ methods on and not safe to pass in as a List constructor parameter - ConcurrentDictionary. I have several others that fall into the same category, namely a set of collections that store weak references to values and an alternate concurrent dictionary implementation that provides a proper point-in-time snapshot while being enumerated over.

The only reason these aren't safe to use in LINQ methods and the List constructor is because they check if the IEnumerable collection also implements ICollection, and if so, assumes that ICollection.Count can be called to determine the number of items in the collection prior to creating an array to hold the items. This creates a race condition between the call to Count and the copying of the items to the resulting array.

The fact that LINQ methods can't be called on something that states it is safe to enumerate due to hidden internal dynamic-downcasting optimizations can not only be surprising but also very difficult to debug while going unnoticed for a long time, resulting in infrequent random crashes, or even worse, junk-data silently making its way through the application and persisting to storage, only under high-load situations. I have no idea how I would find a bug caused by this after a client complained that a random null or 0 value popped into their data once in a blue moon, and immense amounts of hair-pulling would ensue. I got lucky that I stumbled upon this issue before things went into production but many others may not be so lucky.

If a type can be safely enumerated, then IMO it should be safe to use in LINQ and any other place in the BCL that accepts an IEnumerable parameter, and methods that dynamically down-cast to ICollection for optimization purposes should be responsible for ensuring those optimizations do not have hidden unintended consequences which break their contract. I have outlined 2 options below that would allow this to happen.

Ultimately, it seems to me that ConcurrentDictionary probably should not have implemented ICollection<T> until an approach was available to safely allow it to do so without causing this problem. That's what I decided to do for now with our collections, but it would be nice to fix this so that we can implement ICollection and so other developers don't fall into this trap when using ConcurrentDictionary.

Related Issues

For further context, see the following issues:

Make IListProvider public
LINQ's Buffer ctor requires Count/CopyTo results be consistent

Immediate Mitigation

Prominent documentation needs to be added to ConcurrentDictionary to indicate it is NOT safe to pass into LINQ methods or any other method that accepts an IEnumerable<T> parameter but optimizes for ICollection<T>, preferably both in the main class documentation and the GetEnumerator() method documentation. The current docs for GetEnumerator() contains this information:

The enumerator returned from the dictionary is safe to use concurrently with reads and writes to the dictionary, however it does not represent a moment-in-time snapshot of the dictionary. The contents exposed through the enumerator may contain modifications made to the dictionary after GetEnumerator was called.

While this is strictly true, it lead me to believe that ConcurrentDictionary was safe to use with LINQ, which conceptually should work on anything that can be enumerated over. It would be nice to have some clearer information here.

Solution 1: Add ToArray() (as a DIM) on ICollection<T>

All the places I could find where this is a problem downcast the IEnumerable to ICollection, call Count to create an array, then call CopyTo() to copy the items. Having a single method that returns an array would eliminate the race condition between those two calls. ConcurrentDictionary already has a safe ToArray() method which does the appropriate locking to safely return an array. It would be trivial to add the same functionality to my collection classes.

This option is my preferred approach for performance reasons - no need for some kind of dictionary type lookup to check if the collection is concurrent, and collections can provide safe/optimized ToArray() implementations instead of forcing methods to fall back to unoptimized IEnumerable behavior.

The default implementation of the method would just call Count and then CopyTo(), and concurrent collections would override this default implementation with their safe versions.

Solution 2: Provide opt-out mechanism for ICollection.Count optimizations

This could be something like a [ConcurrentCollection] attribute that can be placed on collection classes to indicate that collection state can change between method calls and thus doing something like calling Count and then CopyTo() is not safe. A static helper method such as Enumerable.IsConcurrentCollection(Type collectionType) could be provided which would cache whether a collection type is concurrent or not. If this returns true then the ICollection optimizations would not be used and methods would fall back to IEnumerable behavior.

Another approach could be a marker interface like IConcurrentCollection which could be checked after a successful ICollection cast to ensure it is safe to proceed with the optimization.

[mikernet]

@stephentoub Curious if you have any comments on this matter, given that you were involved in the related issues.

[mikernet]

@VSadov Do you have any thoughts here?

[VSadov]

I do not think this is a problem of a particular type. ConcurrentDictionary in quiescent state can be enumerated and used in LINQ. On the other hand enumerating (as in - visiting every element that belongs to a collection) is not well-defined when membership itself can change.
That is why collections do not handle modifications while enumerating very well. In some cases it results in enumeration failures, but more generally it leads to undefined behavior. ConcurrentDictionary is not particularly special here.

If there is a solution to the "problem", it should be something that prevent overlapping enumeration and modification and ideally at compile time.

[mikernet]

It doesn't need to be well-defined, it just needs to be safe, which it is. Sometimes I don't care if I see modifications to the concurrent dictionary while I'm enumerating it. The point is it is safe to enumerate.

Further, my own concurrent dictionary type does have well-defined snapshot-like enumeration behavior but is still unsafe to use LINQ if I allow it to implement ICollection due to the hidden internal optimization happening there, so I can't make it implement IDictionary either (since that inherits from ICollection).

[mikernet]

If ConcurrentDictionary didn't implement ICollection then this wouldn't be a problem - it would have been safe to use with LINQ. The issue is LINQ's hidden ICollection optimizations, which can result in null/default values popping up that don't exist in the dictionary when using LINQ, or crashes, both which only happen under high load scenarios and very rarely. All we need to stop this from happening is an opt-out mechanism for the ICollection LINQ optimization or a ToArray() method on ICollection so the race condition does not happen.

It's a problem in particular for ConcurrentDictionary because that's the only type in the BCL that is safe to enumerate while modifications are being done but not safe to use LINQ on, which is only an issue because of the hidden optimizations that create a race condition, instead of using only the IEnumerable interface. This also creates a problem for third-party concurrent collections, such as mine.

It comes down to my issue that something that says "I work on IEnumerable" would in fact work fine if it actually treated it like an IEnumerable, but due to the bad assumption that it is safe to downcase to ICollection creates a hidden race condition. There are relatively easy solutions to this that would address this problem, so it seems prudent to me to do so.

[JustArchi]

I was hit by this problem just recently and had to fix it myself by finding affected areas and changing the input to IEnumerable<T> so the "optimization" in LINQ is not hit: JustArchiNET/ArchiSteamFarm@b6805a9

I realize this is not the most popular issue or problem in .NET, but when it hits, the results are scary. @stephentoub mentioning you since you seem most aware of this gimmick - perhaps it'd be wise to reconsider opt-out mechanism for concurrent collections from LINQ optimizations around them so we can fix this issue properly. Making concurrent collections implement something like IConcurrentCollection and LINQ with if (input is ICollection and is not IConcurrentCollection) would probably be sufficient.