x86系統cache locking的原理

cmpxchg 本身不是原子的，需要加 lock 才是原子的，而 lock 是通過鎖記憶體總線來實作原子性的。

記憶體總線就一條，是獨占的，不管你是多核還是單核，同一時間，隻有一個能占用總線.

占用總線的，可以是 CPU 的核，也可以是 DMA 等能通路記憶體的裝置，一般叫 bus master。一個元器件讀記憶體時就會占用總線，讀完後再解除對總線的占用，其它元器件才能進總線繼續通路記憶體，任何元器件不會在一次讀記憶體的中間時刻解除對總線的占用，是以，對記憶體的一個讀操作是原子的。寫記憶體同理。但 cmpxchg 這類指令對于記憶體的通路不止一次，它是一次讀加一次寫，所謂 read-modify-write 操作。這樣的話，由于讀和寫是兩個單獨的操作，會分别占用總線，而不是持續占用總線，是以不是原子的，讀和寫之間可能會有其它元器件對記憶體的通路。是以，為了實作 cmpxchg 的原子操作，需要在指令前加上 lock 字首。

cmpxchg 指令讀取目的記憶體操作數，與寄存器中值比對，如果相同，則将新值寫到目的記憶體位址。加上 lock 後，讀記憶體時，會對記憶體總線發出 LOCK 信号，鎖住總線，這個鎖，要到将新值寫到目的記憶體位址後才會解除，是以，加上 lock 字首的 cmpxchg 指令在讀與寫之間是不會有其它元器件對記憶體進行通路的，是以是原子的。

當 CPU 為單核時，盡管 cmpxchg 要通路兩次記憶體，但在該指令執行過程中，不會有其它的核來打斷指令執行過程（中斷不會發生在單條指令執行過程中，隻會發生在指令執行前後），是以，在讀與寫之間也就不會有其它核去通路記憶體，是以單核 CPU 不用加 lock 字首就已經是原子的了。（但是由于 DMA 的存在，理論上也存在 DMA 與 CPU 通路同一塊 lock 記憶體的情況）

以上是我對 CPU 直接通路記憶體時的 cmpxchg 指令的了解。

然後說說當記憶體已經在 CPU Cache 裡時，cmpxchg 的 lock 細節。

在 Intel 手冊中有這麼一段（卷3 8.1.4）：

For the Intel486 and Pentium processors, the LOCK# signal is always asserted on the bus during a LOCK operation, even if the area of memory being locked is cached in the processor.

For the P6 and more recent processor families, if the area of memory being locked during a LOCK operation is cached in the processor that is performing the LOCK operation as write-back memory and is completely contained in a cache line, the processor may not assert the LOCK# signal on the bus. Instead, it will modify the memory location internally and allow it’s cache coherency mechanism to ensure that the operation is carried out atomically. This operation is called “cache locking. “ The cache coherency mechanism automatically prevents two or more processors that have cached the same area of memory from simultaneously modifying data in that area.

就是說 Intel 486 和 Pentium 處理器，LOCK# 信号總是會發到總線去，即使要鎖的記憶體區域已經在 CPU Cache 中了。《Pentium Processor System Architecture》證明的确如此。

而 P6 和更新的處理器則不同，如果要鎖的記憶體已經在 cache 中，而且在一個 cache 行内（一般 64 個位元組為一行），記憶體模式又是 write-back 的話，那麼處理器 可能 不會發 LOCK# 信号到總線上。它會直接改 cache，然後交給 cache 一緻性機制去保證操作的原子性。cache 一緻性機制能保證多核不會同時修改同一塊被緩存的記憶體區域。

一開始，我并沒有往深了去想，後來看了那篇知乎文章，作者認為 P6 和更新的處理器直接就再也不往總線發 LOCK# 信号了，一切都交給 cache 一緻性去解決，我對此有了疑惑，于是開始進一步探究。

首先什麼是 write-back 的記憶體模式？

根據 Intel 手冊第3卷 11。3 所述：

Write-back(WB) —— Writes and reads to and from system memory are cached. Reads come from cache lines on cache hits; read misses cause cache fills. Speculative reads are allowed. Write misses cause cache line fills (in processor families starting with the P6 family processors), and writes are performed entirely in the cache, when possible. Write combining is allowed. The write-back memory type reduces bus traffic by eliminating many unnecessary writes to system memory. Writes to a cache line are not immediately forwarded to system memory; instead, they are accumulated in the cache. The modified cache lines are written to system memory later, when a write-back operation is performed. Write-back operations are triggered when cache lines need to be deallocated, such as when new cache lines are being allocated in a cache that is already full. They also are triggered by the mechanisms used to maintain cache consistency. This type of cache-control provides the best performance, but it requires that all devices that access system memory on the system bus be able to snoop memory accesses to insure system memory and cache coherency.

可以看到，Write-back 模式下，CPU 隻和 cache 打交道，不管讀還是寫，都不直接通路記憶體。但是上面寫到 「writes are performed entirely in the cache，when possible.」，也就是說寫還是有例外情況的，雖然不知道它這裡的 impossible 具體是什麼情況，暫且擱下不管。

那麼這樣的話，CPU 完全從 cache 讀寫，LOCK# 信号就一定不會出現在記憶體總線了，但文檔中為什麼用的詞是 可能 呢？難道，正是 ‘when possible’ 的例外情況？

