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







# はじめに


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



1. [はじめに] 
2. [Cache Coherence 問題]
3. Cache Aliasing 問題   
3.1 [Cache Aliasing 問題とは何か]   
3.2  __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 Aliasing 問題とは何か)』] では、「Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある」原因の一つである Cache Aliasing 問題について説明しました。この記事では、その Cache Aliasing 問題の解決方法を説明します。すでにご存じの方は読み飛ばしてください。


# Cache Aliasing 問題の解決方法


ここでは、Cache Aliasing問題(正確には Cache Aliasing 時の Cache Line の一貫性の問題)を解決する方法として次の３つを説明します。

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




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


Cache Aliasing 問題をハードウェアで解決する方法は、次のものがあります。

* 回路を付加する
* VIPT をあきらめる
* キャッシュサイズを小さくする




### 回路を付加する


Cache Aliasing 問題を解決するために、Aliasing 検知回路や キャッシュライン間でデータを転送する回路を付加するなどの方法が考えられます。しかし筆者は、あまり詳しくないので説明は省略します。




### VIPT をあきらめる


前項で紹介した「回路を付加する」方法はかなり難しいと思います。     

というのも、前章の『[Cache Aliasing 問題とは何か]』で説明しましたが、Cache Aliasing 問題が発生するのは CACHE の構成が VIPT 方式の場合です。何故 VIPT 方式が採用されたかというと、それは PIPT 方式よりも速くキャッシュのHit/Miss 判定を行えるからです。しかし、Cache Aliasing 問題を解決するために、Aliasing 検知回路などをゴテゴテとつけて PIPT 方式よりも遅くなっては意味がありません。それならば PIPT 方式でいいんじゃね？となります。      

結果的にCache Aliasing 問題をハードウェアで解決しようと思えば、そもそも VIPT 方式ではなく PIPT 方式を採用して Cache Aliasing 問題そのものを起こらないようにするほうが簡単です。




### キャッシュサイズを小さくする


Cache Aliasing が起こるのは、同じ物理アドレスに対して複数の仮想アドレスを割り当てたときに、VIPT 方式で Cache Line の位置を示す VI(Virtually Index) 部に異なる値が割り当てられる場合です。

そこで、物理ページを複数の仮想アドレスに割り当てた場合でも、仮想アドレスの VI 部 が同じになるように、キャッシュサイズを小さくします。例えば、物理ページが 4KB だとすれば、キャッシュサイズを 4KB 以下にしてしまえば、物理ページを複数の仮想アドレスに割り当ててもページのオフセット値は同じになるので、どちらの仮想アドレスからアクセスしても VI は同じになります。

キャッシュサイズをページサイズよりも大きくしたい場合は、ページサイズ以下のキャッシュを複数ならべます。キャッシュを複数ならべる方式を Set-Associative Cache と言います。例えば8 個並列にならべる場合は 8 Way Set-Associative と言います。例えばキャッシュの表記が32KB (8 Way Set-Associative) だった場合、サイズが4KB のキャッシュが８セットあってキャッシュサイズの総容量は 32KB ということです。ただしキャッシュを複数ならべる場合、ならべる数にはハードウェア的な限界があります。




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


Cache Aliasing 問題をソフトウェアで解決する方法は、次のものがあります。

* 仮想アドレスの割り当てを工夫する
  * ページサイズを大きくする
  * ページカラーリング
* データの配置やアクセスパターンを工夫する




### 仮想アドレスの割り当てを工夫する


Cache Aliasing が起こるのは、同じ物理アドレスに対して複数の仮想アドレスを割り当てたときに、VIPT 方式で Cache Line の位置を示す VI(Virtually Index) 部に異なる値が割り当てられる場合です。つまり何らかの方法で同じ物理アドレスの場合は仮想アドレスの VI部に同じ値が割り当てられるようします。

ただし、仮想アドレスの割り当てを工夫するする方法は、仮想記憶を管理している MMU の設定が必要なため、Linux  のようなOSを場合は Kernel の助けが必要になります。




#### ページサイズを大きくする


単純にページサイズ(ページの割り当時の単位)を VI(Virtually Index) の最上位位置よりも大きくします。こうすれば、物理ページを複数の仮想アドレスに割り当ててもページのオフセット値は同じになるので、どちらの仮想アドレスからアクセスしても VI は同じになります。




#### ページカラーリング


ページカラーリングはキャッシュカラーリングとも呼ばれる手法で、物理アドレスに仮想アドレスを割り当てる際に、仮想アドレスの値を工夫する方法です。

