• Locked Locked
  • Replies 6 replies
  • Subscribers 120 subscribers
  • Views 4729 views
  • Users 0 members are here
Options
Related
How was your experience today?
This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

Memory barriers and ldrexd - race condition?

Toebs Douglass
Note: This was originally posted on 2nd October 2012 at http://forums.arm.com

Hi -

Can someone please please PLEASE help me understand something which is still after a LOT of effort trying to understand confusing and puzzling me.

I'm trying to get my head around memory barriers and load-link/conditional-store.

In the ARM Linux kernel, I see this function;

353 static inline u64 atomic64_cmpxchg(atomic64_t *ptr, u64 old, u64 new)
354 {
355   u64 oldval;
356   unsigned long res;
357
358   smp_mb();
359
360   do {
361     __asm__ __volatile__("@ atomic64_cmpxchg\n"
362     "ldrexd   %1, %H1, [%3]\n"
363     "mov         %0, #0\n"
364     "teq         %1, %4\n"
365     "teqeq       %H1, %H4\n"
366     "strexdeq    %0, %5, %H5, [%3]"
367     : "=&r" (res), "=&r" (oldval), "+Qo" (ptr->counter)
368     : "r" (&ptr->counter), "r" (old), "r" (new)
369     : "cc");
370   } while (res);
371
372   smp_mb();
373
374   return oldval;
375 }

Now, I recently read Paul McKenney's paper explaining the hardware issues involved in memory barriers.

So what I understand is that the initial memory barrier flushes the invalidate queue and the store buffer.

That's all good and well.

We then come to the ldrexd.  Now, this will perform the initial load and activate the ERG covering the address where the load occurs.

(And then we compare and if the compare passes, we store.  We then issue another memory barrier to ensure our store will be seen before any other stores that we then perform (assuming the other CPUs issued read barriers, of course)).

Now, that which I am so confused about; after the first memory barrier, well - there's a period between the invalidate queue/store buffer flush and the execution of ldrexd.

During this time another CPU (especially if we're running a lock-free data structure, where we're using the same pointer a lot on different CPUs) could issue an invalidate on that pointer - and we in our CPU could fail to process it before executing ldrexd.

So we haven't yet activated the ERG - we're blind to the invalidate AND we're about to load an out of date value from our cache!

So we can imagine doing so, doing the compare, the compare passes, and then we store - which confuses me even more, because we could then store and THEN find the invalidate...

So, I'm missing something here.  Question is, what?

PLEASE someone enlighten me!

It's that or insanity and I think I'm pretty close by now :-)
Parents
  • Note: This was originally posted on 3rd October 2012 at http://forums.arm.com

    Now if I understand your question correctly, the scenario you have in mind is a little different.  You're asking what would happen if the other thread were to change the value of the pointer itself (so making it point to a different address).  Ok, simple answer is that no number of barriers is going to fix this.  In the first example the thing shared between the threads is the memory being pointed at - not the pointer itself.  Hence we use synchronization controls for accessing the memory, but not the pointer.  If the pointer itself is also a shared resource that can be modified, then access to it _also_ requires synchronization (e.g. a mutex).


    I'm afraid my question is not clear (or my understanding is not clear, which makes my question non-sensical).

    Imagine I have a queue.  Core A is about to attempt to enqueue.  It issues the read barrier, clearing its invalidate queue.  It has a valid cache line entry for the enqueue pointer.  Having finished the read barrier, but before the ldrexd, Core B enqueues another element.  The enqueue pointer is now different and an invalidate has been issued to Core A - but Core A hasn't yet processed that message and NOW executes the ldrexd (and so ERG doesn't help us, because the change has already occurred).  Core A loads the old value from its cache line, successfully compares and then calls strexd to write.

    If Core A writes, we lose the element Core B just enqueued!
Reply
  • Note: This was originally posted on 3rd October 2012 at http://forums.arm.com

    Now if I understand your question correctly, the scenario you have in mind is a little different.  You're asking what would happen if the other thread were to change the value of the pointer itself (so making it point to a different address).  Ok, simple answer is that no number of barriers is going to fix this.  In the first example the thing shared between the threads is the memory being pointed at - not the pointer itself.  Hence we use synchronization controls for accessing the memory, but not the pointer.  If the pointer itself is also a shared resource that can be modified, then access to it _also_ requires synchronization (e.g. a mutex).


    I'm afraid my question is not clear (or my understanding is not clear, which makes my question non-sensical).

    Imagine I have a queue.  Core A is about to attempt to enqueue.  It issues the read barrier, clearing its invalidate queue.  It has a valid cache line entry for the enqueue pointer.  Having finished the read barrier, but before the ldrexd, Core B enqueues another element.  The enqueue pointer is now different and an invalidate has been issued to Core A - but Core A hasn't yet processed that message and NOW executes the ldrexd (and so ERG doesn't help us, because the change has already occurred).  Core A loads the old value from its cache line, successfully compares and then calls strexd to write.

    If Core A writes, we lose the element Core B just enqueued!
Children
No data