知乎文章的作者認為，在這種情況下，兩個核同時執行 cmpxchg 時，兩者都會判斷成功，然後都去寫那塊記憶體，然後 cache 一緻性機制會有 cache 總線仲裁機制，判定隻有一個寫成功，另一個需要失效自己的緩存，并從寫成功的那個核的緩存中讀取新值。

說了這些背景知識之後，再回到我們的 CAS 指令。

當兩個 core 同時執行針對同一位址的 CAS 指令時，其實他們是在試圖修改每個 core 自己持有的 cache line，假設兩個 core 都持有相同位址對應 cache line，且各自 cache line 狀态為 S，這時如果要想成功修改，就首先需要把 S 轉為 E 或者 M，則需要向其它 core invalidate 這個位址的 cache line，則兩個 core 都會向 ring bus 發出 invalidate 這個操作，那麼在 ring bus 上就會根據特定的設計協定仲裁是 core0，還是 core1 能赢得這個 invalidate，勝者完成操作，失敗者需要接受結果，invalidate 自己對應的 cache line，再讀取勝者修改後的值，回到起點。

到這裡，我們可以發現 MESIF 協定大大降低了讀操作的時延，沒有讓寫操作更慢，同時保持了一緻性！那麼對于我們的CAS操作來說，其實鎖并沒有消失，隻是轉嫁到了 ring bus 的總線仲裁協定中。而且大量的多核同時針對一個位址的 CAS 操作會引起反複的互相 invalidate 同一 cache line，造成 ping pong 效應，同樣會降低性能。 隻能說基于CAS的操作仍然是不能濫用，不到萬不得已不用，通常情況下還是使用資料位址範圍分離模式更好。

如果是這樣的話，按作者的想法，cmpxchg 直接就是原子的，不需要加 lock，現在假設要加鎖的記憶體同時被兩個核 cache 住。兩個核同時執行 cmpxchg 指令，都判斷成功，準備設定新值，其中一個成功，另一個失敗。失敗的那個，除了失效自己的 cache 外，還要去寫成功的那個核的 cache 中把新值讀回來，然後再放到 eax(rax) 寄存器中，因為 cmpxchg 的功能就是這樣，成功則設定新值，失敗則将記憶體的值 load 到 eax(rax) 寄存器中，而且成功或失敗 ZF 标志位值也不同。那麼，這樣一看，cmpxchg 指令的電路設計就有點複雜了，還跟 cache 的電路邏輯耦合了，而且，invalidate 失敗者還得去復原 cmpxchg 的結果，我懷疑設計人員不會這樣幹。而且那篇文章的評論中有人測試過不加 lock 會得到不正确的結果（我自己沒試），是以我傾向于認為作者說的不對。

再來說說我的猜想，我認為 cmpxchg 在 write-back 模式下，即使 cache 命中，也必須加 lock 才是原子的：

分情況讨論： 一、要加鎖的記憶體被一個核 cache 住 這種情況，cache line 的狀态為 Exclusive，表示暫時隻有我一個核 cache 了，那麼當該核（後面稱為核A）執行帶 lock 的 cmpxchg 時，會去鎖 cache，然後先執行一個讀，判斷相等，再準備寫 cache。若此時（寫 cache 之前）有另一個核（後面稱為核B）請求讀該記憶體，核A會 snoop 到這個請求，發出 HITM# 信号，表示這個記憶體現在在我的 cache 裡。核B收到 HITM# 信号，會發出 BOFF# 信号取消對記憶體的總線請求，并等待核A把資料發過來。由于核A現在對 cache 加了鎖，還在執行 cmpxchg，是以它會等指令執行完了之後再發資料。核A執行完 cmpxchg，取消對 cache 的鎖，然後将資料發往核B，核B的 BOFF# 信号取消。根據 Intel 文檔描述（卷3 11.2），此時，記憶體控制器也應該監聽到這個資料，然後由記憶體控制器自己更新記憶體，以保持記憶體與核A的 cache 一緻。

注意：以下猜測後來被證明是不對的，我又寫了一篇糾錯文 x86 cache locking 的猜想（續）

二、要加鎖的記憶體同時被兩個核 cache 住 這種情況，cache line 的狀态為 Shared，表示不止我一個核 cache 了。那麼這種情況對 cache 加鎖是沒用的，因為每個核通路自己核中生效的 cache 時，它是不會去跟外面的核互動的，要不然性能就太低了，而對 cache 加鎖也隻能對自己的 cache 加，然而别的核的 cache 中自己就有資料，根本不看你的 cache，那加了鎖又有什麼用呢。這時，兩個核 cmp 都會成功，然後準備執行 xchg，這下就又回到了那個知乎文章作者說的情況了。 是以，我猜，在 cache line 狀态為 Shared 時，lock 會将 cache 失效（自己的和别人的），然後将通路打到記憶體總線去，通過記憶體總線仲裁，兩個核隻有一個核能鎖住總線，鎖成功的那個執行讀-比較-寫，等鎖失敗的那個取得總線通路權後，讀-比較就失敗了，因為記憶體已經被寫了新值。對于帶 lock 的讀，即使是 write-back 模式，應該也是不會去填充 cache 的。（《Pentium Processor System Architecture》介紹以前 Pentium 處理器就是這麼幹的）

這也許就是 Intel 8.1.4 說 可能 的原因，在 Exclusive 狀态下直接做 cache locking，不會在記憶體總線上發 LOCK# 信号，在 Shared 狀态下會回退到 Pentium 處理器的政策。對比 Pentium 的總是往記憶體總線發 LOCK# 信号算是有優化吧。

參考

• https://yemablog.com/posts/cache-locking