Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題の解決方法)







# はじめに


Linux では DMA Bufferを mmap した時に、ある条件が揃うと CPU Cache が無効になり、パフォーマンスが極端に落ちる場合があります。そこで、何故そのようなことが起こるのか説明します。少し長くなるので、次のように記事を幾つかに分けて投稿します。



1. [はじめに]
2. Cache Coherence 問題   
2.1 [Cache Coherence 問題とは何か]   
2.2  __Cache Coherence 問題の解決方法(この記事)__  
3. [Cache Aliasing 問題]
4. [Linux Kernel の Cache 問題の扱い]
5. [Linux では Cache Coherence Hardware を持っていないとDMA Buffer をmmap する際に CPU Cache が無効になる]
6. [Raspberry Pi の例]
7. [RISC-V CPU の注意点]
8. [所感]



1〜3は、コンピューターアーキテクチャの基本的な事項を、簡単に説明したものです。すでにご存じの方は読み飛ばしてください。

4 はこれらの問題を Linux Kernel 内でどのように扱っているかを説明します。

5 がこれらの記事群の結論です。結論だけ知りたい方はここだけ読んでください。



前回の記事 [『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題とは何か)』] では、「Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある」原因の一つである Cache Coherence 問題について説明しました。この記事では、その Cache Coherence 問題の解決方法を説明します。すでにご存じの方は読み飛ばしてください。


# Cache Coherence 問題の解決方法


ここでは、Cache Coherence 問題を解決する方法として次の３つを説明します。

  * [キャッシュを使わない]
  * [ソフトウェアでなんとかする方法]
  * [ハードウェアでなんとかする方法]


## キャッシュを使わない


Cache Coherence 問題の解決方法が、いきなり「キャッシュを使わない」というのはどうかと思いますが、実はよく使われます。なぜなら、比較的簡単にできるからです。

Linux が動作するような CPU は、通常、仮想アドレスをサポートしています。そして仮想アドレスを物理アドレスに変換するための MMU(Memory Management Unit) を搭載しています。じつは MMU には仮想アドレスを物理アドレスに変換する際に、その仮想アドレスに対するアクセスの属性(実行可/不可、書き込み可/不可など) を指定することができます。その属性に キャッシュ可/不可もあります。したがって、ページ単位でキャッシュ可/不可を容易に変更することができるのです。

そのかわり、当然ですが、CPU からのアクセス速度はとてもとても遅くなります。


### 特徴


* ソフトウェアの実装負担：軽い
  * 実質 MMU の設定のみ
* ハードウェアの実装負担：軽い
  * MMU が必要だが、Linux が動作する CPU はすでに実装済み
* CPU からのアクセス：とても遅い


## ソフトウェアでなんとかする方法


前節では「キャッシュを使わない」方法を説明しましたが、せっかくキャッシュがあるんだから、もう少しなんとかならないのか、というわけでソフトウェアでキャッシュを制御する方法が考え出されました。この節ではその方法を説明します。




### CPU が DMA Buffer に書き込んで DEVICE が読む場合


まず、CPU が DMA Buffer にデータを書き込んで、DEVICE が DMA を使って DMA Buffer を読む場合を考えます。その場合は次の図のように処理が進みます。




![Fig.1 Software Solution to Cache Coherence Problem 1-1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F08f3bfb5-c8b5-f7ae-ffa8-74f2a3d0f260.jpeg "Fig.1 Software Solution to Cache Coherence Problem 1-1")

Fig.1 Software Solution to Cache Coherence Problem 1-1

<br />



1. CPU が MEMORY 上の DMA Buffer にデータの書き込みを要求します。   
図の例ではaddr=0x0080 に data=0xABED の書き込みを要求しています。 
2. CACHE が有効な場合は、MEMORY への書き込みは保留され、まずCACHE に書き込んだアドレスとデータが記憶されます。   
図の例では D-Cache に addr=0x0080 と data=0xABED が記憶されます。    
この状態では、まだ MEMORY 上にはデータが書き込まれていません。




