title: Why does this race condition occur only with -O3 and only with a certain, seemingly equivalent code order?
body: <p>I have implemented an immutable hash map and accompanying STM container inspired by clojure's <code>atom</code>, which is to say, something akin to C++'s <code>std::unique_ptr</code>, in that it manages (but not necessarily owns) another object via a pointer, which can be passed around and swapped out, and only decrementing the reference count of the managed object instead of outright destructing it. When running some test code compiled with <code>-O3</code>, I've started noticing incorrect results.</p>
  
  <p>The code for the compare-and-swap looks something like this:</p>
  
  <pre class="lang-c prettyprint-override"><code>hashmap *update(stm *stm, update_callback cb, void *user_args)
  {
      while (1) {
          lock(stm-&gt;mutex);
          hashmap *current = stm-&gt;reference;
          increment_ref_count(current); // Line 6
          unlock(stm-&gt;mutex);
  
          hashmap *aspirant = cb(current, user_args); // returns a new, thread local instance
          increment_ref_count(aspirant);
  
          // Position 1
  
          lock(stm-&gt;mutex);
          if (current == stm-&gt;reference) { // success, no modification while we were busy
              stm-&gt;reference = aspirant;
              increment_ref_count(aspirant); // stm now has a reference
              unlock(stm-&gt;mutex);
  
              // Position 2.1
              decrement_ref_count(current); // release reference acquired at line 6
  
              decrement_ref_count(current); // stm no longer has a reference
              return aspirant;
  
          } else { // reference was modified, loop and try again
              unlock(stm-&gt;mutex);
  
              // Position 2.2
              decrement_ref_count(current); // release reference acquired at line 6
  
              decrement_ref_count(aspirant); // ref_count now at zero, aspirant is free'd
          }
      }
  }
  </code></pre>
  
  <p><code>increment_</code> &amp; <code>decrement_ref_count</code> in-/decrease the reference count of the hashmap atomically. If the count drops to zero as the result of a decrement, the hasmap will be free'd shortly after.</p>
  
  <p>The challenge with designing an STM container for a reference counted pointer was mostly about making aquiring-the-reference-and-incrementing-the-counter atomic, which is why I'm using locks here.</p>
  
  <p>As a test, I'm using the hashmap+STM to count occurences in a word list.</p>
  
  <p>If I run the code as posted here, no race conditions occur. <strong>Now comes my problem</strong>: if I move the <code>decrement_ref_count(current); // for line 6</code> out of the <code>if/else</code>, away from <code>Positions 2.1/2.2</code> (right after the second locked region) and put it at <code>Position 1</code> (right before the second locked region), suddenly the word counts start being incorrect, and I have no idea why.</p>
  
  <p>My argument is that a) I don't make any use of <code>current</code> during the second critical region, and b) therefore it shouldn't matter if I release the reference before or after the compare-and-swap.</p>
  
  <p>Obviously, I have a workaround/solution for the problem; simply leaving the <code>decrement</code>'s where they are now, but I would really like to understand why this happens.</p>
  
  <p>Compiled with: <code>gcc -Wall -Wcast-align -Wswitch-enum -Wswitch-default -Winit-self -pedantic -O3 -DNDEBUG -std=gnu11</code> on the "Windows Subsystem for Linux".</p>