PDP-11/40のメモリ管理を理解したい

PDP-11/40で動作したUNIX V6のカーネルを理解するには、UNIX云々の理解も必要ですが、PDP-11の理解も必要です。カーネルが（旧いスタイルの）C言語で書かれているから、ソースを読めば何をしているか見当をつけることができるとしても、その前提にはPDP-11を深く理解していることが必要です。

PDP-11について深い理解が必要だとしても、いきなり全てを理解するのは無理ですから、まずはメモリ管理から勉強することにしました。PDP-11のメモリ管理は、11/40、11/45、11/70で違いがあるものの、11/40が基本のようです。『PDP-11/40 processor handbook』の「Chapter 6 Memory Management」を理解できるようにしたいと思います。

2024年現在主流のx86などのメモリ管理に比べれば、PDP-11/40のメモリ管理はシンプルです。わざわざ勉強なんかしなくても、理解できるだろうと言われてしまうかもしれません。それはその通りだとは思います。概念的な理解ならば、別に「勉強する」と意気込むほどのことではありませんが、UNIX V6のカーネルを読んでいく為に必要な理解をするには、それなりの勉強が必要だと思います。

 

PDP-11/40のメモリ空間は、仮想アドレス空間が16ビットなので、64Kバイトです。PDP-11は2バイトをワードとして扱うことを基本としているようなので、64Kバイトは32Kワードです。物理アドレス空間は、PDP-11/40や11/45では18ビットあるので、256Kバイト（128Kワード）あります。PDP-11/40のメモリ管理機構により、仮想アドレスが物理アドレス空間のどこかに対応されることになります。まず上位3ビットにより、8セットあるActive Page Registerの何れかが選択されることになります。64Kバイトが8分割されることになるので、8Kバイト（4Kワード）を単位として管理されています。

Active Page Register（APR）は、Page Address Register（PAR）とPage Description Register（PDR）の組み合わせで構成されています。仮想アドレスの上位3ビットによってAPRが特定され、そのPARによって物理アドレス空間における領域がPARによって指定されます。ここでPARで指定できるのは12ビットなので、18ビットある物理アドレス空間をバイト単位で指定することができません。PDP-11のメモリ管理では、6ビットで表現できる領域として64バイト（32ワード）を最小管理単位としています。これを「ブロック」と呼んでいるようです。PARによって物理アドレス空間上の位置が特定されますが、それは先頭位置であり、そこから確保されている範囲はPDRで指定されています。最小1ブロック（すなわち32ワード）で、最大128ブロック（つまり4Kワード）です。

 

このようにして仮想アドレスが物理アドレスにAPRにより変換されます。『PDP-11/40 processor handbook』の「Figure 6-4 Construction of a Physical Adress」に概念図が掲載されていますが、別に複雑ではありません。UNIX V6としては、カーネルがメモリ管理できるようにするために、ブートストラップ処理の中で初期設定をおこなっています。ブートストラップ処理の最初の段階では、メモリ管理が無効状態なので、仮想アドレスとは言っても現実の物理アドレスと一致しています。しかし初期設定が済めば、直ちにメモリ管理が有効となり、仮想アドレス空間が現実の物理アドレス空間の何処に割り当てられることになるのか、きちんと理解しておかないとカーネルを勉強したことにはならないでしょう。

PDP-11におけるSOB命令の挙動

UNIX V6のカーネルのブートストラップ処理を追いかけています。m40.sの「start」ラベルから始まる処理を調べていますが、Lions本で言うと0628行目に、「sob r3,1b」 という処理が現れます。ここで使われている命令「sob」について確認してみました。

『PDP-11/70 PROCESSOR HANDBOOK』の4-67ページに命令「SOB」について説明があります。

Operation: R ← R -1 if this result = 0 then PC ← PC -(2x offset)
Description: The register is decremented. If it is not equal to 0, twice the offset is subtracted from the PC (now pointing to the following work).

