Bug 22180 - Concurrent collection enumeration not thread safe
Summary: Concurrent collection enumeration not thread safe
Status: RESOLVED FIXED
Alias: None
Product: Class Libraries
Classification: Mono
Component: mscorlib ()
Version: master
Hardware: PC Mac OS
: --- normal
Target Milestone: Untriaged
Assignee: Bugzilla
URL:
Depends on:
Blocks:
 
Reported: 2014-08-18 17:41 UTC by Jonathan Pryor
Modified: 2015-01-23 07:28 UTC (History)
3 users (show)

Tags:
Is this bug a regression?: ---
Last known good build:

Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.


Please create a new report on GitHub or Developer Community with your current version information, steps to reproduce, and relevant error messages or log files if you are hitting an issue that looks similar to this resolved bug and you do not yet see a matching new report.

Related Links:
Status:
RESOLVED FIXED

Description Jonathan Pryor 2014-08-18 17:41:46 UTC
Consider System.Collections.Concurrent.ConcurrentQueue<T>.GetEnumerator():

http://msdn.microsoft.com/en-us/library/dd287144(v=vs.110).aspx

> The enumeration represents a moment-in-time snapshot of the contents of the queue.
> It does not reflect any updates to the collection after GetEnumerator was called.

Snapshot semantics allow a degree of sanity when using ConcurrentQueue<T> from multiple threads.

Unfortunately, Mono's ConcurrentQueue<T>.GetEnumerator() does not implement snapshot semantics:

https://github.com/mono/mono/blob/4449269d/mcs/class/corlib/System.Collections.Concurrent/ConcurrentQueue.cs#L169

>		IEnumerator<T> InternalGetEnumerator ()
>		{
>			Node my_head = head;
>			while ((my_head = my_head.Next) != null) {
>				yield return my_head.Value;
>			}
>		}

If you're using `yield return`, you're NOT getting snapshot semantics.

The same is true of ConcurrentDictionary`2, ConcurrentStack<T>, etc. All of the Concurrent types should be reviewed for snapshot semantics.
Comment 1 Rodrigo Kumpera 2014-08-26 00:00:47 UTC
I fail to see the relationship between using yield return and having snapshot semantics.

Under which case you think it will fail to return a proper snapshot of the queue at the time InternalGetEnumerator was called?
Comment 2 Jonathan Pryor 2014-08-26 01:04:49 UTC
@Kumpera: Consider the following app:

  using System;
  using System.Threading;
  using System.Collections.Concurrent;

  class App {
    static ConcurrentQueue<int> Q = new ConcurrentQueue<int> ();
    const int Max = 100;

    public static void Main ()
    {
      var a = new Thread (Add);
      var r = new Thread (Remove);
      var l = new Thread (Log);
    
      a.Start ();
      r.Start ();
      l.Start ();
    
      a.Join ();
      r.Join ();
      l.Join ();
    }

    static void Add ()
    {
      for (int i = 0; i < Max; ++i) {
        Console.WriteLine ("A: {0}", i);
        Q.Enqueue (i);
      }
    }

    static void Remove ()
    {
      for (int i = 0; i < Max; ++i) {
        int v;
        while (!Q.TryDequeue (out v)) {
        }
        Console.WriteLine ("R: {0}", v);
      }
    }

    static void Log ()
    {
      for (int i = 0; i < Max; ++i) {
        Console.WriteLine ("L: {0}", string.Join (", ", Q));
      }
    }
  }

It creates 3 threads to add, remove, and log the contents of the queue. As per snapshot semantics, we should expect that the logged output should never be "invalid".

>   $ mono --version
>   Mono JIT compiler version 3.8.0 ((no/62a857e Wed Aug 13 00:46:20 EDT 2014)
>   $ mcs bxc-22180.cs
>   $ mono bxc-22180.exe
>   A: 0
>   L: 
>   ...
>   R: 0
>   ...
>   L: 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 31, 32, 33, 34
>   ...

Actual output will vary on every execution, but *clearly* the above L: message is invalid: we only ever add one value of 0, so there CANNOT be 27 entires for 0, not with a proper snapshot.k

A different run, a different result, but still some invalid output:

>   L: 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 22, 23, 24, 25, 26, 27, 28, 29

If you run the test and see multiple entries with the same value, or entires that are not constantly increasing, you're seeing the bug.
Comment 3 Marek Safar 2015-01-23 07:28:16 UTC
Fixed in master