src/leveldb/port/atomic_pointer.h

   1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4
   5 // AtomicPointer provides storage for a lock-free pointer.
   6 // Platform-dependent implementation of AtomicPointer:
   7 // - If the platform provides a cheap barrier, we use it with raw pointers
   8 // - If <atomic> is present (on newer versions of gcc, it is), we use
   9 //   a <atomic>-based AtomicPointer.  However we prefer the memory
  10 //   barrier based version, because at least on a gcc 4.4 32-bit build
  11 //   on linux, we have encountered a buggy <atomic> implementation.
  12 //   Also, some <atomic> implementations are much slower than a memory-barrier
  13 //   based implementation (~16ns for <atomic> based acquire-load vs. ~1ns for
  14 //   a barrier based acquire-load).
  15 // This code is based on atomicops-internals-* in Google's perftools:
  16 // http://code.google.com/p/google-perftools/source/browse/#svn%2Ftrunk%2Fsrc%2Fbase
  17
  18 #ifndef PORT_ATOMIC_POINTER_H_
  19 #define PORT_ATOMIC_POINTER_H_
  20
  21 #include <stdint.h>
  22 #ifdef LEVELDB_ATOMIC_PRESENT
  23 #include <atomic>
  24 #endif
  25 #ifdef OS_WIN
  26 #include <windows.h>
  27 #endif
  28 #ifdef OS_MACOSX
  29 #include <libkern/OSAtomic.h>
  30 #endif
  31
  32 #if defined(_M_X64) || defined(__x86_64__)
  33 #define ARCH_CPU_X86_FAMILY 1
  34 #elif defined(_M_IX86) || defined(__i386__) || defined(__i386)
  35 #define ARCH_CPU_X86_FAMILY 1
  36 #elif defined(__ARMEL__)
  37 #define ARCH_CPU_ARM_FAMILY 1
  38 #elif defined(__ppc__) || defined(__powerpc__) || defined(__powerpc64__)
  39 #define ARCH_CPU_PPC_FAMILY 1
  40 #endif
  41
  42 namespace leveldb {
  43 namespace port {
  44
  45 // Define MemoryBarrier() if available
  46 // Windows on x86
  47 #if defined(OS_WIN) && defined(COMPILER_MSVC) && defined(ARCH_CPU_X86_FAMILY)
  48 // windows.h already provides a MemoryBarrier(void) macro
  49 // http://msdn.microsoft.com/en-us/library/ms684208(v=vs.85).aspx
  50 #define LEVELDB_HAVE_MEMORY_BARRIER
  51
  52 // Mac OS
  53 #elif defined(OS_MACOSX)
  54 inline void MemoryBarrier() {
  55   OSMemoryBarrier();
  56 }
  57 #define LEVELDB_HAVE_MEMORY_BARRIER
  58
  59 // Gcc on x86
  60 #elif defined(ARCH_CPU_X86_FAMILY) && defined(__GNUC__)
  61 inline void MemoryBarrier() {
  62   // See http://gcc.gnu.org/ml/gcc/2003-04/msg01180.html for a discussion on
  63   // this idiom. Also see http://en.wikipedia.org/wiki/Memory_ordering.
  64   __asm__ __volatile__("" : : : "memory");
  65 }
  66 #define LEVELDB_HAVE_MEMORY_BARRIER
  67
  68 // Sun Studio
  69 #elif defined(ARCH_CPU_X86_FAMILY) && defined(__SUNPRO_CC)
  70 inline void MemoryBarrier() {
  71   // See http://gcc.gnu.org/ml/gcc/2003-04/msg01180.html for a discussion on
  72   // this idiom. Also see http://en.wikipedia.org/wiki/Memory_ordering.
  73   asm volatile("" : : : "memory");
  74 }
  75 #define LEVELDB_HAVE_MEMORY_BARRIER
  76
  77 // ARM Linux
  78 #elif defined(ARCH_CPU_ARM_FAMILY) && defined(__linux__)
  79 typedef void (*LinuxKernelMemoryBarrierFunc)(void);
  80 // The Linux ARM kernel provides a highly optimized device-specific memory
  81 // barrier function at a fixed memory address that is mapped in every
  82 // user-level process.
  83 //
  84 // This beats using CPU-specific instructions which are, on single-core
  85 // devices, un-necessary and very costly (e.g. ARMv7-A "dmb" takes more
  86 // than 180ns on a Cortex-A8 like the one on a Nexus One). Benchmarking
  87 // shows that the extra function call cost is completely negligible on
  88 // multi-core devices.
  89 //
  90 inline void MemoryBarrier() {
  91   (*(LinuxKernelMemoryBarrierFunc)0xffff0fa0)();
  92 }
  93 #define LEVELDB_HAVE_MEMORY_BARRIER
  94
  95 // PPC
  96 #elif defined(ARCH_CPU_PPC_FAMILY) && defined(__GNUC__)
  97 inline void MemoryBarrier() {
  98   // TODO for some powerpc expert: is there a cheaper suitable variant?
  99   // Perhaps by having separate barriers for acquire and release ops.
 100   asm volatile("sync" : : : "memory");
 101 }
 102 #define LEVELDB_HAVE_MEMORY_BARRIER
 103
 104 #endif
 105
 106 // AtomicPointer built using platform-specific MemoryBarrier()
 107 #if defined(LEVELDB_HAVE_MEMORY_BARRIER)
 108 class AtomicPointer {
 109  private:
 110   void* rep_;
 111  public:
 112   AtomicPointer() { }
 113   explicit AtomicPointer(void* p) : rep_(p) {}
 114   inline void* NoBarrier_Load() const { return rep_; }
 115   inline void NoBarrier_Store(void* v) { rep_ = v; }
 116   inline void* Acquire_Load() const {
 117     void* result = rep_;
 118     MemoryBarrier();
 119     return result;
 120   }
 121   inline void Release_Store(void* v) {
 122     MemoryBarrier();
 123     rep_ = v;
 124   }
 125 };
 126
 127 // AtomicPointer based on <cstdatomic>
 128 #elif defined(LEVELDB_ATOMIC_PRESENT)
 129 class AtomicPointer {
 130  private:
 131   std::atomic<void*> rep_;
 132  public:
 133   AtomicPointer() { }
 134   explicit AtomicPointer(void* v) : rep_(v) { }
 135   inline void* Acquire_Load() const {
 136     return rep_.load(std::memory_order_acquire);
 137   }
 138   inline void Release_Store(void* v) {
 139     rep_.store(v, std::memory_order_release);
 140   }
 141   inline void* NoBarrier_Load() const {
 142     return rep_.load(std::memory_order_relaxed);
 143   }
 144   inline void NoBarrier_Store(void* v) {
 145     rep_.store(v, std::memory_order_relaxed);
 146   }
 147 };
 148
 149 // Atomic pointer based on sparc memory barriers
 150 #elif defined(__sparcv9) && defined(__GNUC__)
 151 class AtomicPointer {
 152  private:
 153   void* rep_;
 154  public:
 155   AtomicPointer() { }
 156   explicit AtomicPointer(void* v) : rep_(v) { }
 157   inline void* Acquire_Load() const {
 158     void* val;
 159     __asm__ __volatile__ (
 160         "ldx [%[rep_]], %[val] \n\t"
 161          "membar #LoadLoad|#LoadStore \n\t"
 162         : [val] "=r" (val)
 163         : [rep_] "r" (&rep_)
 164         : "memory");
 165     return val;
 166   }
 167   inline void Release_Store(void* v) {
 168     __asm__ __volatile__ (
 169         "membar #LoadStore|#StoreStore \n\t"
 170         "stx %[v], [%[rep_]] \n\t"
 171         :
 172         : [rep_] "r" (&rep_), [v] "r" (v)
 173         : "memory");
 174   }
 175   inline void* NoBarrier_Load() const { return rep_; }
 176   inline void NoBarrier_Store(void* v) { rep_ = v; }
 177 };
 178
 179 // Atomic pointer based on ia64 acq/rel
 180 #elif defined(__ia64) && defined(__GNUC__)
 181 class AtomicPointer {
 182  private:
 183   void* rep_;
 184  public:
 185   AtomicPointer() { }
 186   explicit AtomicPointer(void* v) : rep_(v) { }
 187   inline void* Acquire_Load() const {
 188     void* val    ;
 189     __asm__ __volatile__ (
 190         "ld8.acq %[val] = [%[rep_]] \n\t"
 191         : [val] "=r" (val)
 192         : [rep_] "r" (&rep_)
 193         : "memory"
 194         );
 195     return val;
 196   }
 197   inline void Release_Store(void* v) {
 198     __asm__ __volatile__ (
 199         "st8.rel [%[rep_]] = %[v]  \n\t"
 200         :
 201         : [rep_] "r" (&rep_), [v] "r" (v)
 202         : "memory"
 203         );
 204   }
 205   inline void* NoBarrier_Load() const { return rep_; }
 206   inline void NoBarrier_Store(void* v) { rep_ = v; }
 207 };
 208
 209 // We have neither MemoryBarrier(), nor <atomic>
 210 #else
 211 #error Please implement AtomicPointer for this platform.
 212
 213 #endif
 214
 215 #undef LEVELDB_HAVE_MEMORY_BARRIER
 216 #undef ARCH_CPU_X86_FAMILY
 217 #undef ARCH_CPU_ARM_FAMILY
 218 #undef ARCH_CPU_PPC_FAMILY
 219
 220 }  // namespace port
 221 }  // namespace leveldb
 222
 223 #endif  // PORT_ATOMIC_POINTER_H_