• Locked Locked
  • Replies 6 replies
  • Subscribers 120 subscribers
  • Views 4730 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
  • Arm Employee Badge
    Note: This was originally posted on 3rd October 2012 at http://forums.arm.com

    I'm not a Linux expert, so don't know how/when/why Linux will do this.  I'm basing this is on the code, and the function name.

    First lets think of the "normal" case...  Two threads (on two cores) try to simultaneously update the memory pointed at by the pointer to different values, using the same function.  Each core executes the LDREXD in the same cycle, both setting up their local exclusive manuals. Both successfully do the comparisons, and then both attempt the STREXD.  Assuming this is a MPCore configured for SMP the coherency logic will then arbitrate meaning that the STREXD will succeed on one core, but fail on the other (which is of course to try again).  The barrier at the end is to ensure that the code after the function return will see the effects of the store. 

    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).
Reply
  • Arm Employee Badge
    Note: This was originally posted on 3rd October 2012 at http://forums.arm.com

    I'm not a Linux expert, so don't know how/when/why Linux will do this.  I'm basing this is on the code, and the function name.

    First lets think of the "normal" case...  Two threads (on two cores) try to simultaneously update the memory pointed at by the pointer to different values, using the same function.  Each core executes the LDREXD in the same cycle, both setting up their local exclusive manuals. Both successfully do the comparisons, and then both attempt the STREXD.  Assuming this is a MPCore configured for SMP the coherency logic will then arbitrate meaning that the STREXD will succeed on one core, but fail on the other (which is of course to try again).  The barrier at the end is to ensure that the code after the function return will see the effects of the store. 

    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).
Children
No data