# Memory Barriers: a Hardware View for Software Hackers
###### tags: `cache coherence` `IBM Linux Technology Center`
###### Papers: [link](http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf)
###### Authors: [Paul E.McKenny](https://scholar.google.com/citations?user=k8F7-kUAAAAJ&hl=en)
## 0. Preface
* reordering memory 可以讓系統效能更好，但若要維持 order 的正確性，則需要 memory barriers 等 synchronization primitives 來維持
* 而要更加了解這個議題需要對 CPU cache 有深入的了解，因此這篇文章會介紹以下段落：
1. cache 的 structure
2. 介紹 cache coherency protocols
3. store buffers 跟 invalidate queue 如何幫助 cache and cache coherency protocols 來達到高效能
## 1. Cache Structure
* 現今 CPU 執行的速度遠比從 main memory 提取 data 上來的速度快了好幾百倍以上，因此需要只需幾個 cycle 就能 access data 的 cache 的出現。
* CPUs' caches 跟 memory 中的 data flow 可以化為固定長度的 block，稱為 "cache line"，其長度為 16 to 256 bytes 不整。
* 當指定的 data 第一次被 CPU access 的時候會發生 "startup" or "warmup" cache miss，CPU 要多等幾百個 cycles，來把 data 從 memory 中提取上來
* 當 CPU's cache 滿了後，就需要把舊資料踢出去才能有空間讓新資料進來，這稱為 "capacity miss"，不過目前 cache 的設計會讓 cache 還沒滿就需要踢資料，因為使用 hash table 方式
* 此 cache 有 16 個 "set" 以及 2 個 "way"，總共有 32 個 "line"，每個 entry 包含一個 256 byte 的 "cache line"
* 如同一個 set 因為擠滿了而被趕出去，下一次 CPU 又 aceess 到該資料，這就發生了 "associativity miss"
* 若 CPU 要 "write"，那 CPU 要先把所有擁有該 data 的 cache 都先 remove or invalidated 該部分，如果該 data 被 mark 為 "read-only"，則發生 "write miss"。一旦完成 "invalidated" 的動作，CPU 就會開始寫入，而後若是別的 CPU 要 access 該資料，就會發生 cache miss，這種稱為 "communication miss"
## 2. Cache-Coherence Protocols
### 2.1 MESI States
* MESI 代表："Modified" , "Exclusive" , "Shared" , "Invalid"
* Modified (M): 只有該 cache line 裡有最新資料，比 main memory 裡的資料還新
* Exclusive (E): 只有該 cache line 裡有最新資料，不過和 main memory 一致
* Shared (S): 有兩個以上的 cache lines 有最新資料，和 main memory 一致
* Invalid (I): cache line 內的資料已過時，不可使用
### 2.2 MESI Protocol Messages
* Read: 包含要 read 的 cache line 的 physical address
* Read Response: 回覆之前的 Read message，並包含所要求的 data
* Invalidate: 包含要 invalidate 的 cache line 的 physical address，所有 CPU 都要將該 data 移出他們的 cache
* Invalidate Acknowledge: 收到 Invalidate 的 CPU 要在移出 data 後回覆
* Read Invalidate: 包括 "Read" 跟 "Invalidate"，會包含要讀取的 cache line 中的 physical address，同時要求其他 cache 要移出該 data，需要獲得 "Read Responce" 跟 "Invalidate Acknowledge"
* Writeback: 包含要寫回的 data 跟該 data 的 address，此 message 允許 cache 將 "Modified States" 的 message 移出 cache
## 3. Store Result in Unnecessary Stalls
## 4. Store Sequences Result in Unnecessary Stalls
## 5. Read and Write Memory Barriers
## 6. Example - Memory-Barrier Sequence
## 7. Memory-Barrier Instructions For Specific CPU
## 8. Are Memory Barriers Forever?
## 9. Advice to Hardware Designers