LevelDB源碼分析之四：AtomicPointer
一.Windows版本的AtomicPointer實(shí)現(xiàn)
先上源碼，這個(gè)是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;
}
// 使用原子操作的方式寫(xiě)入，即同步的寫(xiě)操作
void AtomicPointer::Release_Store(void* v) {
InterlockedExchangePointer(&rep_, v);
}
// 不使用原子操作的方式讀取，即不同步的讀操作
void* AtomicPointer::NoBarrier_Load() const {
return rep_;
}
// 不使用原子操作的方式寫(xiě)入，即不同步的寫(xiě)操作
void AtomicPointer::NoBarrier_Store(void* v) {
rep_ = v;
}這里同步?jīng)]有用到鎖，所以涉及到了無(wú)鎖編程（Lock-Free）的概念。
二.無(wú)鎖編程
無(wú)鎖編程具體使用和考慮到的技術(shù)方法包括：原子操作（atomic operation）、內(nèi)存柵欄（memory barrier）、內(nèi)存順序沖突（memory order）、 指令序列一致性（sequential consistency）等等。之所以會(huì)出現(xiàn)無(wú)鎖編程技術(shù)，因?yàn)榛阪i的編程的有如下缺點(diǎn)。多線(xiàn)程編程是多CPU（多核CPU或者多個(gè)CPU）系統(tǒng)在中應(yīng)用最廣泛的一種編程方式，在傳統(tǒng)的多線(xiàn)程編程中，多線(xiàn)程之間一般用各種鎖的機(jī)制來(lái)保證正確的對(duì)共享資源（share resources）進(jìn)行訪(fǎng)問(wèn)和操作。在多線(xiàn)程編程中只要需要共享某些數(shù)據(jù)，就應(yīng)當(dāng)將對(duì)它的訪(fǎng)問(wèn)串行化。比如像++count(count是整型變量)這樣的簡(jiǎn)單操作也得加鎖，因?yàn)榧幢闶窃隽坎僮鬟@樣的操作，在匯編代碼中實(shí)際上也是分三步進(jìn)行的：讀、改、寫(xiě)（回）。
movl x, %eax
addl $1, %eax
movl %eax, xvoid setValue()?
{?
? ? ?value = 0x100000006;?
}
所有的C/C++操作被認(rèn)定為非原子的。執(zhí)行的過(guò)程中，這兩條指令之間也是可以被打斷的，而不是一條原子操作（也就是所謂的寫(xiě)撕裂），所以修改共享數(shù)據(jù)的操作必須以原子操作的形式出現(xiàn)，這樣才能保證沒(méi)有其它線(xiàn)程能在中途插一腳來(lái)破壞相應(yīng)數(shù)據(jù)。
而在使用鎖機(jī)制的過(guò)程中，即便在鎖的粒度（granularity）、負(fù)載（overhead）、競(jìng)爭(zhēng)（contention）、死鎖（deadlock）等需要重點(diǎn)控制的方面解決的很好，也無(wú)法徹底避免這種機(jī)制的如下一些缺點(diǎn)：
1、鎖機(jī)制會(huì)引起線(xiàn)程的阻塞（block），對(duì)于沒(méi)有能占用到鎖的線(xiàn)程或者進(jìn)程，將一直等待到鎖的占有者釋放鎖資源后才能繼續(xù)執(zhí)行，而等待時(shí)間理論上是不可設(shè)置和預(yù)估的。
2、申請(qǐng)和釋放鎖的操作，增加了很多訪(fǎng)問(wèn)共享資源的消耗，尤其是在鎖競(jìng)爭(zhēng)(lock-contention)很?chē)?yán)重的時(shí)候，比如這篇文章所說(shuō)
Locks Aren't Slow; Lock Contention Is
3、現(xiàn)有實(shí)現(xiàn)的各種鎖機(jī)制，都不能很好的避免編程開(kāi)發(fā)者設(shè)計(jì)實(shí)現(xiàn)的程序出現(xiàn)死鎖或者活鎖的可能4、優(yōu)先級(jí)反轉(zhuǎn)（prorithy inversion）和鎖護(hù)送(Convoying)的現(xiàn)象
5、難以調(diào)試
無(wú)鎖編程（Lock-Free）就是在某些應(yīng)用場(chǎng)景和領(lǐng)域下解決以上基于鎖機(jī)制的并發(fā)編程的一種方案。
無(wú)鎖編程的概念做一般應(yīng)用層開(kāi)發(fā)的會(huì)較少接觸到，因?yàn)槎嗑€(xiàn)程的時(shí)候?qū)蚕碣Y源的操作一般是用鎖來(lái)完成的。鎖本身對(duì)這個(gè)任務(wù)完成的很好，但是存在性能的問(wèn)題，也就是在對(duì)性能要求很高的，高并發(fā)的場(chǎng)景下，鎖會(huì)帶來(lái)性能瓶頸。所以在一些如數(shù)據(jù)庫(kù)這樣的應(yīng)用或者linux 內(nèi)核里經(jīng)常會(huì)看到一些無(wú)鎖的并發(fā)編程。
鎖是一個(gè)高層次的接口，隱藏了很多并發(fā)編程時(shí)會(huì)出現(xiàn)的非常古怪的問(wèn)題。當(dāng)不用鎖的時(shí)候，就要考慮這些問(wèn)題。主要有兩個(gè)方面的影響：編譯器對(duì)指令的排序和cpu對(duì)指令的排序。它們排序的目的主要是優(yōu)化和提高效率。排序的原則是在單核單線(xiàn)程下最終的效果不會(huì)發(fā)生改變。單核多線(xiàn)程的時(shí)候，編譯器的亂序就會(huì)帶來(lái)問(wèn)題，多核的時(shí)候，又會(huì)涉及cpu對(duì)指令的亂序。memory-ordering-at-compile-time和memory-reordering-caught-in-the-act里提到了亂序?qū)е碌膯?wèn)題。
除了Windows版本，源碼中還提供了AtomicPointer的另外兩種實(shí)現(xiàn)。源文件位置：leveldb/port/atomic_pointer.h?三.利用std::atomic實(shí)現(xiàn)AtomicPointer
std::atomic是C++11提供的原子模板類(lèi)，std::atomic對(duì)int、char、 bool等數(shù)據(jù)類(lèi)型進(jìn)行原子性封裝。原子類(lèi)型對(duì)象的主要特點(diǎn)就是從不同線(xiàn)程訪(fǎng)問(wèn)不會(huì)導(dǎo)致數(shù)據(jù)競(jìng)爭(zhēng)(data race)。從不同線(xiàn)程訪(fǎng)問(wèn)某個(gè)原子對(duì)象是良性 (well-defined) 行為，而通常對(duì)于非原子類(lèi)型而言，并發(fā)訪(fǎng)問(wèn)某個(gè)對(duì)象（如果不做任何同步操作）會(huì)導(dǎo)致未定義 (undifined) 行為發(fā)生。因此使用std::atomic可實(shí)現(xiàn)數(shù)據(jù)同步的無(wú)鎖設(shè)計(jì)。
#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)存屏障，當(dāng)這個(gè)MemoryBarrier()之前的代碼修改了某個(gè)變量的內(nèi)存值后，其他 CPU 和緩存 (Cache) 中的該變量的值將會(huì)失效，必須重新從內(nèi)存中獲取該變量的值。
內(nèi)存屏障的基本用途是避免編譯器優(yōu)化指令 。有些編譯器默認(rèn)會(huì)在編譯期間對(duì)代碼進(jìn)行優(yōu)化，從而改變匯編代碼的指令執(zhí)行順序，如果你是在單線(xiàn)程上運(yùn)行可能會(huì)正常，但是在多線(xiàn)程環(huán)境很可能會(huì)發(fā)生問(wèn)題(如果你的程序?qū)χ噶畹膱?zhí)行順序有嚴(yán)格的要求)。而內(nèi)存屏障就可以阻止編譯器在編譯期間優(yōu)化我們的指令順序，為你的程序在多線(xiàn)程環(huán)境下的正確運(yùn)行提供了保障，但是不能阻止 CPU 在運(yùn)行時(shí)重新排序指令。
舉個(gè)例子，有下面的代碼：
a = b = 0;
//thread1
a = 1
b = 2
//thread2
if (b == 2) {
//這時(shí)a是1嗎？
}a = 1
complier_fence()
b = 2if (b == 2) {
complier_fence()
//這時(shí)a是1嗎？
}當(dāng)把這樣的程序放到多核的環(huán)境上運(yùn)行的時(shí)候，a，b賦值之間的順序性又沒(méi)有保證了。這是由于多核CPU在執(zhí)行編譯器排序好的指令的時(shí)候還是會(huì)亂序執(zhí)行。這個(gè)問(wèn)題在memory-barriers-are-like-source-control-operations里有很好的解釋。這里不再多說(shuō)。
同樣的，為了解決這樣的問(wèn)題，語(yǔ)言上有一些語(yǔ)句提供屏障的效果，保證屏障前后指令執(zhí)行的順序性。而且，慶幸的是，一般能保證CPU內(nèi)存屏障的語(yǔ)句也會(huì)自動(dòng)保證編譯器級(jí)的屏障。注意，不同的CPU的內(nèi)存模型（即對(duì)內(nèi)存中的指令的執(zhí)行順序如何進(jìn)行的模型）是不一樣的，很辛運(yùn)的，x86/64是的內(nèi)存模型是強(qiáng)內(nèi)存模型，它對(duì)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，注意到其中幾個(gè)成員函數(shù)都是inline，如果不是inline，其實(shí)沒(méi)有必要加上內(nèi)存屏障，因?yàn)楹瘮?shù)能夠提供很強(qiáng)的內(nèi)存屏障保證。下面這段話(huà)摘自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對(duì)于Store Barrier來(lái)說(shuō)，在指令后插入Store Barrier，能讓寫(xiě)入緩存中的最新數(shù)據(jù)更新寫(xiě)入主內(nèi)存，讓其他線(xiàn)程可見(jiàn)。
注意acquire，release模型適合單生產(chǎn)者和單消費(fèi)者的模型，如果有多個(gè)生產(chǎn)者，那么現(xiàn)有的保障是不足的，會(huì)涉及到原子性的問(wè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ā)編程系列之一：鎖的意義
下載文檔
