title: Interlocked.Increment not thread safe?
body: <p>I found a compiler bug in just one line of code:</p>
  
  <pre><code>int thisIndex = Interlocked.Increment(ref messagesIndex) &amp; indexMask;
  </code></pre>
  
  <p>The definitions are:</p>
  
  <pre><code>static int messagesIndex = -1;
  public const int MaxMessages = 0x10000;
  const int indexMask = MaxMessages-1;
  </code></pre>
  
  <p><code>messagesIndex</code> is not accessed by any other line of code.</p>
  
  <p>If I run that code billions of times in a single thread, I don't get any errors.</p>
  
  <p>If I run the above line on several threads, I get the same number twice and another number gets skipped every 1x-thousand times.</p>
  
  <p>The following line I have run billions of times on 6 threads without ever getting an error:</p>
  
  <pre><code>int thisIndex = Interlocked.Increment(ref messagesIndex);
  </code></pre>
  
  <p><strong>Conclusion and Question</strong></p>
  
  <p>It seems that <code>Interlocked.Increment()</code> on its own works as expected, but <code>Interlocked.Increment()</code> &amp; <code>indexMask</code> does not :-(</p>
  
  <p>Any idea how I can make it work properly all the time, not just 99.99% ?</p>
  
  <p>I tried to assign <code>Interlocked.Increment(ref messagesIndex)</code> to a volatile integer variable and do the <code>"&amp; indexMask"</code> operation on that variable:</p>
  
  <pre><code>[ThreadStatic]
  volatile static int nextIncrement;
  
  nextIncrement = Interlocked.Increment(ref mainIndexIncrementModTest);
  indexes[testThreadIndex++] = nextIncrement &amp; maskIncrementModTest;
  </code></pre>
  
  <p>It causes the same problem like when I write it in 1 line. </p>
  
  <p><strong>Disassembly</strong></p>
  
  <p>Maybe someone can guess from the disassembly what problem the compiler introduces:</p>
  
  <pre><code>indexes[testThreadIndex++] = Interlocked.Increment(ref mainIndexIncrementTest);
  0000009a  mov         eax, dword ptr [ebp-48h] 
  0000009d  mov         dword ptr [ebp-58h], eax 
  000000a0  inc         dword ptr [ebp-48h] 
  000000a3  mov         eax, dword ptr [ebp-44h] 
  000000a6  mov         dword ptr [ebp-5Ch], eax 
  000000a9  lea         ecx, ds:[00198F84h] 
  000000af  call        6D758403 
  000000b4  mov         dword ptr [ebp-60h], eax 
  000000b7  mov         eax, dword ptr [ebp-58h] 
  
  000000ba  mov         edx, dword ptr [ebp-5Ch] 
  000000bd  cmp         eax, dword ptr [edx+4] 
  000000c0  jb          000000C7 
  000000c2  call        6D9C2804 
  000000c7  mov         ecx, dword ptr [ebp-60h] 
  000000ca  mov         dword ptr [edx+eax*4+8], ecx 
  
  indexes[testThreadIndex++] = Interlocked.Increment(ref mainIndexIncrementModTest) &amp; maskIncrementModTest;
  0000009a  mov         eax, dword ptr [ebp-48h] 
  0000009d  mov         dword ptr [ebp-58h], eax 
  000000a0  inc         dword ptr [ebp-48h] 
  000000a3  mov         eax, dword ptr [ebp-44h] 
  000000a6  mov         dword ptr [ebp-5Ch], eax 
  000000a9  lea         ecx,ds:[001D8F88h] 
  000000af  call        6D947C8B 
  000000b4  mov         dword ptr [ebp-60h], eax 
  000000b7  mov         eax, dword ptr [ebp-60h] 
  000000ba  and         eax, 0FFFh 
  000000bf  mov         edx, dword ptr [ebp-58h] 
  000000c2  mov         ecx, dword ptr [ebp-5Ch] 
  000000c5  cmp         edx, dword ptr [ecx+4] 
  000000c8  jb          000000CF 
  000000ca  call        6DBB208C 
  000000cf  mov         dword ptr [ecx+edx*4+8], eax 
  </code></pre>
  
  <p><strong>Bug Detection</strong></p>
  
  <p>To discover the bug, I run the problem line in 6 threads endlessly and each thread writes the returned integers in huge integer arrays. After some time, I stop the threads and search all six integer arrays if every number is returned exactly once (of course, I allow for the "&amp; indexMask" operation).</p>
  
  <pre><code>using System;
  using System.Text;
  using System.Threading;
  
  
  namespace RealTimeTracer 
  {
      class Test 
      {
          #region Test Increment Multi Threads
          //      ----------------------------
  
          const int maxThreadIndexIncrementTest = 0x200000;
          static int mainIndexIncrementTest = -1; //the counter gets incremented before its use
          static int[][] threadIndexThraces;
  
          private static void testIncrementMultiThread() 
          {
              const int maxTestThreads = 6;
  
              Thread.CurrentThread.Name = "MainThread";
  
              //start writer test threads
              Console.WriteLine("start " + maxTestThreads + " test writer threads.");
              Thread[] testThreads = testThreads = new Thread[maxTestThreads];
              threadIndexThraces = new int[maxTestThreads][];
              int testcycle = 0;
  
              do 
              {
                  testcycle++;
                  Console.WriteLine("testcycle " + testcycle);
                  for (int testThreadIndex = 0; testThreadIndex &lt; maxTestThreads; testThreadIndex++) 
                  {
                      Thread testThread = new Thread(testIncrementThreadBody);
                      testThread.Name = "TestThread " + testThreadIndex;
                      testThreads[testThreadIndex] = testThread;
                      threadIndexThraces[testThreadIndex] = new int[maxThreadIndexIncrementTest+1]; //last int will be never used, but easier for programming
                  }
  
                  mainIndexIncrementTest = -1; //the counter gets incremented before its use
                  for (int testThreadIndex = 0; testThreadIndex &lt; maxTestThreads; testThreadIndex++) 
                  {
                      testThreads[testThreadIndex].Start(testThreadIndex);
                  }
  
                  //wait for writer test threads
                  Console.WriteLine("wait for writer threads.");
  
                  foreach (Thread testThread in testThreads)
                  {
                      testThread.Join();
                  }
  
                  //verify that EVERY index is used exactly by one thread.
                  Console.WriteLine("Verify");
                  int[] threadIndexes = new int[maxTestThreads];
  
                  for (int counter = 0; counter &lt; mainIndexIncrementTest; counter++) 
                  {
                      int threadIndex = 0;
                      for (; threadIndex &lt; maxTestThreads; threadIndex++) 
                      {
                          if (threadIndexThraces[threadIndex][threadIndexes[threadIndex]]==counter) 
                          {
                              threadIndexes[threadIndex]++;
                              break;
                          }
                      }
  
                      if (threadIndex==maxTestThreads) 
                      {
                          throw new Exception("Could not find index: " + counter);
                      }
                  }
              } while (!Console.KeyAvailable);
          }
  
          public static void testIncrementThreadBody(object threadNoObject)
          {
              int threadNo = (int)threadNoObject;
              int[] indexes = threadIndexThraces[threadNo];
              int testThreadIndex = 0;
              try
              {
                  for (int counter = 0; counter &lt; maxThreadIndexIncrementTest; counter++)      
                  {
                      indexes[testThreadIndex++] = Interlocked.Increment(ref mainIndexIncrementTest);
                  }
              } 
              catch (Exception ex) 
              {
                  OneTimeTracer.Trace(Thread.CurrentThread.Name + ex.Message);
              }
          }
          #endregion
  
  
          #region Test Increment Mod Multi Threads
          //      --------------------------------
  
          const int maxThreadIndexIncrementModTest = 0x200000;
          static int mainIndexIncrementModTest = -1; //the counter gets incremented before its use
          const int maxIncrementModTest = 0x1000;
          const int maskIncrementModTest = maxIncrementModTest - 1;
  
  
          private static void testIncrementModMultiThread() 
          {
              const int maxTestThreads = 6;
  
              Thread.CurrentThread.Name = "MainThread";
  
              //start writer test threads 
              Console.WriteLine("start " + maxTestThreads + " test writer threads.");
              Thread[] testThreads = testThreads = new Thread[maxTestThreads];
              threadIndexThraces = new int[maxTestThreads][];
              int testcycle = 0;
              do 
              {
                  testcycle++;
                  Console.WriteLine("testcycle " + testcycle);
                  for (int testThreadIndex = 0; testThreadIndex &lt; maxTestThreads; testThreadIndex++)
                  {
                      Thread testThread = new Thread(testIncrementModThreadBody);
                      testThread.Name = "TestThread " + testThreadIndex;
                      testThreads[testThreadIndex] = testThread;
                      threadIndexThraces[testThreadIndex] = new int[maxThreadIndexIncrementModTest+1]; //last int will be never used, but easier for programming
                  }
  
                  mainIndexIncrementModTest = -1; //the counter gets incremented before its use
                  for (int testThreadIndex = 0; testThreadIndex &lt; maxTestThreads; testThreadIndex++) 
                  {
                      testThreads[testThreadIndex].Start(testThreadIndex);
                  }
  
                  //wait for writer test threads
                  Console.WriteLine("wait for writer threads.");
                  foreach (Thread testThread in testThreads) 
                  {
                      testThread.Join();
                  }
  
                  //verify that EVERY index is used exactly by one thread.
                  Console.WriteLine("Verify");
                  int[] threadIndexes = new int[maxTestThreads];
                  int expectedIncrement = 0;
                  for (int counter = 0; counter &lt; mainIndexIncrementModTest; counter++) 
                  {
                      int threadIndex = 0;
                      for (; threadIndex &lt; maxTestThreads; threadIndex++) 
                      {
                          if (threadIndexes[threadIndex]&lt;maxThreadIndexIncrementModTest     &amp;&amp; 
  threadIndexThraces[threadIndex][threadIndexes[threadIndex]]==expectedIncrement) 
                          {
                              threadIndexes[threadIndex]++;
                              expectedIncrement++;
                              if (expectedIncrement==maxIncrementModTest) 
                              {
                                  expectedIncrement = 0;
                              }
                              break;
                          }
                      }
  
                      if (threadIndex==maxTestThreads) 
                      {
                          StringBuilder stringBuilder = new StringBuilder();
                          for (int threadErrorIndex = 0; threadErrorIndex &lt; maxTestThreads; threadErrorIndex++)
                          {
                              int index = threadIndexes[threadErrorIndex];
                              if (index&lt;0) 
                              {
                                  stringBuilder.AppendLine("Thread " + threadErrorIndex + " is empty");
                              }
                              else if (index==0)
                              {
                                  stringBuilder.AppendLine("Thread " + threadErrorIndex + "[0]=" +
                                  threadIndexThraces[threadErrorIndex][0]);
                              }
                              else if (index&gt;=maxThreadIndexIncrementModTest) 
                              {
                                  stringBuilder.AppendLine("Thread " + threadErrorIndex + "[" + (index-1) + "]=" +
                  threadIndexThraces[threadErrorIndex][maxThreadIndexIncrementModTest-2] + ", " + 
                  threadIndexThraces[threadErrorIndex][maxThreadIndexIncrementModTest-1]);
                              } 
                              else 
                              {
                                  stringBuilder.AppendLine("Thread " + threadErrorIndex + "[" + (index-1) + "]=" +
                  threadIndexThraces[threadErrorIndex][index-1] + ", " + 
                  threadIndexThraces[threadErrorIndex][index]);
                              }
                          } 
  
                          string exceptionString = "Could not find index: " + expectedIncrement + " for counter " + counter + Environment.NewLine + stringBuilder.ToString();
                          Console.WriteLine(exceptionString);
  
                          return;
                          //throw new Exception(exceptionString);
                      }
                  }
              } while (!Console.KeyAvailable);
          }
  
  
          public static void testIncrementModThreadBody(object threadNoObject)
          {
              int threadNo = (int)threadNoObject;
              int[] indexes = threadIndexThraces[threadNo];
              int testThreadIndex = 0;
              try
              {
                  for (int counter = 0; counter &lt; maxThreadIndexIncrementModTest; counter++) 
                  {
                      // indexes[testThreadIndex++] = Interlocked.Increment(ref mainIndexIncrementModTest) &amp; maskIncrementModTest;
                      int nextIncrement = Interlocked.Increment(ref mainIndexIncrementModTest);
                      indexes[testThreadIndex++] = nextIncrement &amp; maskIncrementModTest;
                  }
              } 
              catch (Exception ex) 
              {
                  OneTimeTracer.Trace(Thread.CurrentThread.Name + ex.Message);
              }
          }
          #endregion
      }
  }
  </code></pre>
  
  <p>This produces the following error:</p>
  
  <p>Content of the 6 int-arrays (1 per thread)<br>
      Thread 0[30851]=2637, 2641<br>
      Thread 1[31214]=2639, 2644<br>
      Thread 2[48244]=2638, 2643<br>
      Thread 3[26512]=2635, 2642<br>
      Thread 4[0]=<strong>2636</strong>, 2775<br>
      Thread 5[9173]=2629, <strong>2636</strong>  </p>
  
  <p>Explanation:<br>
      Thread 4 uses 2636<br>
      Thread 5 also uses 2636 !!!! This should never happen<br>
      Thread 0 used 2637<br>
      Thread 2 used 2638<br>
      Thread 1 used 2639<br>
      2640 is not used by any thread !!! That's the error the test detects<br>
      Thread 0 used 2641<br>
      Thread 3 used 2642  </p>