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