この命令が何をしようとするものなのかは分かりましたが、よく見ると「Operation」と「Description」の挙動が整合していません。前段の、「Operation: R ← R -1」というのが、「Description: The register is decremented.」と説明されているのは、整合がとれています。しかし後段で、「if this result = 0 then PC ← PC -(2x offset)」と「If it is not equal to 0, twice the offset is subtracted from the PC (now pointing to the following work).」とは、意味が逆になっているのではないでしょうか。この命令がどうこうではなく、一般的に考えれば、「ある変数が0になるまでループする」というのが普通かと思います。そして「Description」では「If it is not equal to 0,」とあるので、思っていたとおりなのですが、「Operation」では「If this result = 0」となっていて、これは違うのではないかと思います。

念のために他の資料も確認してみました。

1. 『PDP-11/40 PROCESSOR HANDBOOK』では、「Description」の記述は同じですが、「Operation」が「If this result ≠ 0」となっています。
2. 『PDP-11/45 PROCESSOR HANDBOOK』は、11/70と同様です。「Description」の記述も同じで、「Operation」も「If this result = 0」になっています。
3. 『PDP-11/34 PROCESSOR HANDBOOK』は、11/40と同様です。「Description」の記述も同じで、「Operation」は「If this result ≠ 0」になっています。

 

これらより、命令「SOB」の説明は、11/40が正しく、11/45や11/70は誤植なのでしょう。

PDP-11の777572番地はMMRなのかSRなのか、それともSSRなのか

PDP-11/40で動作するUNIX V6のカーネルを勉強するため、まず最初にブートストラップ処理を追いかけていこうと思っています。その処理はm40.sのstartラベルから始まります。まず最初に「bit $1,SSR0」という処理が現れますが、SSR0とは何でしょうか。カーネルを読み進めていくには、PDP-11について幅広く理解していることが求められます。カーネルを学んでいる最中には、それほど知識を有しているわけではありませんから、DECが発行していた資料を調べてみたりする必要があります。その最初の課題が「SSR0」を理解することです。

 

1972年に発行された『pdp-11/40 processor handbook』を参照すると、「CHAPTER 6 MEMORY MANAGEMENT」の中に「6.6.1 Status Register #0 (SR0) (status and error indicators)」という項目があります。ここでは「SR0」とあり、「SSR0」ではないのですが、おそらく同じものです。同書の巻末にある「APPENDIX B MEMORY MAP」では、777572番地が「11/45 SSR0」と説明されています。なぜか「11/45」と断っているし、「SSR0」となっているのも気になります。Lions本では、m40.sの1445行で「SSR0 = 177572」とあるので、SR0が正しいのかSSR0が正しいのか不明ですが、UNIX V6ではSSR0としているようなので、あえて意義を唱えることもありません。

これで一件落着かと思うところですが、さらに調べてみると、疑問が拡がりました。1973年に発行された『pdp-11/45 processor handbook』を参照してみると、「CHAPTER 6 MEMORY MANAGEMENT」の中に「6.6.1 Status Register #0 (SR0) (status and error indicator)」という項目があります。これはpdp-11/40と同じなのですが、巻末の「APPENDIX C MEMORY MAP AND RESERVED LOCATIONS」では「777572 through 777577 Memory Management Status Register 0-2」とあり、pdp-11/40とは表現が異なります。

 

さらに1975年に発行された『pdp-11/70 processor handbook』を参照すると、「CHAPTER 6 ADDRESSING」の中に「6.5.6 Fault Recovery Registers」とあり、そこでは「Memory Management Register #0 (MMR0) (status and error indicators)」と名称が変わっており、巻末の「APPENDIX A UNIBUS ADDRESSES」では「777 572 Memory Mgt regs. (MMR0)」となっていて、もはやSSR0とは名乗らず、MMR0で統一されています。

 

777572番地のレジスタの名称が「SSR0」だろうと「MMR0」だろうと、DECが決めた名称なので、どちらでも構わないのですが、PDP11のモデルによって名前が変わるのは、今後資料を参照する際に混乱しそうで、ちょっと心配です。PDP11の後継機種の資料を参照すると、もはや「SSR0」とは呼ばず、「MMR0」となっているので、DECで方針が変わったのではないかと推測します。当初の「Status Register (SR)」というのは、機能として実体に即しているとは思いますが、意味が一般的すぎることを懸念したのかもしれません。最終的に「Memory Management Register (MMR)」とすることで、より限定された意味を持たせることにしたのでしょう。

 

