MIPSのアドレス変換周り(TLB)の処理をまとめてみた

1年ほど前にTLB(Translation Look-aside Buffer)を使ったアドレス変換処理を実装したのだけど、もう一回実装しようと思ったらあまり覚えてなかったのでまとめておくことにしました。
See MIPS Runを参考にしました。間違っているところがあればご連絡ください。

アドレス変換とは

通常プログラムで扱うアドレスは仮想アドレス(Virtual Address)と呼ばれ、(32bitマシンでは)32bitのアドレスを自由に使えます。しかし、実際のデータは物理メモリ上のどこかに格納されています。物理メモリ上の位置を示すものが物理アドレス(Phisical Address)と呼ばれます。
データにアクセスするためには仮想アドレスから物理アドレスに変換する必要があり、この処理をアドレス変換と呼びます。

単純な実装では、仮想アドレス = 物理アドレスとすることも可能です。しかし、物理メモリサイズ以上のプログラムを動かすことができなくなります。アドレス変換があることにより、少ない物理メモリ上で大量のメモリを使用するプログラムを実行することが可能になります。

基本的な仕組み

アドレス変換の基本的な仕組みは、仮想アドレスと物理アドレスの対応表を持っておき、それを利用するというものです。1アドレス毎に対応を持つと表の量が莫大になってしまうので、どれくらいの粒度で対応表を持つかというのが、ページサイズになります。32bit環境では通常、ページサイズは4KBなことが多いです。ページ毎の対応表のことをページテーブルと呼びます。

ページテーブルは基本的にはメモリ上に保持しておき、変換が必要なときに参照するということになります。しかし、プログラムを実行するときには必ずアドレス変換が必要なため、1サイクル毎にメモリにアクセスすることは非常に大きなボトルネックとなります。

毎回ページテーブルを参照するのが嫌なら対応を覚えておけば良いよねということで、ページテーブルのキャッシュのことをTLB(Translation Look-aside Buffer)と呼びます。CPUはまずTLBに欲しい情報があるかを探し、あればメモリアクセスすること無くアドレス変換が可能になります。

現在のプロセッサではどのような形であれTLBを持っているため、
アドレス変換がうまくできるようにするために、ページテーブルとTLBの管理がOSのお仕事になります。
TLBを管理する方法はプロセッサによって異なります。x86ではページテーブルのアドレスを指定する程度になりますが、MIPSではTLBの入れ替えなども全てOSで行う必要があります。

MIPSのアドレス変換の流れ


まず、アドレス変換の対照となる仮想アドレスは上位20bitsをVPN(Virtual Page Number)と呼び、下位12bitsをページ内オフセット(図ではIn-page address)などと呼びます。
その他に関連する情報として、現在のプロセスがどのアドレス空間に所属しているかを示す、ASID(Address Space Identifer)があります。ASIDは後に詳細を述べますが、EntryHiレジスタの下位8bitsになります。

VPNとASIDを用いて、TLBエントリと比較します。TLBエントリは1つのEntryHiと2つのEntryLoの複数セットからなり、VPN上位19bitsとASIDから対応するEntryHiを1つ探しだし、VPNの下位1bitでEntryLoを選びます。
有効なEntryLoが見つかった場合はTLBヒットとなり、EntryLoからPFN(Physical Frame Number)を得ることができます。
TLBミスの条件やTLBミス時の動作についての詳細は後で述べます。
PFNを得たら、仮想アドレスのVPNの部分をPFNに丸ごと取り替えた値が物理アドレスとなります。

TLBに関連するレジスタ

EntryHi
  • ASIDは現在のプロセスが属するアドレス空間を示す
  • VPN2は仮想アドレスの上位アドレス(ページサイズより上位)
  • なぜ2がついているかというとEntryHiに対応するEntryLoがペアになっているため
  • TLB命令を使った場合、EntryHiが変わる(ASIDが変わる)ため操作後に戻さないといけない
EntryLo
  • PFNはVPNに対応する物理アドレス
  • なぜ定義上でPFNよりbits数が多いのか謎
  • Cはキャッシュ設定。プロセッサによってライトスルー、キャッシュしないなどの設定を可
  • Dは書き込み可能かどうか。0で書き込みをすると例外(TLB Modified Exception)が発生する。初期状態で0にしておき、書き込みが起きたときに1にすることによってダーティかどうか判定できるようにする。
  • Vは有効なTLBかどうか。0の時に参照すると例外(TLB Invalid Exception)が発生する。無効化するときに0にする。
  • Gが1だとASIDを無視する。複数のプロセスで共有したい場合に1にする。
PageMask
  • ページサイズを決めるためのレジスタ
  • Maskのうち1になっている部分が無視される。
  • 定義で下位ビットが0になってる部分を1にして仮想アドレスとのandを取るとin-page addressになる。
Index
  • TLB命令で操作するTLBエントリを指定する
  • tlbp命令で結果をIndexに反映する。31bitが1だと失敗した(見つからなかった)ことを意味する。
Random
  • tlbwr命令で操作するTLBエントリを指定する
  • 1サイクル毎にカウントダウンする。Wiredレジスタの値より小さくならない。
  • TLBエントリの入れ替えは基本的にランダムで行う方針らしい
