LevelDB源碼分析之四：AtomicPointer

時(shí)間：2019-10-09 10:34:01

關(guān)鍵字： leveldb atomicpointer

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]AtomicPointer 是 leveldb 提供的一個(gè)原子指針操作類，使用了基于原子操作（atomic operation）或者內(nèi)存屏障（memory barrier）的同步訪問機(jī)制，這比用鎖和信

AtomicPointer 是 leveldb 提供的一個(gè)原子指針操作類，使用了基于原子操作（atomic operation）或者內(nèi)存屏障（memory barrier）的同步訪問機(jī)制，這比用鎖和信號(hào)量的效率要高。

一.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;
}
// 使用原子操作的方式寫入，即同步的寫操作
void AtomicPointer::Release_Store(void* v) {
  InterlockedExchangePointer(&rep_, v);
}
// 不使用原子操作的方式讀取，即不同步的讀操作
void* AtomicPointer::NoBarrier_Load() const {
  return rep_;
}
// 不使用原子操作的方式寫入，即不同步的寫操作
void AtomicPointer::NoBarrier_Store(void* v) {
  rep_ = v;
}

從代碼中可以看出，AtomicPointer是基于原子操作實(shí)現(xiàn)的一個(gè)原子指針操作類，通過原子操作實(shí)現(xiàn)多線程的讀寫同步。原子操作，即不可分割開的操作。該操作一定是在同一個(gè)CPU時(shí)間片中完成，這樣即使線程被切換，多個(gè)線程也不會(huì)看到同一塊內(nèi)存中不完整的數(shù)據(jù)。

這里同步?jīng)]有用到鎖，所以涉及到了無鎖編程（Lock-Free）的概念。

二.無鎖編程

無鎖編程具體使用和考慮到的技術(shù)方法包括：原子操作（atomic operation）、內(nèi)存柵欄（memory barrier）、內(nèi)存順序沖突（memory order）、指令序列一致性（sequential consistency）等等。之所以會(huì)出現(xiàn)無鎖編程技術(shù)，因?yàn)榛阪i的編程的有如下缺點(diǎn)。
多線程編程是多CPU（多核CPU或者多個(gè)CPU）系統(tǒng)在中應(yīng)用最廣泛的一種編程方式，在傳統(tǒng)的多線程編程中，多線程之間一般用各種鎖的機(jī)制來保證正確的對(duì)共享資源（share resources）進(jìn)行訪問和操作。在多線程編程中只要需要共享某些數(shù)據(jù)，就應(yīng)當(dāng)將對(duì)它的訪問串行化。比如像++count(count是整型變量)這樣的簡單操作也得加鎖，因?yàn)榧幢闶窃隽坎僮鬟@樣的操作，在匯編代碼中實(shí)際上也是分三步進(jìn)行的：讀、改、寫（回）。

movl x, %eax
addl $1, %eax
movl %eax, x

更進(jìn)一步，甚至內(nèi)存變量的賦值操作都不能保證是原子的，比如在32位環(huán)境下運(yùn)行這樣的函數(shù)
void setValue()?
{?
? ? ?value = 0x100000006;?
}
所有的C/C++操作被認(rèn)定為非原子的。執(zhí)行的過程中，這兩條指令之間也是可以被打斷的，而不是一條原子操作（也就是所謂的寫撕裂），所以修改共享數(shù)據(jù)的操作必須以原子操作的形式出現(xiàn)，這樣才能保證沒有其它線程能在中途插一腳來破壞相應(yīng)數(shù)據(jù)。
而在使用鎖機(jī)制的過程中，即便在鎖的粒度（granularity）、負(fù)載（overhead）、競爭（contention）、死鎖（deadlock）等需要重點(diǎn)控制的方面解決的很好，也無法徹底避免這種機(jī)制的如下一些缺點(diǎn)：
1、鎖機(jī)制會(huì)引起線程的阻塞（block），對(duì)于沒有能占用到鎖的線程或者進(jìn)程，將一直等待到鎖的占有者釋放鎖資源后才能繼續(xù)執(zhí)行，而等待時(shí)間理論上是不可設(shè)置和預(yù)估的。