この調査をしていて、いろいろな資料を見つけました。1976年に発行された『KT11-D memory management option user's manual』では「CHAPTER 3 OPERATION AND PROGRAMMING」の中に「3.6.1 Status Register 0 (SR0)」とあるのは、上述した『pdp-11/40 processor handbook』で書かれていたのと、ほぼ同じ内容です。この資料の「CHAPTER 2 INSTALLATION INFORMATION」には以下の記述があり、pdp-11/40と11/35で使われたモジュールであることがわかります。

The installaion procedure for the KT11-D Memory Management Unit option is included as part of the complete PDP-11 system installation procedure described in Chapter 2 of the PDP-11/40, PDP-11/35 System Mnual (21 Inch Chassis).

 

 また1972年に発行された『PDP-11/45 memory management reference manual』では「INTRODUCTION」において以下の記述があります。PDP-11/70もメモリ管理としてはPDP-11/45と同等のようなのですが、PDP-11/70でKT11-Cを使用しているという情報は得られませんでした。

The KT11-C Memory Management Unit is a hardware option designed for use with the PDP-11/45 Programmed Data Processor.

 

UNIX V6カーネルのlow.sを読む

UNIX V6カーネルを学ぶため、日本語版の『Lions' Commentary on UNIX』を参照し、DECが発行していた各種資料などを参考にしつつ、ロジックを追いかけていこうと思います。カーネルは、システムコールを受け付けたり、メモリやディスクなどのリソースを管理したり、割り込みを処理したり、様々な役割を担います。しかしそれはカーネルが起動し定常状態に達してからの話であって、マシンが起動しカーネルが読み込まれたブートストラップ処理とは違う世界の話です。カーネルを学ぶために、どの切り口から挑んでいくかは人それぞれかと思いますが、私はブートストラップ処理から始めようと考えています。そうであれば、まず最初に見ていくのはlow.sです。

 

Lions本でlow.sは、0500-0599行目に相当します。日本語版では66-67ページにあります。

