Improve the implementation of atomic operations on Linux/ARM (including Android/ARM).

base/atomicops_internals_arm_gcc.h

+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This file is an internal atomic implementation, use base/atomicops.h instead.
+//
+// LinuxKernelCmpxchg and Barrier_AtomicIncrement are from Google Gears.
+
+#ifndef BASE_ATOMICOPS_INTERNALS_ARM_GCC_H_
+#define BASE_ATOMICOPS_INTERNALS_ARM_GCC_H_
+
+namespace base {
+namespace subtle {
+
+// Memory barriers on ARM are funky, but the kernel is here to help:
+//
+// * ARMv5 didn't support SMP, there is no memory barrier instruction at
+//   all on this architecture, or when targetting its machine code.
+//
+// * Some ARMv6 CPUs support SMP. A full memory barrier can be produced by
+//   writing a random value to a very specific coprocessor register.
+//
+// * On ARMv7, the "dmb" instruction is used to perform a full memory
+//   barrier (though writing to the co-processor will still work).
+//   However, on single core devices (e.g. Nexus One, or Nexus S),
+//   this instruction will take up to 200 ns, which is huge, even though
+//   it's completely un-needed on these devices.
+//
+// * There is no easy way to determine at runtime if the device is
+//   single or multi-core. However, the kernel provide a useful helper
+//   function at a fixed memory address (0xffff0fa0), which will always
+//   perform a memory barrier in the most efficient way. I.e. on single
+//   core devices, this is an empty function that exits immediately.
+//   On multi-core devices, it implements a full memory barrier.
+//
+//   Note that this helper function doesn't modify any register or memory.
+//   See the comment in Barrier_AtomicIncrement() to see why it is
+//   important.
+//
+// * This source could be compiled to ARMv5 machine code that runs on a
+//   multi-core ARMv6 or ARMv7 device. In this case, memory barriers
+//   are needed for correct execution. Always call the kernel helper, even
+//   when targetting ARMv5TE.
+//
+
+#define LINUX_ARM_KERNEL_MEMORY_BARRIER 0xffff0fa0
+
+inline void MemoryBarrier() {
+  // Note: This is a function call, which is also an implicit compiler
+  // barrier.
+  ((void (*)(void))LINUX_ARM_KERNEL_MEMORY_BARRIER)();
+}
+
+#if defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_6__)
+
+// On ARMv6 and higher, it is possible to directly use ldrex/strex
+// instructions to implement fast atomic operations directly.
+inline Atomic32 NoBarrier_CompareAndSwap(volatile Atomic32* ptr,
+                                         Atomic32 old_value,
+                                         Atomic32 new_value) {
+  Atomic32 prev_value;
+  int reloop;
+  do {
+    // The following is equivalent to:
+    //
+    //   prev_value = LDREX(ptr)
+    //   reloop = 0
+    //   if (prev_value != old_value)
+    //      reloop = STREX(ptr, new_value)
+    __asm__ __volatile__("    ldrex %0, [%3]\n"
+                         "    mov %1, #0\n"
+                         "    teq %0, %4\n"
+#ifdef __thumb2__
+                         "    it eq\n"
+#endif
+                         "    strexeq %1, %5, [%3]\n"
+                         : "=&r"(prev_value), "=&r"(reloop), "+m"(*ptr)
+                         : "r"(ptr), "r"(old_value), "r"(new_value)
+                         : "cc", "memory");
+  } while (reloop != 0);
+  return prev_value;
+}
+
+inline Atomic32 Acquire_CompareAndSwap(volatile Atomic32* ptr,
+                                       Atomic32 old_value,
+                                       Atomic32 new_value) {
+  Atomic32 result = NoBarrier_CompareAndSwap(ptr, old_value, new_value);
+  MemoryBarrier();
+  return result;
+}
+
+inline Atomic32 Release_CompareAndSwap(volatile Atomic32* ptr,
+                                       Atomic32 old_value,
+                                       Atomic32 new_value) {
+  MemoryBarrier();
+  return NoBarrier_CompareAndSwap(ptr, old_value, new_value);
+}
+
+inline Atomic32 NoBarrier_AtomicIncrement(volatile Atomic32* ptr,
+                                          Atomic32 increment) {
+  Atomic32 value;
+  int reloop;
+  do {
+    // Equivalent to:
+    //
+    //  value = LDREX(ptr)
+    //  value += increment
+    //  reloop = STREX(ptr, value)
+    //
+    __asm__ __volatile__("    ldrex %0, [%3]\n"
+                         "    add %0, %0, %4\n"
+                         "    strex %1, %0, [%3]\n"
+                         : "=&r"(value), "=&r"(reloop), "+m"(*ptr)
+                         : "r"(ptr), "r"(increment)
+                         : "memory");
+  } while (reloop);
+  return value;
+}
+
+inline Atomic32 Barrier_AtomicIncrement(volatile Atomic32* ptr,
+                                        Atomic32 increment) {
+  // TODO(digit): Investigate if it's possible to implement this with
+  // a single MemoryBarrier() operation between the LDREX and STREX.
+  // See http://crbug.com/246514
+  MemoryBarrier();
+  Atomic32 result = NoBarrier_AtomicIncrement(ptr, increment);
+  MemoryBarrier();
+  return result;
+}
+
+inline Atomic32 NoBarrier_AtomicExchange(volatile Atomic32* ptr,
+                                         Atomic32 new_value) {
+  Atomic32 old_value;
+  int reloop;
+  do {
+    // old_value = LDREX(ptr)
+    // fail = STREX(ptr, new_value)
+    __asm__ __volatile__("   ldrex %0, [%3]\n"
+                         "   strex %1, %4, [%3]\n"
+                         : "=&r"(old_value), "=&r"(reloop), "+m"(*ptr)
+                         : "r"(ptr), "r"(new_value)
+                         : "memory");

[Dmitry Vyukov, 2013/06/04 09:26:00]

I think that NoBarrier functions does not require "memory" clobber, because they
properly enumerate all inputs/outputs.
However, there is probably no code in Chromium for which is makes any
performance difference (stats collection?), I would use "memory", "cc"
everywhere just to be safe.

[digit1, 2013/06/04 13:24:18]

Thanks for the details, I've put "cc" and "memory" to all fragments.

+  } while (reloop != 0);
+  return old_value;
+}
+
+#else
+
+// The kernel also provides a helper function to perform an atomic
+// compare-and-swap operation at the hard-wired address 0xffff0fc0.
+// On ARMv5, this is implemented by a special code path that the kernel
+// detects and treats specially when thread pre-emption happens.
+// On ARMv6 and higher, it uses LDREX/STREX instructions instead.
+//
+// Note that this always perform a full memory barrier, there is no
+// need to add calls MemoryBarrier() before or after it. It also
+// returns 0 on success, and 1 on exit.
+//
+// Available since Linux 2.6.24. Note that the first Android releases

[Dmitry Vyukov, 2013/06/04 09:26:00]

It was available before 2.6.24, but it was returning spurious failures (fails
even if old_value==*ptr)

[digit1, 2013/06/04 11:51:56]

Thanks. I'm changing this to "Available and reliable since..."

[digit1, 2013/06/04 13:24:18]

Done.

+// used 2.6.29, and ChromeOS is currently at 3.4, iirc, so this should
+// only be a concern for people running _really_ old custom Linux/ARM
+// distributions).
+typedef int (*LinuxKernelCmpxchgFunc)(Atomic32 old_value,
+                                      Atomic32 new_value,
+                                      volatile Atomic32* ptr);
+LinuxKernelCmpxchgFunc pLinuxKernelCmpxchg __attribute__((weak)) =
+    (LinuxKernelCmpxchgFunc)0xffff0fc0;
+
+inline Atomic32 NoBarrier_CompareAndSwap(volatile Atomic32* ptr,
+                                         Atomic32 old_value,
+                                         Atomic32 new_value) {
+  Atomic32 prev_value;
+  for (;;) {
+    prev_value = *ptr;
+    if (prev_value != old_value)
+      return prev_value;

[Dmitry Vyukov, 2013/06/04 09:26:00]

This does not have acquire semantics either.
We load *ptr, see that it's different from old_value and return.
Caller can act based on the value returned from NoBarrier_CompareAndSwap(), e.g.
if it's equal to 1, load some global var. This needs dmb in between.

[digit1, 2013/06/04 11:51:56]

I see. Is it correct that this remark should only apply to
Acquire_CompareAndSwap()? I.e. that NoBarrier_CompareAndSwap() and
Release_CompareAndSwap() don't need this extra dmb before the return?

[digit1, 2013/06/04 12:00:37]

Also, please note that it looks like that the NoBarrier_CompareAndSwap()
implementation in base/atomicops_internals_gcc.h (currently used on Android/ARM
and NaCL) have the same "issue".

A bit off-topic, but base/atomicops_internal_mips_gcc.h is even more
interesting. The NoBarrier_CompareAndSwap() inline assembly also doesn't use any
memory barrier, and Barrier_CompareAndSwap() places _compiler_ barriers
before/after a call to NoBarrier_CompareAndSwap().

[Dmitry Vyukov, 2013/06/04 12:49:32]

Yes, that's correct.
But Acquire version does not need dbm, if pLinuxKernelCmpxchg() succeeds,
because it includes the barrier.
For this reason I prefer to do it the other way around, i.e. if the cheapest
atomic RMW is Barrier, then implement the Barrier version and then forward
Acquire/Release/NoBarrier to Barrier with a comment that there is no more
efficient implementation. But if you forward Barrier into NoBarrier, that's kind
of questionable.
I know that it's implemented this way in atomicops for historical reasons.

[Dmitry Vyukov, 2013/06/04 12:49:32]

I would not be surprised if there are bugs.

[digit1, 2013/06/04 13:24:18]

I've uploaded a patch where only Acquire_CompareAndSwap() performs the extra
memory barrier before returning. Please let me know if this is still not
correct.

+    if (!pLinuxKernelCmpxchg(old_value, new_value, ptr))
+      return old_value;
+  }
+}
+
+inline Atomic32 NoBarrier_AtomicExchange(volatile Atomic32* ptr,
+                                         Atomic32 new_value) {
+  Atomic32 old_value;
+  do {
+    old_value = *ptr;
+  } while (pLinuxKernelCmpxchg(old_value, new_value, ptr));
+  return old_value;
+}
+
+inline Atomic32 NoBarrier_AtomicIncrement(volatile Atomic32* ptr,
+                                          Atomic32 increment) {
+  return Barrier_AtomicIncrement(ptr, increment);
+}
+
+inline Atomic32 Barrier_AtomicIncrement(volatile Atomic32* ptr,
+                                        Atomic32 increment) {
+  for (;;) {
+    // Atomic exchange the old value with an incremented one.
+    Atomic32 old_value = *ptr;
+    Atomic32 new_value = old_value + increment;
+    if (!pLinuxKernelCmpxchg(old_value, new_value, ptr)) {
+      // The exchange took place as expected.
+      return new_value;
+    }
+    // Otherwise, *ptr changed mid-loop and we need to retry.
+  }
+}
+
+inline Atomic32 Acquire_CompareAndSwap(volatile Atomic32* ptr,
+                                       Atomic32 old_value,
+                                       Atomic32 new_value) {
+  return NoBarrier_CompareAndSwap(ptr, old_value, new_value);
+}
+
+inline Atomic32 Release_CompareAndSwap(volatile Atomic32* ptr,
+                                       Atomic32 old_value,
+                                       Atomic32 new_value) {
+  return NoBarrier_CompareAndSwap(ptr, old_value, new_value);
+}
+
+#endif  // __ARM_ARCH_6__ || __ARM_ARCH_7A__
+
+// NOTE: Atomicity of the following load and store operations is only
+// guaranteed in case of 32-bit alignement of |ptr| values.
+
+inline void NoBarrier_Store(volatile Atomic32* ptr, Atomic32 value) {
+  *ptr = value;
+}
+
+inline void Acquire_Store(volatile Atomic32* ptr, Atomic32 value) {
+  *ptr = value;
+  MemoryBarrier();
+}
+
+inline void Release_Store(volatile Atomic32* ptr, Atomic32 value) {
+  MemoryBarrier();
+  *ptr = value;
+}
+
+inline Atomic32 NoBarrier_Load(volatile const Atomic32* ptr) { return *ptr; }
+
+inline Atomic32 Acquire_Load(volatile const Atomic32* ptr) {
+  Atomic32 value = *ptr;
+  MemoryBarrier();
+  return value;
+}
+
+inline Atomic32 Release_Load(volatile const Atomic32* ptr) {
+  MemoryBarrier();
+  return *ptr;
+}
+
+#undef LINUX_ARM_KERNEL_MEMORY_BARRIER
+
+}  // namespace base::subtle
+}  // namespace base
+
+#endif  // BASE_ATOMICOPS_INTERNALS_ARM_GCC_H_