LevelDB源碼分析之四：AtomicPointer
一.Windows版本的AtomicPointer實現(xiàn)
先上源碼，這個是Windows版本的源碼，源文件位置：leveldb/port/port_win.h和leveldb/port/port_win.cc
class AtomicPointer {
private:
void * rep_;
public:
AtomicPointer() : rep_(nullptr) { }
explicit AtomicPointer(void* v);
void* Acquire_Load() const;
void Release_Store(void* v);
void* NoBarrier_Load() const;
void NoBarrier_Store(void* v);
};AtomicPointer::AtomicPointer(void* v) {
Release_Store(v);
}
// 使用原子操作的方式讀取，即同步的讀操作
void* AtomicPointer::Acquire_Load() const {
void * p = nullptr;
InterlockedExchangePointer(&p, rep_);
return p;
}
// 使用原子操作的方式寫入，即同步的寫操作
void AtomicPointer::Release_Store(void* v) {
InterlockedExchangePointer(&rep_, v);
}
// 不使用原子操作的方式讀取，即不同步的讀操作
void* AtomicPointer::NoBarrier_Load() const {
return rep_;
}
// 不使用原子操作的方式寫入，即不同步的寫操作
void AtomicPointer::NoBarrier_Store(void* v) {
rep_ = v;
}這里同步?jīng)]有用到鎖，所以涉及到了無鎖編程（Lock-Free）的概念。
二.無鎖編程
無鎖編程具體使用和考慮到的技術(shù)方法包括：原子操作（atomic operation）、內(nèi)存柵欄（memory barrier）、內(nèi)存順序沖突（memory order）、 指令序列一致性（sequential consistency）等等。之所以會出現(xiàn)無鎖編程技術(shù)，因為基于鎖的編程的有如下缺點。多線程編程是多CPU（多核CPU或者多個CPU）系統(tǒng)在中應(yīng)用最廣泛的一種編程方式，在傳統(tǒng)的多線程編程中，多線程之間一般用各種鎖的機制來保證正確的對共享資源（share resources）進行訪問和操作。在多線程編程中只要需要共享某些數(shù)據(jù)，就應(yīng)當將對它的訪問串行化。比如像++count(count是整型變量)這樣的簡單操作也得加鎖，因為即便是增量操作這樣的操作，在匯編代碼中實際上也是分三步進行的：讀、改、寫（回）。
movl x, %eax
addl $1, %eax
movl %eax, xvoid setValue()?
{?
? ? ?value = 0x100000006;?
}
所有的C/C++操作被認定為非原子的。執(zhí)行的過程中，這兩條指令之間也是可以被打斷的，而不是一條原子操作（也就是所謂的寫撕裂），所以修改共享數(shù)據(jù)的操作必須以原子操作的形式出現(xiàn)，這樣才能保證沒有其它線程能在中途插一腳來破壞相應(yīng)數(shù)據(jù)。
而在使用鎖機制的過程中，即便在鎖的粒度（granularity）、負載（overhead）、競爭（contention）、死鎖（deadlock）等需要重點控制的方面解決的很好，也無法徹底避免這種機制的如下一些缺點：
1、鎖機制會引起線程的阻塞（block），對于沒有能占用到鎖的線程或者進程，將一直等待到鎖的占有者釋放鎖資源后才能繼續(xù)執(zhí)行，而等待時間理論上是不可設(shè)置和預(yù)估的。
2、申請和釋放鎖的操作，增加了很多訪問共享資源的消耗，尤其是在鎖競爭(lock-contention)很嚴重的時候，比如這篇文章所說
Locks Aren't Slow; Lock Contention Is
3、現(xiàn)有實現(xiàn)的各種鎖機制，都不能很好的避免編程開發(fā)者設(shè)計實現(xiàn)的程序出現(xiàn)死鎖或者活鎖的可能4、優(yōu)先級反轉(zhuǎn)（prorithy inversion）和鎖護送(Convoying)的現(xiàn)象
5、難以調(diào)試
無鎖編程（Lock-Free）就是在某些應(yīng)用場景和領(lǐng)域下解決以上基于鎖機制的并發(fā)編程的一種方案。
無鎖編程的概念做一般應(yīng)用層開發(fā)的會較少接觸到，因為多線程的時候?qū)蚕碣Y源的操作一般是用鎖來完成的。鎖本身對這個任務(wù)完成的很好，但是存在性能的問題，也就是在對性能要求很高的，高并發(fā)的場景下，鎖會帶來性能瓶頸。所以在一些如數(shù)據(jù)庫這樣的應(yīng)用或者linux 內(nèi)核里經(jīng)常會看到一些無鎖的并發(fā)編程。
鎖是一個高層次的接口，隱藏了很多并發(fā)編程時會出現(xiàn)的非常古怪的問題。當不用鎖的時候，就要考慮這些問題。主要有兩個方面的影響：編譯器對指令的排序和cpu對指令的排序。它們排序的目的主要是優(yōu)化和提高效率。排序的原則是在單核單線程下最終的效果不會發(fā)生改變。單核多線程的時候，編譯器的亂序就會帶來問題，多核的時候，又會涉及cpu對指令的亂序。memory-ordering-at-compile-time和memory-reordering-caught-in-the-act里提到了亂序?qū)е碌膯栴}。
除了Windows版本，源碼中還提供了AtomicPointer的另外兩種實現(xiàn)。源文件位置：leveldb/port/atomic_pointer.h?三.利用std::atomic實現(xiàn)AtomicPointer
std::atomic是C++11提供的原子模板類，std::atomic對int、char、 bool等數(shù)據(jù)類型進行原子性封裝。原子類型對象的主要特點就是從不同線程訪問不會導致數(shù)據(jù)競爭(data race)。從不同線程訪問某個原子對象是良性 (well-defined) 行為，而通常對于非原子類型而言，并發(fā)訪問某個對象（如果不做任何同步操作）會導致未定義 (undifined) 行為發(fā)生。因此使用std::atomic可實現(xiàn)數(shù)據(jù)同步的無鎖設(shè)計。
#if defined(LEVELDB_CSTDATOMIC_PRESENT)
class AtomicPointer {
private:
std::atomic rep_;
public:
AtomicPointer() { }
explicit AtomicPointer(void* v) : rep_(v) { }
inline void* Acquire_Load() const {
return rep_.load(std::memory_order_acquire);
}
inline void Release_Store(void* v) {
rep_.store(v, std::memory_order_release);
}
inline void* NoBarrier_Load() const {
return rep_.load(std::memory_order_relaxed);
}
inline void NoBarrier_Store(void* v) {
rep_.store(v, std::memory_order_relaxed);
}
};
#endif // Define MemoryBarrier() if available
// Windows on x86
#if defined(OS_WIN) && defined(COMPILER_MSVC) && defined(ARCH_CPU_X86_FAMILY)
// windows.h already provides a MemoryBarrier(void) macro
// http://msdn.microsoft.com/en-us/library/ms684208(v=vs.85).aspx
#define LEVELDB_HAVE_MEMORY_BARRIER
// Gcc on x86
#elif defined(ARCH_CPU_X86_FAMILY) && defined(__GNUC__)
inline void MemoryBarrier() {
// See http://gcc.gnu.org/ml/gcc/2003-04/msg01180.html for a discussion on
// this idiom. Also see http://en.wikipedia.org/wiki/Memory_ordering.
__asm__ __volatile__("" : : : "memory");
}
#define LEVELDB_HAVE_MEMORY_BARRIER
// Sun Studio
#elif defined(ARCH_CPU_X86_FAMILY) && defined(__SUNPRO_CC)
inline void MemoryBarrier() {
// See http://gcc.gnu.org/ml/gcc/2003-04/msg01180.html for a discussion on
// this idiom. Also see http://en.wikipedia.org/wiki/Memory_ordering.
asm volatile("" : : : "memory");
}
#define LEVELDB_HAVE_MEMORY_BARRIER
// Mac OS
#elif defined(OS_MACOSX)
inline void MemoryBarrier() {
OSMemoryBarrier();
}
#define LEVELDB_HAVE_MEMORY_BARRIER
// ARM
#elif defined(ARCH_CPU_ARM_FAMILY)
typedef void (*LinuxKernelMemoryBarrierFunc)(void);
LinuxKernelMemoryBarrierFunc pLinuxKernelMemoryBarrier __attribute__((weak)) =
(LinuxKernelMemoryBarrierFunc) 0xffff0fa0;
inline void MemoryBarrier() {
pLinuxKernelMemoryBarrier();
}
#define LEVELDB_HAVE_MEMORY_BARRIER
#endif
// AtomicPointer built using platform-specific MemoryBarrier()
#if defined(LEVELDB_HAVE_MEMORY_BARRIER)
class AtomicPointer {
private:
void* rep_;
public:
AtomicPointer() { }
explicit AtomicPointer(void* p) : rep_(p) {}
inline void* NoBarrier_Load() const { return rep_; }
inline void NoBarrier_Store(void* v) { rep_ = v; }
inline void* Acquire_Load() const {
void* result = rep_;
MemoryBarrier();
return result;
}
inline void Release_Store(void* v) {
MemoryBarrier();
rep_ = v;
}
};
#endifMemoryBarrier()的作用是添加內(nèi)存屏障，當這個MemoryBarrier()之前的代碼修改了某個變量的內(nèi)存值后，其他 CPU 和緩存 (Cache) 中的該變量的值將會失效，必須重新從內(nèi)存中獲取該變量的值。
內(nèi)存屏障的基本用途是避免編譯器優(yōu)化指令 。有些編譯器默認會在編譯期間對代碼進行優(yōu)化，從而改變匯編代碼的指令執(zhí)行順序，如果你是在單線程上運行可能會正常，但是在多線程環(huán)境很可能會發(fā)生問題(如果你的程序?qū)χ噶畹膱?zhí)行順序有嚴格的要求)。而內(nèi)存屏障就可以阻止編譯器在編譯期間優(yōu)化我們的指令順序，為你的程序在多線程環(huán)境下的正確運行提供了保障，但是不能阻止 CPU 在運行時重新排序指令。
舉個例子，有下面的代碼：
a = b = 0;
//thread1
a = 1
b = 2
//thread2
if (b == 2) {
//這時a是1嗎？
}a = 1
complier_fence()
b = 2if (b == 2) {
complier_fence()
//這時a是1嗎？
}當把這樣的程序放到多核的環(huán)境上運行的時候，a，b賦值之間的順序性又沒有保證了。這是由于多核CPU在執(zhí)行編譯器排序好的指令的時候還是會亂序執(zhí)行。這個問題在memory-barriers-are-like-source-control-operations里有很好的解釋。這里不再多說。
同樣的，為了解決這樣的問題，語言上有一些語句提供屏障的效果，保證屏障前后指令執(zhí)行的順序性。而且，慶幸的是，一般能保證CPU內(nèi)存屏障的語句也會自動保證編譯器級的屏障。注意，不同的CPU的內(nèi)存模型（即對內(nèi)存中的指令的執(zhí)行順序如何進行的模型）是不一樣的，很辛運的，x86/64是的內(nèi)存模型是強內(nèi)存模型，它對CUP的亂序執(zhí)行的影響是最小的。
A strong hardware memory model is one in which every machine instruction comes implicitly withacquire and release semantics. As a result, when one CPU core performs a sequence of writes, every other CPU core sees those values
change in the same order that they were written.
回到leveldb里的AtomicPointer，注意到其中幾個成員函數(shù)都是inline，如果不是inline，其實沒有必要加上內(nèi)存屏障，因為函數(shù)能夠提供很強的內(nèi)存屏障保證。下面這段話摘自memory-ordering-at-compile-time：
In fact, the majority of function calls act as compiler barriers, whether they contain their own compiler barrier or not. This excludes inline functions, functions declared with thepure attribute, and cases where link-time code
generation is used. Other than those cases, a call to an external function is even stronger than a compiler barrier, since the compiler has no idea what the function’s side effects will be. It must forget any assumptions it made about memory that is potentially
visible to that function.
//thread1
Object.var1 = a;
Object.var2 = b;
Object.var2 = c;
atomicpointer.Release_Store(p);
//thread2
user_pointer = atomicpointer.Acquire_Load();
get Object.var1
get Object.var2
get Object.var3對于Store Barrier來說，在指令后插入Store Barrier，能讓寫入緩存中的最新數(shù)據(jù)更新寫入主內(nèi)存，讓其他線程可見。
注意acquire，release模型適合單生產(chǎn)者和單消費者的模型，如果有多個生產(chǎn)者，那么現(xiàn)有的保障是不足的，會涉及到原子性的問題。
參考鏈接：
Locks Aren't Slow; Lock Contention Is
memory-ordering-at-compile-time
memory-reordering-caught-in-the-act
An Introduction to Lock-Free Programming
Acquire and Release Fences
Memory Barriers Are Like Source Control Operations
Acquire and Release Semantics
并發(fā)編程系列之一：鎖的意義
下載文檔