2、申請(qǐng)和釋放鎖的操作，增加了很多訪問共享資源的消耗，尤其是在鎖競爭(lock-contention)很嚴(yán)重的時(shí)候，比如這篇文章所說

Locks Aren't Slow; Lock Contention Is

3、現(xiàn)有實(shí)現(xiàn)的各種鎖機(jī)制，都不能很好的避免編程開發(fā)者設(shè)計(jì)實(shí)現(xiàn)的程序出現(xiàn)死鎖或者活鎖的可能
4、優(yōu)先級(jí)反轉(zhuǎn)（prorithy inversion）和鎖護(hù)送(Convoying)的現(xiàn)象
5、難以調(diào)試
無鎖編程（Lock-Free）就是在某些應(yīng)用場景和領(lǐng)域下解決以上基于鎖機(jī)制的并發(fā)編程的一種方案。
無鎖編程的概念做一般應(yīng)用層開發(fā)的會(huì)較少接觸到，因?yàn)槎嗑€程的時(shí)候?qū)蚕碣Y源的操作一般是用鎖來完成的。鎖本身對(duì)這個(gè)任務(wù)完成的很好，但是存在性能的問題，也就是在對(duì)性能要求很高的，高并發(fā)的場景下，鎖會(huì)帶來性能瓶頸。所以在一些如數(shù)據(jù)庫這樣的應(yīng)用或者linux 內(nèi)核里經(jīng)常會(huì)看到一些無鎖的并發(fā)編程。

鎖是一個(gè)高層次的接口，隱藏了很多并發(fā)編程時(shí)會(huì)出現(xiàn)的非常古怪的問題。當(dāng)不用鎖的時(shí)候，就要考慮這些問題。主要有兩個(gè)方面的影響：編譯器對(duì)指令的排序和cpu對(duì)指令的排序。它們排序的目的主要是優(yōu)化和提高效率。排序的原則是在單核單線程下最終的效果不會(huì)發(fā)生改變。單核多線程的時(shí)候，編譯器的亂序就會(huì)帶來問題，多核的時(shí)候，又會(huì)涉及cpu對(duì)指令的亂序。memory-ordering-at-compile-time和memory-reordering-caught-in-the-act里提到了亂序?qū)е碌膯栴}。

除了Windows版本，源碼中還提供了AtomicPointer的另外兩種實(shí)現(xiàn)。源文件位置：leveldb/port/atomic_pointer.h?
三.利用std::atomic實(shí)現(xiàn)AtomicPointer
std::atomic是C++11提供的原子模板類，std::atomic對(duì)int、char、 bool等數(shù)據(jù)類型進(jìn)行原子性封裝。原子類型對(duì)象的主要特點(diǎn)就是從不同線程訪問不會(huì)導(dǎo)致數(shù)據(jù)競爭(data race)。從不同線程訪問某個(gè)原子對(duì)象是良性 (well-defined) 行為，而通常對(duì)于非原子類型而言，并發(fā)訪問某個(gè)對(duì)象（如果不做任何同步操作）會(huì)導(dǎo)致未定義 (undifined) 行為發(fā)生。因此使用std::atomic可實(shí)現(xiàn)數(shù)據(jù)同步的無鎖設(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

四.利用內(nèi)存屏障來實(shí)現(xiàn)AtomicPointer

// 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;
  }
};
#endif