1. 0502-0505行では、br4からbr7という識別子に値を割り当てています。PDP-11に親しんでいれば疑問に思うことも無いのかもしれませんが、私はbr4やbr7というのが何なのか分かりませんでした。DECの資料を読んでいくと、brというのは「Bus Request」のことで、PSWのプロセッサ優先度ビットを定義していることが判明しました。
2. 0507行では、アセンブルされた結果が格納されるアドレスを指定しています。同様の記述が0520行や0529行などにもあります。この記述はPDP-11アセンブラの記述方法なのか、UNIXアセンブラ独時の記法なのかわかりませんが、とても特徴的です。Lions本では266ページで開設されています。ともかく0507行は「. = 0^.」となっていますから、000000番地を指定していることになります。
3. 0508行では、「br 1f」とあり、0522行目にある「1」というラベルに飛びます。これはそれだけのことだと思いますが、0509行には「4」という数字が突然表れます。これは何なのか、何故「4」なのか、これは誰かが参照しているのか、まったくわかりません。次の0512-0518行目には「トラップベクタ」が並んでおり、これらはアドレス毎に役割が決まっていますから、それとアドレスがずれないようにするための埋め草なのかもしれません。そうならば「4」などという意味の分からない数字ではなく「0」でも良いような気がしますし、または「. = 4^.」を入れても構わないような気がします。
4. 0512-0518行では、上述したとおり「トラップベクタ」が並んでいます。これらはPDP-11によって構造が定義されており、最初のワードが呼び出すルーチンのアドレスで、次のワードがPSWに格納される値です。それはよいとしても、全て「trap」というルーチンを呼び出すことになっているのは何故かという疑問は残ります。さらに謎なのが、「br7+0.」のように、0505行で定義された「br7」に数字を加えていることです。表記上の注意事項としては、数字にピリオドが付加されており、これはLions本の265ページに書かれているように10進数と解釈されるための工夫です。わざわざ10進数としなくても、8進数で記述しても良かった気もしますが、それはどちらでも構いません。疑問なのは、何故「br7」に数値を加えているのかです。これはPDP-11によってPSWに格納されるワードなので、加算された値はNZVCフラグに何かが入ることになります。それを「trap」ルーチン側で参照しているのかというと、そうでもなさそうです。参照していないような気がしますが、これはm40.sにあるルーチンなので、そこで再度考えてみようと思います。ちなみに「br7」に数値を加算しているのは、0538行とか0547-0549行にもあります。しかも「br7+7.」というのが、0538行と0547行にあり、重複してもよいのだろうかという疑問もあります。
5. 0522行では、「jmp start」があります。ここは40番地になっており、PDP-11としては「System Software」が利用する領域という扱いになっています。0番地では「br 1f」として40番地に飛び、40番地では「jmp start」として更にstartに飛ぶので、何故こんなに手間をかけるのだろうかとは思いますが、何か歴史的な事情とか、PDP-11の都合とかがあるのかもしれません。
6. 0523行では、「jmp dump」という命令が置かれています。ここにはラベルも与えられていませんが、どのようにして呼び出されることになっているのでしょうか。おいおいわかってくることを期待しています。
7. 0525-0544行では、デバイス事の割り込みベクタが定義されています。そもそもlow.sはmkconfによって生成されるものなので、現実のUNIX V6においては利用されるデバイスに相当する割り込みベクタが出現するはずです。Lions本では説明の都合上必要なデバイスだけが現れます。そこではbr4-br7の何れかが記述されていますが、それらはデバイスのデフォルト値として、それぞれのマニュアルに記述されています。マニュアルによって記述箇所は一定していませんが「Address and Priority Assignments」という箇所に書かれていることが多いようです。
8. 0558-0577行では、0525-0544行の割り込みベクタで指定されているルーチンが定義されています。基本的な構造は同一で、0558行のklinであれば「jsr r0,call; _klrint」となっています。ここに現れる「call」はm40.sにあるので、あとで詳細に見ていくつもりです。ただし現時点で不思議なのは、なぜ「jsr」命令をつかっているんだろうということです。ここには「jsr」命令が並んでいますが、「Jump Sub Routine」という名前から想像されるところでは、サブルーチンから戻ってくるのだろうかと思うところですが、多分片道切符で、戻ってこないのでしょう。それならば「jmp」命令のほうが自然ではないかと思うのです。

 

low.sを見てきて、いろいろと疑問が生まれ、それらが全て解決したわけではありません。疑問が残ったままですが、カーネルのブートストラップ処理を追いかけるため、次は「start」処理を見ていこうと思います。

UNIX V6のmkconfはl.sとc.cを生成する

UNIX V6のカーネルを学ぶため、日本語版の『Lions' Commentary on UNIX』を主な参考書として使おうと考えています。この書籍にはUNIX V6カーネルの全ソースコードと解説が掲載されていますから、これだけあればソースコードとしては十分なのですが、ネット上にはUNIX V6のソースコードが置かれているので、それも併用しようと思います。

 

カーネルを理解するには、闇雲にアプローチしても手に負えません。カーネルは光の当て方によって、様々な姿を見せてくれますから、そのどこかに注力して、カーネルの深淵に迫ろうと思っています。Lions本にはLions本なりのアプローチがあり、BSDの黒本には黒本なりのアプローチがあります。どこからアプローチしても、途中で挫折しなければ、到達点は同じのハズです。

 

PDP-11/40にカーネルがロードされ、実行を開始し、初期設定などが完了してカーネルとして機能する準備が完了した後ならば、ユーザプロセスからシステムコールを受け付けたり、メモリ管理を行なったり、ファイルシステムによりファイル操作をするなど、カーネルとしての役割を淡々と実行していきます。カーネルとしての諸機能を恙なく処理するには、カーネルの実行開始時にリソースの初期設定を済ませておく必要があります。このような視点では、カーネルの初期状態と定常状態という2つの状態としてカーネルを理解するアプローチになります。

 