Wired
  • Randomレジスタが指定しない範囲を示す。TLBエントリの0からWired-1を指さなくなる。
  • TLBエントリを固定で使用したい場合に利用する。
Context
  • TLBの入れ替え(TLB Refill)を高速に行うためのレジスタ
  • PTEBaseに任意の値を入れておく。通常、ページテーブルのアドレスを入れておく。
  • BadVPN2はTLB Refill例外が発生したアドレス(BadVaddr)の上位19bits。
  • PTEBaseをうまくセットすることにより、例外時にContextのアドレスに欲しいTLBエントリが格納されているアドレスを参照できるため、高速にTLB入れ換えが可能になる。
XContext
  • 64bit用のContext
  • 32bitを対象にしているため説明しません
BadVAddr
  • TLBの例外が起きたアドレス

TLB操作命令

tlbr命令
  • Indexで指定したTLBエントリをEntryHiとEntryLo0,EntryLo1レジスタに読み込む
tlbw命令
  • Indexで指定したTLBエントリにEntryHiとEntryLo0,EntryLo1レジスタの内容を書き込む
tlbwi命令
  • Randomで指定したTLBエントリにEntryHiとEntryLo0,EntryLo1レジスタの内容を書き込む
tlbp命令
  • IndexにEntryHiレジスタにマッチするTLBエントリの番号を読み込む

TLB例外

TLB Refill Exception

対応するTLBエントリが見つからなかった。tlbwr命令などでTLBの入れ換えが必要。
TLB Refill例外のみ、専用の(例外処理の)エントリポイントが存在する。
ただし、例外処理中にTLB Refill例外が発生した場合(Nested TLB Refill例外)、汎用のエントリポイントに飛ぶ。

TLB Invalid Exception

TLBエントリは見つかったが無効化されている。tlbwr命令などでTLBの入れ換えが必要。
汎用の(例外処理の)エントリポイントに飛ぶ。

TLB Modified Exception

TLBエントリが見つかったが書き込みできない(D=0)。D=1に更新する。
汎用の(例外処理の)エントリポイントに飛ぶ。

TLBエントリの管理の例

Contextレジスタを最大限利用する場合、各ASID毎のページテーブルを4MB境界(PTEBaseが23bitからだから)で配置すると良い。
4MB境界で配置し、PTEBaseに上位ビットをセットしておくと、例外発生時にContextレジスタが入れ換えたいEntryLoが格納されているアドレスを指している状態になる。
よって、TLB Refill例外の処理は以下のように非常にシンプルになる。
(See MIPS Runから転載しました。)

TLBmiss32:
   mfc0    k1, C0_CONTEXT
   lw      k0, 0(k1)
   lw      k1, 8(k1)
   mtc0    k0, C0_CONTEXT
   mtc0    k1, C0_CONTEXT
   ehb
   tlbwr
   eret

この管理方法の問題点は、4MB境界という広い領域をどうやって確保するかという点にある。
1ASID毎に4MBということは、256ASIDで1GBになってしまう。
実際には4MBのページテーブルを作成したとしても使われる範囲はごくわずかであるため無駄が大きい。

そこで、ページテーブル自体を仮想アドレスに配置する。
仮想アドレスに配置することで、実際に4MBのページテーブルを作成したとしても使われない領域に物理メモリが使われなくなる。

物理メモリ上に直接ページテーブルを作成した場合には常にページテーブルを参照することができたが、
仮想アドレス上に配置した場合にはアドレス変換が必要になるため、
ページテーブルがあるアドレスのTLBエントリが無いという場合がありうる。
上記のサンプルコードの3,4行目のロード時に発生する可能性がある。
これはNested TLB Refill Exception(専用の名前があるわけではないのでネスト例外とでも呼ぶ)と呼ばれ、特別な例外処理となる。

ネスト例外は通常のTLB Refill Exceptionとは異なる汎用的な例外処理エントリポイントで処理される。
つまり、他の例外と同様に、Causeレジスタで例外発生理由を判断し、BadVAddrレジスタで例外が発生したアドレスを得て処理をする必要がある。
ネスト例外と通常の例外処理とが異なる点は、
EPC(例外処理が終わったあと戻る場所)の位置がネスト例外が発生した場所ではなく、最初に例外が発生した場所になることである。
ネスト例外を処理後、eret命令により例外発生前の場所に戻ろうとすると、TLBmiss32のロード命令の場所ではなく、ユーザプログラムまで戻ることになる。
ユーザプログラムに処理が戻ってもユーザプログラムが必要としているTLBに関しては処理されていないため、再びTLB Refill例外が発生する。
しかし、2回目の例外処理ではTLBmiss32でネスト例外が発生することなく処理が完了する。

(1回目)ユーザプログラムでload==(TLB Refill例外)==>TLBmiss32でload==(ネスト例外)==>汎用例外処理==>eret==>ユーザプログラム
(2回目)ユーザプログラムでload==(TLB Refill例外)==>TlBmiss32でload(例外発生せず)==>eret==>ユーザプログラム

このようにして仮想アドレス上にページテーブルを配置した場合でも問題なくTLBの入れ換え処理を行うことが可能である。
仮想アドレス上に配置することで、Contextレジスタを利用した高速なTLB Refill例外処理を実現しながら
領域を節約した実装が可能になる。