![Fig.2 Software Solution to Cache Coherence Problem 1-2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F99a2e692-b165-5a5c-9d53-73ea0e5dd41c.jpeg "Fig.2 Software Solution to Cache Coherence Problem 1-2")

Fig.2 Software Solution to Cache Coherence Problem 1-2

<br />



3. ここで CPU が CACHE に対して該当するアドレスの内容を強制的に MEMORY に吐き出させます(Flush します)。




![Fig.3 Software Solution to Cache Coherence Problem 1-3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F51db08f9-959a-ff23-1344-acceafa4e78c.jpeg "Fig.3 Software Solution to Cache Coherence Problem 1-3")

Fig.3 Software Solution to Cache Coherence Problem 1-3

<br />



4. 次に DEVICE が DMA を使って DMA Buffer を読みに行きます。
5. MEMORY にはすでに CPU が書き込みを要求した値が反映されているので、 DEVICE は CPU が書き込んだ値を得ることができます。



これが、CPUが DMA Buffer に書き込んで DEVICE が読む場合の Cache Coherence 問題をソフトウェアで解決する方法です。


### DEVICE が DMA Buffer に書き込んで CPU が読む場合


次に、DEVICE が DMA Buffer にデータを書き込んで CPU が読む場合を考えます。その際、次の図のように CPU の Cache になんらかのデータがすでにキャッシュされているとします。


![Fig.4 Software Solution to Cache Coherence Problem 2-1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fc0ba96c1-6ff0-2fc5-94b8-e563a53e6c49.jpeg "Fig.4 Software Solution to Cache Coherence Problem 2-1")

Fig.4 Software Solution to Cache Coherence Problem 2-1

<br />



1. CPU が DMA Buffer からのデータを読み込んでその内容が CACHE に記録されている、あるいは CPU が DMA Buffer を初期化してその内容がすでに MEMORY に反映されているとします。この図の例では addr=0x0080 の data=0x0000 が D-Cache 上にすでに記録されています。


![Fig.5 Software Solution to Cache Coherence Problem 2-2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fc59acaea-e47f-302f-bd96-5fdbbef24df4.jpeg "Fig.5 Software Solution to Cache Coherence Problem 2-2")

Fig.5 Software Solution to Cache Coherence Problem 2-2

<br />



2. DEVICE が DMA Buffer にデータを書き込みます。   
この図の例では addr=0x0080 に data=0xDEAD を書き込んでいます。




![Fig.6 Software Solution to Cache Coherence Problem 2-3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F6ceb4919-9aac-7cc1-8ce9-c01dd0629934.jpeg "Fig.6 Software Solution to Cache Coherence Problem 2-3")

Fig.6 Software Solution to Cache Coherence Problem 2-3

<br />



3. ここで CPU が CACHE に対して該当するアドレスの内容を破棄(Invalidate)するように命じます。




![Fig.7 Software Solution to Cache Coherence Problem 2-4](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fd6fc9c53-f0d5-b82d-94db-1ae256e6ee9d.jpeg "Fig.7 Software Solution to Cache Coherence Problem 2-4")

Fig.7 Software Solution to Cache Coherence Problem 2-4

<br />



4. CPU が DMA Buffer のデータを読みます。
5. CACHE には DMA Buffer に該当するアドレスの内容が破棄されているため、あらためて MEMORY から読まれます。そのため、DEVICE が書き込んだ値を CPU が得ることが出来ます。



これが DEVICE が DMA Buffer に書き込んで CPU が読む場合の Cache Coherence 問題をソフトウェアで解決する方法です。




### 特徴


* ソフトウェアの実装負担：とても重い
  * CPU からのアクセスと DEVICE からのアクセスが排他的であるため、制御が必要
  * DEVICE が DMAするタイミングをソフトウェアが管理できないといけない
* ハードウェアの実装負担：軽い
  * キャッシュの Flush/Invalidate 機構が必要だが、たいていの CPU はすでに実装済み
* CPU からのアクセス：まあまあ速い
  * CPU からのアクセスだけなら速いが、 キャッシュの Flush/Invalidate に意外と時間がかかることに注意が必要。


## ハードウェアでなんとかする方法


