皆様こんにちは．18のhiraです．
僕はコンピュータ工学をやっているつもりなのですが，最近アドレス変換に触れ理解に苦しんだため，備忘録的にその挙動を記録します(そのため正確性はありません…)．
OSが載っているような複雑なコンピュータでは，Excelやゲーム，音楽ソフトなど複数のアプリを同時に動かすことができます．この時，アプリ同士のアドレスが重ならないようにアドレスをずらす機構があります．
この変換機構は Memory Management Unit (MMU) という機構によって行われます．またこの変換方法も代表的なものがいくつかあり，今回は32bitのRISC-Vが公式に使用するSv32を題材として紹介します．
ページとアドレス変換
複数のアプリを実行すると，例えばExcelのプログラムとゲームのプログラムがどちらも「1234」というアドレスを使いたい場合，奪い合いになったり，一方が予期しない上書きが行われる可能性があります．
正常動作のためにはプログラムごとに使用するアドレスの範囲をずらす必要がありますが，それぞれのプログラムは独自に作成され，どのプログラムと一緒に実行されるかなど知る由もありません．
そのため実際には実行時にアドレスを変換しています．
例えばプログラム作成時にExcelが0~2000まで，ゲームが0~3000までのアドレスを使うとしている場合，コンピュータは実行時にExcelは10000~20000のアドレス範囲を物理的にメモリ上に割り当て，ゲームには40000~60000の範囲を割り当てます．Excelの元の0~2000といったアドレスは10000~20000の中に対応付けられ，他のアプリと干渉することはなくなります．
このプログラムのアドレスを 仮想アドレス(virtual address) ，実行時に変換されたメモリ上の実行アドレスを 物理アドレス(physical address) といいます．
ページング方式
メモリは一定のアドレスの範囲ごとに分割されて管理されています．この1つのアドレスの範囲を ページ と言います．
次節の図1のメモリの場合，下位8bitが00~ffまでのアドレスを1つのページとしています．
ページとして分割することでまとまったアドレス範囲の取扱がしやすくなり，アプリ1にはページ1~10，アプリ2にはページ100~105を割り当てるといったアドレス空間の分割管理がしやすくなります．
Sv32の場合，1枚のページは4KBのデータを持ちます．
またページという抽象化を行うことで，実際のメモリより大きなアドレス空間を扱えます．
例えば物理メモリの大きさが1GBしかなくても，メモリに入り切らないページを外部記憶装置(HDDなど)に一時保管して必要に応じてメモリに送ってやれば，CPUからはあたかも100GBのメモリがあるかのように同じ「ページ」の仕組みのままで扱えます．
このメモリ，メモリ上に今使いたいページが無いことを Page Fault と言い，またページフォルト発生時に該当するページを外部記憶装置間からメモリに取ってくる(+不要なページを追い出す)ことを Page Swap と言います．
MMUとTLBによる仮想-物理アドレス変換
仮想アドレスと物理アドレスの変換を行うのがMMUです．例えば図1のCPU0ではプログラムの仮想アドレス0x10**がMMUによってメモリ上の物理アドレス0x96**に変換されています．
この時，仮想-物理アドレスの変換テーブルを記録しているのが Translation Lookaside Buffer (TLB) です．TLBは一度変換したことのある仮想-物理アドレスの対応を記録しておき，次に同じアドレスを変換する際はこのテーブルを引くことで面倒な変換アドレス計算を省略できます(図1赤線)．
一方，初めて変換するアドレスの場合，TLBのテーブルにはまだ変換先の情報が無いため，変換先を計算する必要があります(図1青線)．
この時， Table Walk という変換アドレス計算(次節)を行います．これにより与えられた仮想アドレスに対応する物理アドレスを求め，TLBのテーブルに対応関係を記録します(図1紫線)．
対応先の物理アドレスが求まったら改めてメモリにあるその物理アドレスにアクセスします（図1緑線）．
この時，物理アドレスを含むページがメモリ上に無い場合はページフォルトとなります．外部記憶装置から該当する新しいページをメモリに読み込みます(図1黄線)．
変換テーブルを記録するTLBですが，これ自体にも色々種類があるようで，次節のVPNの10bitを記録する方法や，上位16bitを記録する方法などがあるようです．
物理-仮想アドレスの対応計算
仮想アドレスから物理アドレスへの変換は複数の段階を経て行われます．多段階にすることで使用するアドレス空間の細かな制御ができるようになり，冗長なページ管理データを削減しています．
32bitのSv32方式ではプログラムのアドレスは，仮想/物理アドレスは Virtual / Physical Page Number (V/PPN) に分けられます．仮想アドレスの場合，
- [31:22]の10bitのVPN[1]
- [21:12]の10bitのVPN[0]
- [11:0]の12bitのoffset
に分割されます．同様に物理アドレスもPPN[1]，PPN[0]，offsetに分割されます．1stステージではVPN[1]，2ndステージではVPN[0]が使われPPNが求められます．offsetは仮想/物理で共通です．
さらに，変換先の計算ではRISC-VのCSRの1つであるsatp registerが使われます．これのPPNを用いて基準アドレスである root PTE を最初に求めます．
仮想/物理アドレスの対応先の計算は以下の流れで行われます．
- satp registerから root PTEを求める(a)．
- root PTEにVPN[1]を加え1stステージのPTEのアドレスを求める．
- PTEの下位4bitから，そのPTEの内容をチェックし，PTEの上位22bitのPPNの扱いを判断する．
・xxx0: valid=0なのでページフォルト
・0001: 次ステージのPTEへのポインタとなるPPN
・xxx1(0001以外): 仮想アドレスに対応する物理アドレスのPPN - 今回は0001なので次ステージのPTEを求める必要がある．
- PTEの上位bitをPPNとする次ステージの新たなPTEを求める．
- 更新したPTEを確認する．今回はxxx1のため，このPTEが leaf PTE である．このPPNにoffsetを足したものが求める物理アドレスである．
こうしてある仮想アドレスに対応する物理アドレスが計算されました．この結果をTLBに記録することで，次回からは上記の計算をすること無く，TLBのテーブルを引くことで対応する仮想/物理アドレスが求まります．