カーネルが定常状態に入った後は、システムコールとか、メモリやディスクなどのリソース管理とか、デバイスドライバの処理など、様々な観点からカーネルを見ていくことになるでしょう。しかしそれは、カーネルが初期状態を終えた後の話です。まずは、UNIX V6のカーネルが初期状態で何をしているのか理解するところから始めようと思います。

 

Linos本によれば、カーネルの初期状態は、66ページに掲載されているlow.sから始まります。UNIX V6のカーネルをネット上で探して見ると、The Unix Heritage Societyで「Sixth Edition Unix」を見つけました。ここに置いてあるのは、Lions本とは違う点があります。

1. Lions本では「unix」というディレクトリの下にフラットにソースファイルがあるように見えますが、上述した場所では、kenとかdmrなどのサブディレクトリに分かれています。
2. Lions本では、説明の都合上だと思いますが、説明対象外のデバイドライバのソースファイルは掲載されていませんが、上述した場所では全て置いてあります。
3. ここが最も重要かと思いますが、Lions本で掲載されているlow.sとconf.cは、上述した場所には置いてありません。
   

 

Lions本では、291ページで次のように書かれています。これはlow.sの説明ですが、conf.cも同様の記述があります。

mkconfと呼ばれるユーティリティプログラムによって生成される。

 

確かに上述した場所にはmkconf.cがあるのですが、このユーティリティプログラムが生成するのはl.sとc.cであって、low.sとconf.cではありません。カーネルの生成につかわれるスクリプトを見ても、生成されるのはl.sとc.cとして処理されるようになっています。Lions本が何故low.sとconf.cに変わっているのか、理由は不明です。もしかして初期のV6はl.sやc.cだったけど、いずれかの時点でlow.sやconf.cに変更されたのかもしれないと想像しました。しかしUNIX V7のmkconf.cを参照してみましたが、相変わらずl.sとc.cのままだったので、先の仮定は成り立たないようです。

 

Lions本がlow.sとconf.cに変更されているのは、独自に変更したのか、そういう変更が加えられたものを入手したのか、経緯は不明です。

UNIX V6のブートストラップ

PDP-11で動作したUNIX v6の内部構造に関する資料としては、『Lions' Commentary on UNIX』が有名です。これを用いてカーネルについて学んでみようと思い、いろいろと情報を集めているところです。

 

カーネルと言うものは、UNIX V6に限らず、WindowsでもLinuxでも、マシンの電源が入ってから、ブートストラップ処理を経て、カーネルとしての起動が完了します。カーネル自体はマシンの機種依存性が少なくなるように作られていますが、ブートストラップ処理はマシンに強く依存した処理になっています。

 

上述したLions本では、ブートストラップ処理について次のように書かれています。

これで、プロセッサのROMに永久に記憶されているブートストラッププログラムがスタートする。ブートストラップローダープログラムは（システムディスクのブロック#0から）大きなローダープログラムをロードし、この大きなローダープログラムが/unixと呼ばれるファイルを探し、メモリの低位部分にロードする。

 

これが間違いとは思いませんし、現状のWindowsやLinuxだって同様のブートストラップ処理をおこなっているはずですが、現状のパソコンのブートストラップ処理と同じイメージを持つと、PDP-11当時の状況を見誤ってしまう気がします。

調べてみたら、Web上で「PDP-11のブートストラップ」という記事を見つけました。Lions本ではあっさりと書かれている処理が詳細に書かれているので、細部がよくわかります。

しかもLions本で「プロセッサのROMに永久に記憶」されていると書かれている「ROM」というものが、現状のパソコンのような半導体メモリをイメージしてしまうと、当時の状況を反映していないと思われます。これもWeb上の記事「Diode Matrix」を見ると、具体的にわかります。

 

またYouTubeでも「PiDP-11 - Manually toggling the bootloader for RT-11」や「Booting v6 Unix on a PDP-11/34」などを視れば、PDP-11で起動する手順がどのようなものだったのかが、よくわかります。