前節ではソフトウェアでなんとかする方法を説明しましたが、特徴でも説明した通り、ソフトウェアの実装負担が重くとてもとても面倒です。

さすがに面倒臭くなったのか、最近はハードウェアでなんとかしてしまう方法が一般的です。そこで、この節では Cache Coherence 問題をハードウェアで解決する方法を説明します。




### CPU が DMA Buffer に書き込んで DEVICE が読む場合


まず、CPU が DMA Buffer にデータを書き込んで、DEVICE が DMA を使って DMA Buffer を読む場合を考えます。その場合は次の図のように処理が進みます。




![Fig.8 Hardware Solution to Cache Coherence Problem 1-1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F89b09614-edbb-9062-a542-12621e555eb6.jpeg "Fig.8 Hardware Solution to Cache Coherence Problem 1-1")

Fig.8 Hardware Solution to Cache Coherence Problem 1-1

<br />



1. CPU が MEMORY 上の DMA Buffer にデータの書き込みを要求します。   
図の例ではaddr=0x0080 に data=0xABED の書き込みを要求しています。 
2. CACHE が有効な場合は、MEMORY への書き込みは保留され、まずCACHE に書き込んだアドレスとデータが記憶されます。   
図の例では D-Cache に addr=0x0080 と data=0xABED が記憶されます。    
この状態では、まだ MEMORY 上にはデータが書き込まれていません。




![Fig.9 Hardware Solution to Cache Coherence Problem 1-2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fb46d3ee5-41d7-d334-64c9-b0b474e2235e.jpeg "Fig.9 Hardware Solution to Cache Coherence Problem 1-2")

Fig.9 Hardware Solution to Cache Coherence Problem 1-2

<br />

3. DEVICE はMEMORY に対して DMA Buffer からの読み出し要求を行います。   
この時、Cache Coherence 問題をハードウェアでなんとかする場合、まず InterConnect が DEVICE からの要求を一旦受け付けます。
4. InterConnect は DEVICE からの読み出し要求で指定されたアドレスを、キャッシュをもっている CPU に対して通知します。これをスヌープと言います。


![Fig.10 Hardware Solution to Cache Coherence Problem 1-3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fd6d47537-b95e-837a-cb6c-2c121484202d.jpeg "Fig.10 Hardware Solution to Cache Coherence Problem 1-3")

Fig.10 Hardware Solution to Cache Coherence Problem 1-3

<br />


![Fig.11 Hardware Solution to Cache Coherence Problem 1-4](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F477c2cc3-9f25-e58a-c672-cc0fadb3bb63.jpeg "Fig.11 Hardware Solution to Cache Coherence Problem 1-4")

Fig.11 Hardware Solution to Cache Coherence Problem 1-4

<br />



5. 該当するアドレスの内容を保持している CACHE をもつ CPU が存在する場合は、そのCPUからデータをもらいます。   
また、該当するアドレスの内容を保持している CACHE をもつ CPU が一つも存在しない場合は、MEMORY からデータを読み取ります。



これが、CPUが DMA Buffer に書き込んで DEVICE が読む場合の Cache Coherence 問題をハードウェアで解決する方法です。




### DEVICE が DMA Buffer に書き込んで CPU が読む場合


次に、DEVICE が DMA Buffer にデータを書き込んで CPU が読む場合を考えます。その際、次の図のように CPU の CACHE になんらかのデータがすでにキャッシュされているとします。




![Fig.12 Hardware Solution to Cache Coherence Problem 2-1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F1bb7e9df-7a0d-c689-62dd-6fc7e8e74261.jpeg "Fig.12 Hardware Solution to Cache Coherence Problem 2-1")

Fig.12 Hardware Solution to Cache Coherence Problem 2-1

<br />



