Bug 2709 - CyclicDeque is not thread safe
Summary: CyclicDeque is not thread safe
Status: RESOLVED INVALID
Alias: None
Product: Class Libraries
Classification: Mono
Component: mscorlib ()
Version: master
Hardware: Macintosh Mac OS
: --- normal
Target Milestone: Untriaged
Assignee: Jérémie Laval
URL:
Depends on:
Blocks:
 
Reported: 2012-01-01 09:49 UTC by Ken Bell
Modified: 2012-01-02 18:25 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 INVALID

Description Ken Bell 2012-01-01 09:49:09 UTC
CyclicDeque, which is used in the implementation of System.Threading.Tasks.SimpleConcurrentBag, System.Collections.Concurrent.ConcurrentBag and Mono.Threading.Tasks.FixedTaskScheduler is not thread-safe.

If the size of the 'array' member needs to be increased, there is a race condition with other threads that are populating the array in PushBottom.

Repro code:

using System;
using System.Collections.Generic;
using System.Threading;
using Mono.Threading.Tasks;

namespace TestProject
{
    class MainClass
    {
        private const int numThreads = 10;
        private const int numItems = 100;
        private static CyclicDeque<int> dequeue;
        
        public static void Main (string[] args)
        {
            dequeue = new CyclicDeque<int> ();
            
            Thread[] threads = new Thread[numThreads];
            
            for (int i = 0; i < numThreads; ++i) {
                int start = i * 1000;
                ThreadStart ts = new ThreadStart (delegate {
                    Enqueue (start);});
                
                threads [i] = new Thread (ts);
            }
            
            for (int i = 0; i < numThreads; ++i) {
                threads [i].Start ();
            }
            
            
            for (int i = 0; i < numThreads; ++i) {
                threads [i].Join ();
            }
            
            List<int> values = new List<int> ();
            int val;
            
            PopResult result = dequeue.PopTop (out val);
            while (result != PopResult.Empty) {
                if (result == PopResult.Succeed) {
                    values.Add (val);
                }
                else
                {
                    Console.WriteLine("Failed to PopTop");
                }
                
                result = dequeue.PopTop(out val);
            }
            
            values.Sort ();
            
            if(values.Count != numThreads * numItems)
            {
                throw new Exception("Incorrect number of values, expected=" + (numThreads * numItems) + ", actual=" + values.Count);
            }
   
            for(int i = 0; i < numThreads; ++i)
            {
                for(int j = 0; j < numItems; ++j)
                {
                    int lookFor = i * 1000 + j;
                    if(!values.Contains(lookFor))
                    {
                        Console.WriteLine("Value missing=" + lookFor);
                    }
                }
            }

            Console.WriteLine ("Hello World!");
        }
        
        private static void Enqueue (int rangeStart)
        {
            for (int i = 0; i < numItems; ++i) {
                dequeue.PushBottom (rangeStart + i);
            }
        }
    }
}

Running this code shows a large number of values end up as 'zero'.
Comment 1 Jérémie Laval 2012-01-02 17:16:54 UTC
Hey Ken,

This is totally normal. The semantics of CyclicDeque are the same than the normal ABP work-stealing queue i.e. only the PopTop operation is thread-safe wrt to all worker threads. All *Bottom operations need to happen on a single thread.

If you look at the implementation of all the class that use CyclicDeque, each thread has its own instance and only use those of other threads with the PopTop operation.

However if you find a place where this is not the case then indeed there is a bug.
Comment 2 Ken Bell 2012-01-02 18:25:16 UTC
Thanks - misunderstanding on my part.