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 問題とは何かを説明します。すでにご存じの方は読み飛ばしてください。


# Cache Aliasing 問題とは何か


Cache Aliasing 問題とは、仮想記憶をサポートしたコンピューターシステムにおいて、同じ物理アドレスに複数の異なる仮想アドレスを割り当てた際に発生するキャッシュの問題のことです。この Cache Aliasing 問題には、キャッシュの一貫性の問題とキャッシュ効率の問題の二つがありますが、ここではキャッシュの一貫性の問題を説明します。


## キャッシュの実装例


ここではまず、Cache Aliasing 問題を説明するために、キャッシュの実装例を示します。


### キャッシュの基本構成


一般的に CPU の CACHE は 下図のように、複数のキャッシュラインを保持する RAM で構成されています。ここでのキャッシュラインとは、キャッシュの状態を保持しておくフラグ部、アドレスの上位部分を保持しておくタグ部、MEMORY 上のデータを保持しておくデータ部を一組にしたものです。


![Fig.1 Example of CACHE structure](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F53286c1f-2666-c9e4-9008-e322533ec102.jpeg "Fig.1 Example of CACHE structure")

Fig.1 Example of CACHE structure

<br />



指定されたアドレスが CACHE にあるかどうかを判定する時は、下図のように行います。まず、アドレスを３部分に分割します。


![Fig.2 Example of Address structure](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F7a13c8be-362b-daa1-39c5-9a5616ffd309.jpeg "Fig.2 Example of Address structure")

Fig.2 Example of Address structure

<br />



最下位の Pos 部は、CACHE LINE のデータ部の位置を示します。通常 、一つのCACHE LINE のデータ部は MEMORY 上の数バイト分を保持します。ちなみにこの容量のことを CACHE LINE SIZE と呼びます。この容量は CPU によって異なり、例えば Cortex-A53 の L1-Cache のCACHE LINE SIZE は64バイトです。この場合、Pos 部は6ビットあります。 

2番目の Index 部は、RAM に格納されているCACHE LINE のうちの、どの CACHE LINE かを示します。この Index 部で示す内容を RAM から読み出します。

３番目の Tag 部は、Index 部によって RAM から読み出された CACHE LINE が、指定されたアドレスのものかを判定する際に使用されます。指定されたアドレスの Tag 部と、RAMから読み出された CACHE LINE の TAG 部と比較して、一致すれば、RAM から読み出された CACHE LINE は指定されたアドレスのものと判定されます。


### キャッシュの実装例(PIPT方式)


ここではまず、CACHE の実装例の一つとして PIPT(Physically Indexed  P hysically  T agged) 方式を説明します。PIPT 方式とはその名前の通り、下の図のように、仮想アドレスを物理アドレスに変換してから CACHE LINE を読む方式のことです。


![Fig.3 PIPT(Physically Indexed Physically Tagged)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F654ed3cd-82e9-a7d0-0771-cd65c5ffbe1e.jpeg "Fig.3 PIPT(Physically Indexed Physically Tagged)")

Fig.3 PIPT(Physically Indexed Physically Tagged)

<br />



PIPT方式の特徴は、まず仮想アドレスを物理アドレスに変換してから RAMをアクセスすることです。そのため、指定されたアドレスが CACHE にあるかどうかを判定するのに、３ステップ必要になります。




### キャッシュの実装例(VIPT方式)


もう一つ、CACHE の実装例の一つとして  VIPT(Virtually Indexed Physically Tagged)方式を説明します。VIPT 方式では、下の図のように、 CACHE LINE を読む際は、仮想アドレスの Index をそのまま使います。そして CACHE LINE を読むのと同時並行で仮想アドレスを物理アドレスに変換します。


![Fig.4 VIPT(Virtually Indexed Physically Tagged)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2Fcaf245d2-1df3-66d6-b393-6551721dea46.jpeg "Fig.4 VIPT(Virtually Indexed Physically Tagged)")

Fig.4 VIPT(Virtually Indexed Physically Tagged)

<br />



VIPT 方式の特徴は、指定されたアドレスが CACHE にあるかどうかを判定するのに、PIPT 方式より１ステップ速い２ステップで済むことです。



このように、一見良さげな VIPT 方式ですが、現在のモダンな CPU ではほとんど採用されていません。何故ならば、問題点がいくつかあるからです。そのうちの一つが次節で説明する Cache Aliasing 問題です。




## Cache Aliasing とは


まず、次の図のように、同じ物理アドレスに複数の異なる仮想アドレスを割り当てることを考えます。


![Fig.5 Assign multiple Virtual Address Areas to a single Physical Area](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F2abc080d-c020-84ff-1de3-0b84f294d5fd.jpeg "Fig.5 Assign multiple Virtual Address Areas to a single Physical Area")

Fig.5 Assign multiple Virtual Address Areas to a single Physical Area

<br />



キャッシュが PIPT(Physically Indexed Physically Tagged)方式の場合は、次の図のように、仮想アドレスをまず物理アドレスに変換してから  RAM から CACHE LINE を読み出すため、どちらの仮想アドレスの場合も必ず同じ CACHE LINE を指します。


![Fig.6 In the case of PIPT](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F60d4e929-03c2-8deb-76c5-f21cce1d1c0c.jpeg "Fig.6 In the case of PIPT")

Fig.6 In the case of PIPT

<br />



ところがキャッシュが VIPT(Virtually Indexed Physically Tagged) 方式の場合は、CACHE LINE を読み出すために仮想アドレスの Index をそのまま使います。そのため、次の図のように、異なる仮想アドレスからのアクセスの場合、それぞれが異なる CACHE LINE を指すことがあります。


![Fig.7 In the case of VIPT](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0%2F24981%2F8a979fef-ef10-96e0-2e60-dfcb850720a4.jpeg "Fig.7 In the case of VIPT")

Fig.7 In the case of VIPT

<br />



このように、同じ物理アドレスに複数の異なる仮想アドレスを割り当てた際に異なる CACHE LINE が割り当てられた状態を Cache Aliasing と言います。



この Cache Aliasing が引き起こす問題のことを Cache Aliasing 問題と言います。Cache Aliasing 問題のもっともやっかいなものが、CACHE LINE 間の一貫性(Coherency) 問題です。判りやすい例を挙げると、ある仮想アドレスを使って書き込んだ内容が、別の仮想アドレスを使って読んだときに、ちゃんと書き込んだデータが読めるかということです。


# まとめ


この記事では、「Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある」のを説明する際に、知っておいてほしい Cache Aliasing 問題とは何かについて説明しました。

Cache Aliasing 問題とは、仮想記憶をサポートしたコンピューターシステムにおいて、同じ物理アドレスに複数の異なる仮想アドレスを割り当てた際に、キャッシュが VIPT 方式で実装されている場合は、キャッシュの一貫性に問題が発生することです。

次の記事 [『Linux で DMA Bufferを mmap した時に CPU Cacheが無効になる場合がある (Cache Aliasing 問題の解決方法)』] では、この 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』"