1. CPU が DMA Buffer からのデータを読み込んでその内容が CACHE に記録されている、あるいは CPU が DMA Buffer を初期化してその内容がすでに MEMORY に反映されているとします。この図の例では addr=0x0080 の data=0x0000 が D-Cache 上にすでに記録されています。
2. DEVICE はMEMORY に対して DMA Buffer への書き込み要求を行います。   
この時、Cache Coherence 問題をハードウェアでなんとかする場合、まず InterConnect が DEVICE からの要求を一旦受け付けます。   
この図の例では  MEMORY 上のaddr=0x0080 に data=0xDEAD を書き込むことを InterConnect に要求しています。
3. InterConnect は DEVICE からの書き込み要求で指定されたアドレスを、キャッシュをもっている CPU に対して通知します。これをスヌープと言います。




![Fig.13 Hardware Solution to Cache Coherence Problem 2-2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F33251885-71fa-11f4-a967-1eb338b22473.jpeg "Fig.13 Hardware Solution to Cache Coherence Problem 2-2")

Fig.13 Hardware Solution to Cache Coherence Problem 2-2

<br />



4. CPU は InterConnect からの書き込みアドレスを受け取り、CACHE 内に該当する内容が存在するか調べます。もし存在しているならば、その内容を破棄(Invalidate)します。
5. CACHE 内のデータが汚れている状態(CPU がMEMORY に対して書き込み要求を行い、まだMEMORY に反映されていない状態)の場合は、単純にその内容を破棄(Invalidate)出来ません。何故なら、CPU が要求した MEMORY への書き込みが消えてしまい、MEMORY との一貫性が失われるからです。   
したがって、CACHE 内のデータが汚れている状態の場合は、InterConnect は CACHE に残っているデータと DEVICE からの書き込みデータをマージして MEMORY に書き込みます。






![Fig.14 Hardware Solution to Cache Coherence Problem 2-3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fabcbf4d4-b531-8fee-774d-c42be7b72572.jpeg "Fig.14 Hardware Solution to Cache Coherence Problem 2-3")

Fig.14 Hardware Solution to Cache Coherence Problem 2-3

<br />



5. CACHE 内のデータが汚れていない状態(CPU がMEMORY に対して書き込み要求を行っていない状態)の場合は、単純にその内容を破棄(Invalidate)します。   
その上で、InterConnect は DEVICE からの書き込みデータを MEMORY に書き込みます。




### 特徴


* ソフトウェアの実装負担：無し
* ハードウェアの実装負担：とても重い
  * CACHE は CPU からだけでなく外部からのスヌープにも対応必須
  * InterConnect はスヌープに対応、   
かつ、 CACHE からのデータのマージ書き込みに対応必須
  * 上記の機能をサポートした Inter Connect Protocol が必要
* CPU からのアクセス：速い


# まとめ


この記事では、「Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある」のを説明する際に、知っておいてほしい Cache Cohernce 問題について、どのような解決方法があるのかを説明しました。これら解決方法の比較を簡単に表にまとめると次のようになります。

Table.1 Cache Coherence 問題の解決方法比較

<table border="2">
  <tr>
    <td align="center"></td>
    <td align="center">ソフトウェアの実装負担</td>
    <td align="center">ハードウェアの実装負担</td>
    <td align="center">CPUからの<br />アクセス速度</td>
  </tr>
  <tr>
    <td>キャッシュを使わない方法</td>
    <td align="center">軽い</td>
    <td align="center">軽い</td>
    <td align="center">とても遅い</td>
  </tr>
  <tr>
    <td>ソフトウェアによる解決方法</td>
    <td align="center">とても重い</td>
    <td align="center">軽い</td>
    <td align="center">まあまあ速い</td>
  </tr>
  <tr>
    <td>ハードウェアによる解決方法</td>
    <td align="center">無し</td>
    <td align="center">とても重い</td>
    <td align="center">速い</td>
  </tr>
</table>



次の記事 [『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題とは何か)』] では、「Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある」もう一つの原因である Cache Aliasing 問題について説明します。



