Thread: Trying to understand hazard pointer implementation

This brings us to the work done with local_c0 and local_c1 (and will after this bring us back to the point actually in hand);

Code:

  reader_start:
  {
    local_c0 = c0;
    local_c1 = c1;
    __atomic_thread_fence( __ATOMIC_ACQUIRE );
    if( local_c0 == c0 and local_c1 == c1 )
      if( local_c0 > local_c1 )
        printf( "uh-oh! c0 is %llu and c1 is %llu\n", local_c0, local_c1 );
  } 
 goto reader_start;

So, here we make local copies of c0 and c1. They can be absolutely any value at all - any ordering whatsoever. We might see tons of c0 increments and none at all of c1. This is all fine.

We then issue the load barrier. At this point, we process the outstanding invalidation request queue.

Once this is done, we then look again at c0 and c1. If they have changed - i.e. they differ from local_c0 and/or local_c1, then we had invalidation requests which we had not yet seen when we loaded into c0 and c1, or which occurred after those loads.

If this is so, then we're out - we go around and try again.

However, if the values in c0 and c1 are *the same as before the load barrier*, then there were *no* invalidation requests pending from the time we loaded c0 to the time we compared local_c0 with c0 and local_c1 with c1.

Now it may be the very instant after the compare the invalidation request queue refills to the brim - but for us, it doesn't matter; what we *know* now is that *even though we issued a load barrier*, the values in c0 and c1 *did not change by the time of our if() *AFTER* the load barrier*, and *THEREFORE* we have *actually* got hold of the real values at that point.

We're basically looping over a race condition, until it works, and when it does finally work, then we know we have values which were correctly propagated from the storing physical core to ourselves. Of course, the very instant after the if() the actual values may change - but we are still working in our code with local_c0 and local_c1, the copies of the values which we have proved to be correct with regard to each other; we have access to something which at least was true at some point. This is useful, because we then make decisions based on it, and then try to apply those decisions using atomic operations. If the truth has moved on enough that the data upon which we made our decisions has changed, such that our decision is wrong, the atomic operation where we try to apply our decision will fail, and then we iterate around again in some higher-level loop.

So you can pretty much use load barriers as lines in the sand where you can get real values - but you have to do some extra work.

After this, we will go back to whether or not store barriers actually cause all stores to complete by the time they return, or if only by the time of the first store after the store barrier.