ページカラーリングは、もともと Cache Thrassing への対策として考えられました。Cache Thrashing とは、メモリのアクセスパターンによっては、ある CACHE LINE にアクセスが集中してしまい、頻繁に CACHE LINE のデータの置き換えが起きて却って性能が落ちる現象を指します。

ページに仮想アドレスを割り当てる際に、割り当てる仮想アドレスの値を工夫することで、Cache Thrassing や Cache Aliasing を防ぎます。

しかし、このページカラーリングは、ページの割り当て時のソフトウェア的な負荷が大きく、実装がかなり困難です。




### データの配置やアクセスパターンを工夫する


前節の仮想アドレスの割り当てを工夫する方法は、仮想記憶を管理している MMU の設定が必要なため、Linux  のようなOSを場合は Kernel の助けが必要になります。そこで、Kernel の助けを借りずに Cache Aliasing 問題を解決するために、アプリケーションのレベルでデータの配置やアクセスパターンを工夫して Cache Aliasing が起きないようにする方法が考えられます。しかし、この方法はソフトウェアのプログラミングがかなり面倒臭いことになります。




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


VIPT 方式を採用していて Cache Aliasing 問題が起こりうるシステムで、ソフトウェアで解決するのも難しいとなれば、最終手段としてキャッシュを使わないという手法があります。

一言でキャッシュを使わないといっても、すべての仮想領域からのアクセスでキャッシュ無効にする方法もあれば、次の図のように、一つだけ指定された仮想領域からのみキャッシュを有効にして、それ以外の仮想領域からのアクセスに対してはキャッシュを無効にする方法があります。

ただし、この場合でも『[Cache Coherence 問題とは何か]』で説明した、MEMORY と CPUの CACHE との間の Coherence問題は残っていることに注意してください。


![Fig.1 Disable Cache from the second and higher Virtual Areas](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fa9ecb8d6-073c-f22c-e4c1-a1d0573509dd.jpeg "Fig.1 Disable Cache from the second and higher Virtual Areas")

Fig.1 Disable Cache from the second and higher Virtual Areas

<br />




# まとめ


この記事では、「Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある」のを説明する際に、知っておいてほしい Cache Aliasing 問題について、次のような解決方法を紹介しました。



  * 回路を付加する
  * VIPT をあきらめる
  * キャッシュサイズを小さくする
  * ページサイズを大きくする
  * ページカラーリング
  * データの配置やアクセスパターンを工夫する
  * キャッシュを使わない



次の記事 [『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Linux Kernel の Cache 問題の扱い)』]では、Linux  Kernel が Cache Coherence 問題と Cache Aliasing 問題をどのように扱っているかについて説明します。




# 蛇足



## CACHE に VIPT 方式が使われないもう一つの理由


最近の CPU では VIPT 方式の CACHE はあまり使われていません。その理由の一つは、この記事の「[ハードウェアでなんとかする方法]」で述べた通り、Cache Aliasing 問題をハードウェアで解決するには そもそも CACHE を VIPT 方式でなく PIPT 方式にするほうが簡単だからです。

しかし、もうひとつ VIPT 方式には問題があります。それはマルチプロセッサに向いていないというものです。

『[Cache Coherence 問題の解決方法]』のハードウェアでなんとかする方法では、スヌープが行われることを説明しました。スヌープでは、 DEVICE や他の CPU からのアクセス要求アドレスを CACHE に通知して各々の CACHE は通知されたアドレスの内容がキャッシュされているかどうかを調べる必要があります。


![Fig.2 Hardware Solution to Cache Coherence Problem 1-2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fc8c4795f-b23e-e02b-704c-27f5aa13f6a5.jpeg "Fig.2 Hardware Solution to Cache Coherence Problem 1-2")

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

<br />



このスヌープアドレスが物理アドレスの場合、VIPT 方式だと 物理アドレスを仮想アドレスに変換してから CACHE を調べる必要があります。物理アドレスと仮想アドレスが1対１ならばテーブルだけで済むかもしれませんが、一つの物理アドレスに複数の仮想アドレスを割り当てた場合を想定すると実装の難易度が爆上がりします。

このスヌープアドレスを仮想アドレスにするという選択肢もありますが、それだと Cache Aliasing 問題は未解決のままだし、MMU をどこに配置するかとか、その管理をどうするのかという問題があります。

というわけで、昨今のマルチプロセッサ全盛の時代では、Cache Coherence 問題はハードウェアでなんとかする方法が主流になっており、その場合は VIPT 方式は適していないのです。



[キャッシュを使わない]: #キャッシュを使わない
[ソフトウェアでなんとかする方法]: #ソフトウェアでなんとかする方法
[ハードウェアでなんとかする方法]: #ハードウェアでなんとかする方法
[はじめに]: 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』"