[キャッシュを使わない]: #キャッシュを使わない
[ソフトウェアでなんとかする方法]: #ソフトウェアでなんとかする方法
[ハードウェアでなんとかする方法]: #ハードウェアでなんとかする方法
[はじめに]: https://qiita.com/ikwzm/items/aa7e2373705872ccf764 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (はじめに)』@Qiita"
[『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (はじめに)』]: https://qiita.com/ikwzm/items/aa7e2373705872ccf764 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (はじめに)』@Qiita"
[Cache Coherence 問題]: https://qiita.com/ikwzm/items/f60281491cc83f29c019 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題とは何か)』@Qiita"
[Cache Coherence 問題とは何か]: https://qiita.com/ikwzm/items/f60281491cc83f29c019 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題とは何か)』@Qiita"
[『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題とは何か)』]: https://qiita.com/ikwzm/items/f60281491cc83f29c019 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題とは何か)』@Qiita"
[Cache Coherence 問題の解決方法]: https://qiita.com/ikwzm/items/6d3225e4cbdbbabcabd5 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題の解決方法)』@Qiita"
[『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題の解決方法)』]: https://qiita.com/ikwzm/items/6d3225e4cbdbbabcabd5 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Coherence 問題の解決方法)』@Qiita"
[Cache Aliasing 問題]: https://qiita.com/ikwzm/items/1b8dc72e04d0fa031a0f "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題とは何か)』@Qiita"
[Cache Aliasing 問題とは何か]: https://qiita.com/ikwzm/items/1b8dc72e04d0fa031a0f "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題とは何か)』@Qiita"
[『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題とは何か)』]: https://qiita.com/ikwzm/items/1b8dc72e04d0fa031a0f "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題とは何か)』@Qiita"
[Cache Aliasing 問題の解決方法]: https://qiita.com/ikwzm/items/b3c24f04121a0d2deefd "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題の解決方法)』@Qiita"
[『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題の解決方法)』]: https://qiita.com/ikwzm/items/b3c24f04121a0d2deefd "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題の解決方法)』@Qiita"
[Linux Kernel の Cache 問題の扱い]: https://qiita.com/ikwzm/items/f32985890b2013ef5528 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Linux Kernel の Cache 問題の扱い)』@Qiita"
[『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Linux Kernel の Cache 問題の扱い)』]: https://qiita.com/ikwzm/items/f32985890b2013ef5528 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Linux Kernel の Cache 問題の扱い)』@Qiita"
[Linux では Cache Coherence Hardware を持っていないとDMA Buffer をmmap する際に CPU Cache が無効になる]: https://qiita.com/ikwzm/items/0f77072158ce842018fc "『Linux では Cache Coherence Hardware を持っていないとDMA Buffer をmmap する際に CPU Cache が無効になる』@Qiita"
[『Linux では Cache Coherence Hardware を持っていないとDMA Buffer をmmap する際に CPU Cache が無効になる』]: https://qiita.com/ikwzm/items/0f77072158ce842018fc "『Linux では Cache Coherence Hardware を持っていないとDMA Buffer をmmap する際に CPU Cache が無効になる』@Qiita"
[Raspberry Pi の例]: https://qiita.com/ikwzm/items/f8bcb82cfdb818bdb07d "『Raspberry Pi では DMA Buffer をmmap する際に CPU Cache が無効になる』@Qiita"
[『Raspberry Pi では DMA Buffer をmmap する際に CPU Cache が無効になる』]: https://qiita.com/ikwzm/items/f8bcb82cfdb818bdb07d "『Raspberry Pi では DMA Buffer をmmap する際に CPU Cache が無効になる』@Qiita"
[RISC-V CPU の注意点]: https://qiita.com/ikwzm/items/3c6b15029780be57f3a9 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (RISC-V CPU の注意点)』@Qiita"
[『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (RISC-V CPU の注意点)』]: https://qiita.com/ikwzm/items/3c6b15029780be57f3a9 "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (RISC-V CPU の注意点)』@Qiita"
[所感]: https://qiita.com/ikwzm/items/46f00c39b7d92c06654e "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (所感)』@Qiita"
[『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (所感)』]: https://qiita.com/ikwzm/items/46f00c39b7d92c06654e "『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (所感)』@Qiita"
[『Kernel/VM探検隊@北陸 Part 6』]: https://kernelvm.connpass.com/event/297033/ "『Kernel/VM探検隊@北陸 Part 6』"