從上面可以看出各個(gè)平臺(tái)都有相應(yīng)的MemoryBarrier()實(shí)現(xiàn)，比如說windows平臺(tái)已經(jīng)定義過MemoryBarrier(void)宏，可以直接使用。而linux平臺(tái)的gcc則通過內(nèi)聯(lián)一條匯編指令__asm__ __volatile__("" : : : "memory");來自定義MemoryBarrier()。
MemoryBarrier()的作用是添加內(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í)行順序，如果你是在單線程上運(yùn)行可能會(huì)正常，但是在多線程環(huán)境很可能會(huì)發(fā)生問題(如果你的程序?qū)χ噶畹膱?zhí)行順序有嚴(yán)格的要求)。而內(nèi)存屏障就可以阻止編譯器在編譯期間優(yōu)化我們的指令順序，為你的程序在多線程環(huán)境下的正確運(yùn)行提供了保障，但是不能阻止 CPU 在運(yùn)行時(shí)重新排序指令。
舉個(gè)例子，有下面的代碼：

a = b = 0;
//thread1
a = 1
b = 2

//thread2
if (b == 2) {
   //這時(shí)a是1嗎？
}

假設(shè)只有單核單線程1的時(shí)候，由于a和 b的賦值沒有關(guān)系，因此編譯器可能會(huì)先賦值b然后賦值a，注意單線程的情況下是沒有問題的，但是如果還有線程2，那么就不能保證線程2看到b為2 的時(shí)候a就為1。再假設(shè)線程1改為如下的代碼：

a = 1
complier_fence()
b = 2

其中complier_fence()為一條阻止編譯器在fence前后亂序的指令，x86/64下可以是下面的匯編語句，也可以由其他語言提供的語句保證。asm volatile(“” ::: “memory”);此時(shí)我們能保證b的賦值一定發(fā)生在a賦值之后。那么此時(shí)線程2的邏輯是對(duì)的嗎？還不能保證。因?yàn)榫€程2可能會(huì)先讀取a的舊值，然后再讀取b的值。從編譯器來看a和b之間沒有關(guān)聯(lián)，因此這樣的優(yōu)化是可能發(fā)生的。所以線程2也需要加上編譯器級(jí)的屏障。

if (b == 2) {
   complier_fence()
   //這時(shí)a是1嗎？
}

加上了這些保證，編譯器輸出的指令能確保a，b之間的順序性。注意a，b的賦值也可以換成更復(fù)雜的語句，屏障保證了屏障之前的讀寫一定發(fā)生在屏障之后的讀寫之前，但是屏障前后內(nèi)部的原子性和順序性是沒有保證的。
當(dāng)把這樣的程序放到多核的環(huán)境上運(yùn)行的時(shí)候，a，b賦值之間的順序性又沒有保證了。這是由于多核CPU在執(zhí)行編譯器排序好的指令的時(shí)候還是會(huì)亂序執(zhí)行。這個(gè)問題在memory-barriers-are-like-source-control-operations里有很好的解釋。這里不再多說。

同樣的，為了解決這樣的問題，語言上有一些語句提供屏障的效果，保證屏障前后指令執(zhí)行的順序性。而且，慶幸的是，一般能保證CPU內(nèi)存屏障的語句也會(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.

因此在x86/64上可以不用考慮CPU的內(nèi)存屏障，只需要在必要的時(shí)候考慮編譯器的亂序問題即可。

回到leveldb里的AtomicPointer，注意到其中幾個(gè)成員函數(shù)都是inline，如果不是inline，其實(shí)沒有必要加上內(nèi)存屏障，因?yàn)楹瘮?shù)能夠提供很強(qiáng)的內(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.

下面針對(duì)Acquire_Load和Release_Store假設(shè)一個(gè)場景：

//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來說，在指令后插入Store Barrier，能讓寫入緩存中的最新數(shù)據(jù)更新寫入主內(nèi)存，讓其他線程可見。

對(duì)于Load Barrier來說，在指令前插入Load Barrier，可以讓高速緩存中的數(shù)據(jù)失效，強(qiáng)制從新從主內(nèi)存加載數(shù)據(jù)。

注意acquire，release模型適合單生產(chǎn)者和單消費(fèi)者的模型，如果有多個(gè)生產(chǎn)者，那么現(xiàn)有的保障是不足的，會(huì)涉及到原子性的問題。

參考鏈接：

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ā)編程系列之一：鎖的意義