コグノスケ

Linuxのstruct pageって何

目次: Linux

以前からLinuxのページディスクリプタ（要はstruct page）って何なの？という疑問が晴れないまま居ました。特に実際のページフレームとの対応をどうやって取っているのかが全くわからん。どこかに対応が書いてあるにしては、それらしい場所がない…。

分からんながらも、機会を見つけては調べたり考えたりしていたら、なんとなーく分かった気がする。

分かった気がすることを書き散らしますが、間違っててもご勘弁下さい。自信ないです。

メモリゾーン

前提知識として簡単に説明します。Linuxではメモリ領域をゾーンという固まりで管理しています。ゾーンはページフレーム（普通は4KBのメモリ領域）をいくつかまとめた固まりです。ページフレームがずらーっと並んでいるようなイメージ。

厳密にはもっと書くべきことがあるのでしょうが、今回はこのくらいの理解で進めるはず。たぶん。

ページディスクリプタとページフレーム

では本題に入ります。
まず私の疑問点は「ページディスクリプタ（以下、struct page）のポインタをもらったとき、どうやって対応するページフレームを得るのか？」です。

ここでstruct pageのメンバに直接書いてあれば話は早いのですが、struct pageにページフレーム番号を示す情報などはありません。残念。

実はstruct pageは中身も大事ですが、ポインタ値が非常に重要な意味を持ちます。というのも実メモリのページフレームとの対応を取るために、ポインタの計算を行うからです。計算についてはまた説明します。

ページフレームを求めるためには、
ページディスクリプタ -> ゾーン -> ページフレーム
の順に求めます。まどろこしいですが、直接求められないのです。

ページディスクリプタ -> ゾーン

ページディスクリプタが対応するページフレーム、こいつが属するゾーンを求めます。自分でも何言ってるのかわかんないけど、まあいいや。

まずstruct pageにpage_flags_t flagsというメンバを見ます。こいつはその名の通りページの属性や状態を示すフラグを格納する変数なのですが、上位3ビット（または8ビット）だけは意味が違っていて（※1）、このページが所属するゾーンを表す数値が入っています。

なのでflags >> NODEZONE_SHIFTによってページが何番目のゾーンに所属しているのかがわかります。例えば1だとしたら、ゾーンの配列zone_table[1]（グローバル変数）を見ればゾーンの情報が見られます（※2）。

（※1）不思議な設計に見えますが、むやみにメンバを増やすとstruct pageだけで相当量のメモリを圧迫（struct pageはページフレームの数だけ存在する）してしまいます。

（※2）最近のLinuxではゾーンの一覧（zone_table）はグローバル配列ではありません。struct pglist_dataという構造体（ゾーンが必要ならnode_dataというグローバル配列（アーキテクチャ依存）、ゾーンが不要ならcontig_page_dataという変数）経由でゾーンを見るようになっています。ゾーンが要らないというアーキテクチャを考慮したのでしょう。

ページディスクリプタ＆ゾーン -> ページフレーム

長くなってきましたが、本題のページフレームの求め方に行きます。先ほど苦労して求めたゾーンにはzone_mem_mapというメンバが居て、ゾーンに属するstruct pageの一覧を持っています（※3）。

ゾーンのzone_mem_mapのイメージ

上の絵で注目して欲しいのはzone_mem_mapと、ページディスクリプタのポインタ（pとします）がわかれば、zone_mem_mapの何番目にpが存在しているかわかるということです。上の絵では5番目に位置しています。

薄い水色の四角内で具体的な数値（数値は適当ですが）を当てはめてpのアドレスからzone_mem_mapのアドレスを引くことで、pがzone_mem_mapの何番目にいるか求められる様子を示しています。

ページフレームを求める

これでstruct pageがゾーンの先頭から何番目のページなのかがわかりました。あとはページフレームを求めるだけです。ゾーンの構造体のメンバzone_start_pfnがゾーンの開始ページフレーム番号を表しているので、そこへ先ほどの数字（5）を足します。

これにてstruct pageと対応するページフレームが求められました。

もし物理アドレスに興味があるのならば、ページフレームの番号にページフレームのサイズ（普通は4KBのはず）を掛けてあげればよいです。
高位メモリや非連続なメモリモデルを持つアーキテクチャだと、単純に掛けるだけではダメかもしれません。

（※3）最近のLinuxにはありません。恐らくzone_pgdat->node_mem_mapが等価だと思われます。たぶん…。

念のため

有給をとって休みました。お休みを病欠で消費するとすごくもったいない気がするのです…。

上の一文をどこかで見た気がすると思ったら、去年の6月11日（2007年6月11日の日記参照）にも風邪で有給を取って休んでいて、同じようなこと書いていました。ああ、進化してない。

昔からこの時期（4月末〜5月末）はほぼ確実に風邪を引いている。時期に何か秘密があるのかなあ？季節の変わり目にしては遅いような気がするんだけど。

風邪

熱は下がったけど、喉がヤバいことに変わりなし。起きている間に良化 -> 寝ている間に悪化を繰り返しているみたい。部屋の空気が乾燥しているとかかなあ？

昨日はご飯食べるの忘れてたので、今日はきちんと食べました。

今日は

おとなしく寝てました。熱もあるんだろうけど、鼻〜喉がヤバい。焼け付くような感じがする。

SP3というセキュリティフィックス

5/7にWindows XP SP3がリリースされました。デスクトップに早々とインストールしたものの、ノートのことをすっかり忘れていました。

これまた寝る前に始めたのが良くなかった。朝までノートを動かす羽目になりました。寝るときノートの液晶画面が眩しい、かといて閉じるとスリープする…とお悩みの方。スリープしないよう設定変更するのも手ですけど、単に輝度を最低に落とすだけでも割と良い感じですよ。

ブラウジング環境

会社でもSeaMonkeyを使っています。通常のブラウジングには苦労しませんが、会社の変なシステムがIE6専用でして、全く動きません。しかもやたら別ウインドウを開きたがる悪い癖のあるシステムなのでウインドウだらけになる。IE系のタブブラウザでも動くかなあ、動くようなら導入しようかな。

風邪悪化

5/6から引きずってた風邪がここにきて悪化してきた。頭がガンガンする。飲み会に行きたかったけど、諦めて寝よう。

メイリオは不明瞭

Windows XP用のメイリオフォントが公開されたので入れてみたら、IT Mediaのビジネスニュースサイト Business Media誠の表示がメイリオで出るようになってしまった。見づらい。

調べたら、スタイルシートでフォントが指定（"メイリオ","Hiragino Kaku Gothic Pro","ヒラギノ角ゴPro W3","ＭＳ Ｐゴシック",Osakaの順だった）されていたためでした。今までは優先度4の ＭＳ Ｐゴシックが選ばれていたのに、メイリオを入れたことによって優先度1のメイリオが選ばれるようになったわけです。

Webページでフォント指定するなよ、全くもってダサイな…。SeaMonkeyの設定で、Allow documents use other fontsをOFFに、ついでにMinimum Font Sizeも10くらいに上げておきました。ん、見やすい見やすい。

やめて！VAIOのHPはもう0よ！

いつからか我が家のVAIO type Gのファンがぶんぶん回りっぱなしになっています。冬の間は「うるせえなあ…」と思う程度で済んだのですが、改めて本体を触るとかなり熱い。

これから夏を迎えるに当たって温度が心配になってきましたので、原因を探ってみました。

負荷を調べる（2008年5月18日改訂）

さて負荷をどうやって調べるかが問題です。ファンがブンブンしている状態でタスクマネージャを見ても0％ のままで、負荷がかかっているのかすらわかりません。というわけで 1秒おきにrdtsc命令を発行し、その差分を表示するプログラムを書き（※）ました。

このプログラムが表示する値を理解するには、まずCPUの動作周波数がどうやって決まるか、rdtsc命令の返す値は何を表すか、を説明しなければなりません。付け焼き刃の知識で頑張って説明します。

（※）本来なら自分で書かなくても、Crystal CPUIDのReal Time Clock表示機能を使うべきです。しかしCrystal CPUIDは無駄に表示が凝っており、表示の負荷でシステムクロック周波数が上がる（rdtscの変化分が300MHzくらいまで）本末転倒状態だったので、没にしました。

システムクロックとCPUバスクロック（2008年5月18日追記）

まずCPUバスクロック（CPU <-> ノースブリッジバス）の説明から入ります。CPUバスクロックはシステムバスクロックの半整数倍です。VAIO君の場合はシステムクロック = 133MHz、CPUバスクロック = システムクロック（133MHz）x 4倍 = 533MHzのようです。

システムクロックはマザーボード上の水晶振動子（安い10MHz〜30MHzくらい？）を原発振としたPLL（Phase Locked Loop）で供給されます。PLLって何？と聞かれても詳しくは知らんので勘弁して下さい。

CPUバスはIntelの伝統でFSB（Front Side Bus）と呼ばれ（※）ますが、今回はCPUバスで通します。

ノースブリッジにはメモリコントローラが載っていてSDRAMが繋がっています。比較的高速のバス（AGPバス、PCI-e x16バス）などをノースブリッジに繋げることが多いようです。
ノースブリッジの先にはサウスブリッジが居て、PCIバス、PCI-e x1, x4バスなど、比較的低速のデバイスを繋ぐことが多いようです。

CPU <- (1) -> ノースブリッジ <- (2) -> サウスブリッジ
                  |                        | (PCIバス)
              DDR SDRAM                PCIデバイス

(1) FSB(Front Side Bus, Intel系), HyperTransport(AMD系)
(2) DMI(Direct Media Interface, Intel系), HyperTransport(AMD系)

別にこの2つでなければならないことはないです。
他の方式で接続するシステムも有るはず。

重要な点として、(1)、(2) のクロックとDDR SDRAMやPCIのクロックは全て同期しています。でないとデータのやりとりができないからだと思うんですが…。
そのためCPUバスと同様に、システムクロックから生成したバスクロックを用います。PCIバスだと33MHzを欲しがるので、システムクロック133MHz x 1/4 = 33MHzとします。

• CPUの動作周波数 = システムクロックx CPU内部動作周波数倍率
• CPUバスの動作周波数 = システムクロックx倍率
• 周辺バスの動作周波数（例: PCIバス）= システムクロックx倍率

（※）"Front" Side Busに対して "Back" Side Busもあるのか？
BSBもあります、いや…ありました。BSBはCPU <-> 2次キャッシュのバスです。しかし最近はCPUに2次キャッシュも混載されているのでBSBは不要です。ですから「最近のシステムにはありません」という方が正しそう。

rdtscとCPUの動作周波数（2008年5月18日追記）

rdtsc命令とはCPU内部のタイムスタンプカウンタを読み出す命令です。Core系以前のCPUではrdtscのカウントアップ周波数 = CPU動作周波数でしたので、SpeedStepなどで倍率を変化させるとrdtscの増分も変化していました。しかしCore系では常に一定の周波数（Core Solo 1500Uの場合は最大動作周波数1330MHz）でカウントアップされます。
（hdk氏、ご指摘＆情報提供ありがとうございます）

つまり、
過去のCPU: システムクロックx動作倍率（可変）
Core系: システムクロックx一定値
です。

じゃあ最初に書いたrdtscを見るプログラムって意味無くね？と思うのはまだ早いんだ、これが。

VAIO上で先ほどのプログラムを使ってrdtscの増分を見ると、システムの負荷によって変化します。rdtscの増分はシステムクロックx一定値、のはずですから、変化しているのはシステムクロック側と予想されます。

システムクロックを上げれば茨の道のオーバークロック（※）ですが、下げる方向に使えば省エネです。VAIOではCPUの省エネ機能（Enhanced SpeedStep）に飽きたらず、システムクロックも下げさらに省エネしようという設計なのでしょう。

（※）規定値よりシステムクロックを上げることをオーバークロックといいます。今までの説明からも類推できるように、システムクロックをメチャクチャ上げるとCPUバスクロック、さらにはPCIバス（1/4倍 = 33MHz）やAGPバス（1/2倍 = 66MHz）まで上がり、いずれバスに繋がっているデバイスの許容値を超えて異常動作したり動作しなくなります。
この問題の解決にはシステムクロックと周辺バスクロックの比率を変える必要があります。オーバークロックを売りにしているマザーボードだと比較的柔軟みたいです。

VAIOの現状（2008年5月18日追記）

システムに負荷をかけると、システムクロックが最大値に張り付いてrdtscの増分も最大値である1330MHzに張り付きます。負荷が低いと50MHz程度（※）まで落ちます。

さて、今のVAIOを見ると 1330MHzに張り付きっぱなしです。ファンがずっとブンブンしているのはこのせいでしょう。

ファンのスピードはシステム負荷に連動しているようなので、rdtsc値の増分を下げる方向 = システムクロックを下げる方向へ改善することで「ファンがブンブン言う問題」は解決すると思われます。VAIOがシステム負荷をどうやって測定しているのかまではわかりませんでした。

（※）負荷が低いときはCPU内部動作周波数倍率は6.0倍まで落ちますので、rdtscカウンタの増分x 6/10が本来のシステムクロックです。まあ、その辺の細かい値は今回どうでもいいので、高い、中間、低い、くらいが見えればOKです。

犯人はUSB HDDだ

というわけで犯人捜しです。片っ端からケーブルを引っこ抜いてみると、USB HDDを引っこ抜いた段階で50MHzくらいまで下がりました。犯人はこれかあ。手始めに、デバイスの取り外しで無効化してみたものの全く負荷が下がりません。

USB 2.0コントローラが有効な状態で一度USB HDDを認識させてから、USB 2.0コントローラ（Intel USB2 EHCI）を無効にすることで、USB 1.1の機器として再認識させると、負荷が下がりました。

これで解決ですね……って、こんなん毎回やってられんよ。面倒くさくて死にそう。

もしかして

ひょっとするとHDDケース（センチュリーのやつだった気がする）がおかしいのかもしれません。こやつは Windows XPの起動時に電源ONだと100％BoDするという、怪しさ爆発デバイスです。

というわけで別のUSB HDDを繋いで、再度実験。やはり負荷が上がってダメです。さらに手持ちのデバイスで実験。

• USB Flushメモリ -> 負荷高
• USB DVDドライブ -> 負荷高
• USB 2.0ハブ -> 負荷低
• USBモデム（NEC N902iS、USB 2.0デバイス） -> 負荷低
• USBマウス（USB 1.1デバイス） -> 負荷低

うーむ、どうもUSB Mass StrageがNGっぽいですね。WindowsのUSB EHCIドライバか、USB Mass Strageドライバのどちらかが常に負荷をかける作りになっているんでしょうか？これはノートPCの設計者に優しくない作りだなあ…。

まとめ

• USB Mass Storage（USB HDD、USB 2.0デバイス） -> 負荷高、速い
• USB Mass Storage（USB 2.0デバイス）を「デバイスの取り外し」で無効化 -> 使えないくせに、負荷高
• USB Mass Storage（USB DVD、USB 2.0デバイス） -> 負荷高
• USB Mass Storage（Flushメモリ、USB 2.0デバイス） -> 負荷高
• USB Mass Storage（USB 1.1デバイス） -> 負荷低、ただし遅い
• USBモデム、シリアルポート（NEC N902iS、USB 2.0デバイス？） -> 負荷低
• USBハブ（ARVEL、USB 2.0デバイス） -> 負荷低
• USBマウス（Logicool、USB 1.1デバイス） -> 負荷低
• USBゲームパッド（MS SideWinder、USB 1.1デバイス） -> 負荷低

まとめといた。

再いんすこ

目次: プロバイダ

大下邸のPCのセットアップをしました。NTT西日本のBフレッツ（光プレミアム）ではONU（光ファイバーつなぐやつ）以外に、CTUというルータのような装置を貸与されます。CTUはDHCPサーバとして動くので、大抵はケーブルを差せば動くようになっております。

無線LANも使いたかったので、無線LANルータのDHCPサーバ機能を殺して接続しておきました。PPPoEもDHCPもNATも何もかもOFFにしているため、無線LANルータではなく単なる有線 <-> 無線ブリッジになり下がってますけど。もったいない話だ。

CTU

CTUはNTT西日本独自の装置らしくて、地域IP網（IPv6）とユーザ側のネットワーク（多くはIPv4）を橋渡しする役目を果たしているようです。それ以外もごちゃごちゃやってるようですが、あまり詳しく書いてあるところがないですね…。

大きさも普通のルータ程度ですし、ルータ機能も良くできてると思いますが、設定するために一々NTTのサーバへアクセス（アドレスはhttps://ctu.fletsnet.com/, IPv4:210.247.16.1, IPv6:2001:d70:3:1::3:3）しなければならないのがめんどくさい…。

そして

うーむ、風邪引いたかもしれん。

淡路島とは関係ありません

大下さんちに遊びに行きました。阪急の淡路駅で初めて降りた気がします。

淡路駅は特急が止まります。ですが駅前には商店街があるだけで特に何があるっつーわけでもないです。駅や周辺地域の規模ではなくて、交通要所（千里線と京都線の乗り換え駅）だから止まるんだな。たぶん。

メモはすぐどっかに消える

ファミコンのアルテリオスというゲームを攻略した情報を一生懸命メモした（特にパスワード）のに、またやろうとしたら紙がない。こういう時って、やる気がなくなって諦めた頃に紙が出てくるもんですよね。

ここに書いてしまえば忘れないだろってことで書いておきます。まあ、ネット上の情報も「どう頑張っても探せなくなった」ら、消えたも同然なんですけどね。人の記憶と似てますねえ。

アルテリオスはうまくできていて、主人公の名前によって扉のパスワードが変わります。なので主人公の名前を「A」にしないと、以下のパスワードと違うパスワードになってしまうはずです（私には確認できませんが、カセットのロットなどその他の要因でも変わるかも）。

メイランド

特に何もない。レベルあげて武器買ったらさっさとリートランドへ進む。

リートランド、コロニー

ディーモスの右の扉のパスワード「1726」
小惑星でコルテス博士に会え、パスワードは「8A71」
（ウルムの言葉を習ってからもう一度）
ウルム: フローダのオルト博士に会え、パスワードは「B1B3」

リートランド、小惑星

（扉の向こう）コルテス博士: 4人の博士に会え、パスワード「7A7A」
（ウルムの言葉を習ってからもう一度）
左奥のウルム: 宮殿のパスワードは「27B1」

ユナイト、ダーフラの街

ディーモスの左の扉のパスワード「3740」

ユナイト、ニーツニーの街

オドラノエルでウルムの言葉を習える
弟: イクニバッドにいる姉さんに会え

ユナイト、イクニバッドの街

姉: ジェノ博士の部屋のパスワード「1B3A」、先に弟に会わないと何も言わない

ユナイト、オドラノエルの街

（扉の向こう）ジェノ博士: 4人の老人に会え、パスワードは「34C8」
老人: ウルムの言葉を教えてくれる。（この後、リートランドのウルムにもう一度会いに行くこと）

ディーモス、ノエロパの街

左には赤い石を置け、右には青い石を置け
リートランドにオルト博士を知っているウルムが居る（※リートランドのコロニーのこと）

ディーモス、エトラパノフの街

クラークス博士はレルチという街（ディーモスではなくてトゥメールカムスにある街）に いる、パスワードは「5A6A」

ディーモス、城内

（左の扉の向こう）レッドクリスタルがある、ヘビーシェルが守っている
（右の扉の向こう）ブルークリスタルがある、ヘビーシェルが守っている
（真ん中の扉）ヘビーシェルx 2が守っている
レティシア: 宮殿の扉のパスワードは「2112」、ヘビーシェルが守っている

トゥメールカムス、レルチの街

（扉の向こう）クラークス博士: 4人の老人に会え、パスワードは「14FD」

トゥメールカムス、フローダの街

（扉の向こう）宮殿の扉のパスワードは「109E」
オルト博士: 4人の老人に会え、パスワードは「CBDB」

トゥメールカムス、宮殿

（最初の扉）フローダの街で聞いたパスワード
（次の扉）リートランドの小惑星で聞いたパスワード
（左の扉）コルテスのパスワード、クリスタルをくれる
（右の扉）クラークスのパスワード、クリスタルをくれる
（右下の扉）オルトのパスワード、クリスタルをくれる
（左下の扉）ジェノのパスワード、クリスタルをくれる
（次の扉）レティシアのパスワード

トゥメールカムス、宮殿最深部

詳細忘れた。皿みたいなものにもらった4つのクリスタルを置けば先に進めるんだったかな？
最後のボス（サーベラー）がいるんではり倒す。メチャクチャ硬いです。

まあ、攻略の有無以前に単純に敵が強くてクリアできてないけどな…。ハイパーなんちゃら系がアホみたいにTUEEEEEEので、必ずボコボコにされる。

以下、おまけ

チートコードを調べてたときのメモです。知ってどうする情報とか、いじるとおかしくなる情報もあります。自己責任で。セーブデータが飛んでも知りません。

0026: 戦闘時の横位置、移動時の横位置も？
0702: 戦闘時の縦位置

0428: HP
0430: WE

6201: 敵の縦位置0x65くらいで自分の初期位置
6202: 敵の横位置0x80くらいで自分の初期位置

6230: 敵弾の判定？0にすると敵の弾が来ない

070e: 左の自弾の横位置
0716: 右の自弾の横位置

マップは変化しないが、出現する敵などに影響する。
0420: 現在居る惑星
00メイランド
01ユナイト
02リートランド
03ディーモス
04トゥメールカムス
05ディーモス
06トゥメールカムス
07（バグってリセットされる）

自身が居る位置は左上から右向きに1ずつ増えるようだ。
（画面左端）0 1 2 3（画面右端）
            4 5 6 7
            続く...
例えばメイランドだと、0x40足すと一個下に進める
0421: 自身が居る位置、上位8ビット
0422: 自身が居る位置、下位8ビット

マップを変えられるが、大抵変なところにはまる。
0423: 現在居るマップ
00メイランド、メイン迷路
01ユナイト、メイン迷路
02ユナイト、ダーフラの街
03ユナイト、ニーツニーの街
04ユナイト、イクニバッドの街
05ユナイト、オドラノエルの街
06リートランド、メイン迷路
07リートランド、小惑星
08リートランド、コロニー
09ディーモス、メイン迷路
0aディーモス、城内
0bディーモス、ノエロパの街
0cディーモス、エトラパノフの街
0dトゥメールカムス、メイン迷路
0eトゥメールカムス、宮殿
0fトゥメールカムス、宮殿最深部
10トゥメールカムス、レルチの街
11トゥメールカムス、フローダの街
12以降はバグる

(下位4ビットが種類、5ビット目が装備しているか否か、それ以外は無意味)
042c: 武器1
042d: 武器2
042e: 武器3
042f: 武器4

043e: ストップ個数
043f: デビルハンマー個数
0440: デストロイド個数
0446: アイテム装備状態(2: ストップ, 4: デビルハンマー, 8: デストロイド)
0447: 武器攻撃力合計値

実家にはまだアルテリオスのカセットがあるはずですが、肝心のファミコン本体が死んじゃったからなあ。もうエミュレータでしか画面が拝めないのかあ…。

何を補うの？

毎回話題がバラバラな日記ですみません。今日は補数の話です。

N進数の補数は2つあります。Nの補数と、N-1の補数です。10進数ならば10の補数と10-1の補数（9の補数ともいう）があります。

N進数における二つの補数

あるN進数xの Nの補数yとは、足すと桁上がりする最小の数値を指します。
10進数でいきますと、x = 123だとしたら、10の補数は足すと桁上がり（1,000になる）する最小の数値ですから877です。

要するにy = 1,000 - x = 1,000 - 123 = 877と計算します。4桁の数字なら10,000から引けばいいですし、5桁なら100,000から、n桁なら10^(n) から引いてください。

あるN進数xの N-1の補数zとは、足しても桁上がりしない最大の数値を指します。
また10進数を例に取ると、x = 123として、10-1の補数は足しても桁上がり（1,000）に達しない最大の数ですから、876です。足すと999になります。

これも要するにz = (1,000 - 1) - x = 999 - x = 876と計算します。特徴として、10の補数から1引いても得られますし、逆に10-1の補数に1を加えると10の補数になります（この性質は後ほど重要です）。

補数の活用方法

Nの補数は何が嬉しいかというと「負の数の表現として使えば、引き算が不要になる」という点です。

3桁の10進数500 - 300を計算したいとします。「引き算は知らないが3桁の足し算と10の補数を書いた表だけ持ってる」と仮定します。むちゃくちゃに見えますけど、後で意味が分かると思います。

引き算は知りませんので、まずは負の数を消しにかかります。負の数は絶対値の補数に置き換えて消します。表を見ると300の10の補数は700（計算で出すなら1,000 - 300）ですから、
500 - 300 = 500 + 700
こう置き換えます。すると足し算のみになって、計算できるようになります。
500 + 700 = 1,200
4桁目が出てきてしまいましたが、3桁の足し算しか知らんので4桁目は捨てます。さようなら〜。
1,200 => 200
この結果は500 - 300 = 200の結果と一致します。

不思議に見えますが、そもそも補数yの定義がy = 1,000 - xなので、x = 300で式を展開すると、
500 + (1,000 - 300) = 1,200 --(4桁目無視)--> 200
となるのは当たり前といわれれば当たり前の結果です。しつこいですが大事なポイントは「引き算が足し算に化ける」という点です。

2進数だと非常に嬉しい

とはいえ、10進数だと補数を計算するために結局引き算が必要で、ありがたみがありません。これはその他の記数法（図では3進数を例とした）でも同じです。

3進数と3の補数、3-1の補数

ところが2進数となると非常に嬉しい性質があります。以下の図を見てください。

2進数と2の補数、2-1の補数

2進数においては全桁を反転させる演算（Not演算）によって、容易に2-1の補数を得ることができ、そこに1加えれば2の補数を得ることができます。つまりNot演算さえあれば2の補数の導出に引き算は不要です。コンピュータだからこそできる技といえましょう。

この性質のためコンピュータに減算器は不要で（※）、加算器の前にNot演算と1加える回路をつけるだけで良いのです。回路が少なくなればコンピュータも安くなります。いやあ、補数って素晴らしいですね。

（※）コンピュータは前章の説明に出てきた「引き算は知らないが3桁の足し算と10の補数を書いた表だけ持ってる」の代表格です。コンピュータの場合2進数を扱うため10の補数ではなく2の補数です。
まとめると「一定桁（32桁、64桁など）の足し算と、2の補数しか知らない」変な奴と言えます。本当は意図的にそう作っていると言った方が正しいですけど…。

負の数を解釈

補数を負の数として扱うと良いこと（減算がなくなる）があるのは分かっていただけたかとおもいます。残る問題はどこからを負の数と見なすかです。卑近な例で言うとprintfしたときに、どこからマイナスなのよ？って話です。

前章まで話してきた計算の問題と関係ありそうに見えますが、実は全然関係ありません。ぶっちゃけた話、どこから負の数と見なしても構いません。以下の図をご覧下さい。

2進数から10進数へ解釈する一方法

この図にある解釈方法ですと2進数の101以上を負の数と見なします。

• 101未満の数を表示しなさいと言われたら、そのまま10進数に変換した値を印字します。
• 101以上の数を表示しなさいと言われたら、補数をとって10進数に変換した値と、マイナスの符号をともに印字します。

何？ずれてる？いやいや…。このような解釈でも使っている人がウンと言えばそれで良いんです。とはいったものの、この方式ではウンと言う人は少なそうです。この方式は欠点が多すぎます。

桁が増えたときに正負の境界をどう決めるかがあいまいであるがために、境界を見分ける処理が複雑になる可能性があります。プログラマや回路設計者に嫌われますね。それとやたら正の数ばかりが多くて、負の数を使いたい人にも嫌われます。

良い解釈方法はあるか

多くの方が見慣れたパターンは、最上位のビットが1なら負の数と見なす、以下のような解釈方法でしょう。

2進数から10進数へ解釈する効率的な方法

この解釈方法が採用されている理由は、効率的だからだと思われます。この解釈方法であれば、何桁になろうとも「最上位ビットの有無」という同じルールが適用できます。さらに正の数の範囲と負の数の範囲がほぼ同じ（負の数の範囲が1広いけど）で使いやすいのです。

Linuxのページテーブルが見当たらないときがある

目次: Linux

Linuxのページディレクトリを見ていると0xc000 0000以降（※）はページディレクトリエントリがあるのに、その先のページテーブルがありません。なぜこれで動くんでしょう？

調べてみると、なるほど、トリックがありました。

LinuxはCR4のPSEビット（Page Size Extension、ビット4）を1にして、4MB/4KBどちらのサイズでも使えるようにしています。

確かめ方は、右Alt + ScrLockを押してレジスタダンプすると簡単でしょうか？以下のようなメッセージが出るはずです。Pentium Proから導入されているはずですので、未対応というのはそうそうないかと…。

Pid: 0, comm:              swapper
EIP: 0060:[<c01019bd>] CPU: 0
EIP is at default_idle+0x31/0x59
 EFLAGS: 00010246    Not tainted  (2.6.18-6-486 #1)
EAX: 00000000 EBX: 00000800 ECX: c1101040 EDX: c030e000
ESI: 00099100 EDI: c0302800 EBP: 003a7007 DS: 007b ES: 007b
CR0: 8005003b CR2: c02bd7f4 CR3: 07175000 CR4: 00000690
 [<c0101a1c>] cpu_idle+0x37/0x4c
 [<c03105fa>] start_kernel+0x270/0x272

肝心なのはCR4レジスタの値です。CR4レジスタが0x0000 0690、2進数だと0110 1001 0000ですから、ビット4（ビット0から数えるので、右から5番目）のPSEビットが1になっていることが分かります。

（※）カーネルが使うリニアアドレス用のマッピングで、物理メモリ先頭896MB分を仮想アドレス0xc000 0000へマップしています。
物理: 0x0000 0000 .... 0x37ff ffff
リニア: 0xc000 0000 .... 0xf7ff ffff
というマッピングです。

二種類のページ

じゃあ4MBと4KBの区別はどこでやってるのさ？というと、ページディレクトリテーブルの要素である、ページディレクトリエントリでやっています。インテルのマニュアルによれば、ページディレクトリエントリの構成は以下のようになっています。

32ビットx86のページディレクトリエントリ

細かい説明は後述しますが、PSビット（Page Size、ビット7）が1になっていれば4MBのページを指し、0ならば4KBのページを使うことを意味します。

128MBの実メモリを割り当てた仮想マシン上でLinuxを起動して、適当なプロセスのページテーブルをダンプしてみると、768要素目から以下のようなページディレクトリエントリが見受けられます。

128MBしか実メモリがないので、768〜799番目（4MB x 32ページ）までしか値が埋まりません。余った800番目以降は別の用途に使われます。

  768: 0x000001e3, 0x004001e3, 0x008001e3, 0x00c001e3, 
  772: 0x010001e3, 0x014001e3, 0x018001e3, 0x01c001e3, 
  776: 0x020001e3, 0x024001e3, 0x028001e3, 0x02c001e3, 
  780: 0x030001e3, 0x034001e3, 0x038001e3, 0x03c001e3, 
  784: 0x040001e3, 0x044001e3, 0x048001e3, 0x04c001e3, 
  788: 0x050001e3, 0x054001e3, 0x058001e3, 0x05c001e3, 
  792: 0x060001e3, 0x064001e3, 0x068001e3, 0x06c001e3, 
  796: 0x070001e3, 0x074001e3, 0x078001e3, 0x07c001e3, 
  800: 0x00000000, 0x00000000, 0x07baf067, 0x00000000, 

772番目を例に取ると、0xc100 0000〜0xc13f ffffの4MB分のアドレスをマップしています。0x010001e3は2進数だと0001 0000 0000 0000 0001 1110 0011ですので、先ほどの図に当てはめてみると、

ビット0: P（存在）: 1

4KBページの時はページテーブルがロードされていることを表します。4MBページの場合はページが存在していることを表します。

ビット1: R/W（読み取り/書き込み）: 1

0は読み取り専用、1なら書き込み可能であることを表します。
CR0のWPビット（書き込み保護、ビット16）を1にすると、スーパバイザからユーザの書き込み禁止ページに書き込んだときに、ページフォルト例外が発生するようになります。コピーオンライト機能の実現に役立ちます。

• ページテーブルエントリEAが指すページAをコピーせよという命令に対し、実際はコピーせず、エントリEAを読み取り専用にし、さらに同じページを指すエントリEBを読み取り専用で作ります。
• 読み取り時
  • エントリEAの指すページAへの読み取りは今まで通りです。
  • エントリEBは書き込みがない限りページAと同じ内容なので、読み取りだけならばエントリの指すページを変更する必要はありません。
• 書き込み時
  • エントリEAの指すページAに書き込もうとすると、ページフォルト例外を発生させてページをコピーし、ページA' を作ります（書き込み時のコピー、コピーオンライト、COWとも）。
    以降はエントリEAは書き込み可能、指す先はページA' です（EA -> A', EB -> A）。
    そうしないとエントリEBが指すページAを使っている人が混乱します。エントリEBを使っている人から見ると、何もしていないのに（エントリEAの指すページAへの書き込み発生時に）勝手にページの内容が変わったように見えます。
  • 同様にエントリEBの指すページAに書き込もうとしても、ページフォルト例外が発生します。そのとき初めてページAの複製、ページBを作ります（コピーオンライト）。
    以降、エントリEBは書き込み可能、指す先はページBに変更されます。(EA -> A, EB -> B)
    ただし既にエントリEAがページAを指していないことが分かっているなら、コピー作業は無駄なのでしません。エントリEBはページAを指したままで、書き込み可能に変更されるだけです（EA -> A', EB -> A）。

ビット2: U/S（ユーザ/スーパバイザ）: 0

0はスーパバイザ用の領域を意味し、1はユーザ/スーパバイザ用の領域を意味します。

ビット3: PWT（ページライトスルー）: 0

0ならページへの書き込み時に、可能ならキャッシュのみを更新（ライトバック方式）します。1にするとキャッシュとメモリを同時に更新（ライトスルー方式）します。PCDが1のときは、そもそもキャッシュを使わないので無意味です。

• CR0のNWビット（非ライトバック、ビット29）が1だと、ライトスルー方式が採用されます。こちらが優先です。
• CR3のPWTビット（ページライトスルー、ビット3）が1だと、ライトスルー方式が採用されます。これはページディレクトリエントリだけのキャッシュ方式に適用されます。

しかしMTRRの設定とも関係します。ライトバックとライトスルーの設定がかち合ったときは、ライトスルーが優先されます。

ビット4: PCD（ページキャッシュ無効）: 0

0にするとページをキャッシュします。1にするとページをキャッシュしなくなります。I/Oメモリなど、キャッシュしても意味がない領域などに使うそうです。

• CR0のCDビット（キャッシュ無効、ビット30）が1だと、メモリに対するキャッシュ全てが無効になります。こちらが優先です。
• CR3のPCDビット（ページキャッシュ無効、ビット4）が1だと、ページ単位のキャッシュは無効になります。これはページディレクトリエントリだけのキャッシュ方式に適用されます。

キャッシュの設定はMTRRの設定とも関係します。ライトバックとライトスルーがかち合ったときは、ライトスルーが優先されます。

ビット5: A（アクセス）: 1

ページ番号が指しているページに読み込み、書き込みがあると1にセットされます。

ビット6: D（ダーティ）: 1

ページ番号が指しているページに書き込みがあると1にセットされます。

ビット7: PS（ページサイズ）: 1

0なら4KBページ、1なら4MBページを表します。ページディレクトリエントリ（一段目のテーブル）だけで有効です。
Linuxではページテーブル（二段目のテーブル）でアクセス権のないページを表すために、Pビットと合わせて使っています（当然CPUは無視します）。P:PS = 0:0なら存在しないページ、P:PS = 0:1ならアクセス権のないページを表します。
（4KBページ、ページテーブルエントリ（二段目のテーブル）のみ）Pentium Pro以降であれば、このビットはPATビットを表します。このビットが1であればPCDおよびPWTの2ビットで4つのメモリ属性（ライトバック、ライトスルー、MTRR優先のキャッシュ無効、MTRR上書きのキャッシュ無効）を表します。このビットが0であれば、従来と同じです。

ビット8: G（グローバル）: 1

0ならTLBフラッシュの時に消されます、1なら消されずにずっと残ります。
CR4のPGEビット（グローバルページ有効、ビット7）を1にしないと意味がありません。

ビット12: PAT（ページ属性テーブル）: 0

（4MBページのみ）0ならPAT機能を無効にして、1ならPAT機能を有効にします。

ビット31-22: ページ番号: 4（0x4）

先頭から16MB（4MB x 4個目）の位置にある4MB分の領域（0x0100 0000〜0x013f ffff）をマップすることを表します。

なぜ使い分けるのか

4MBのページングを使っているのはカーネル用のリニアアドレス（0xc000 0000〜）だけのようです。他のページディレクトリエントリにはPSビットが設定されていません。ページ番号の指す先には、もう一段ページテーブルがあり、その先にやっと4KBのページがあります。

理由ですが、インテルのマニュアルによると4MBと4KBのページは別のTLBに置かれるので、カーネルのように頻繁に使うコードやデータは4MBページに置いておくと、フラッシュされなくて良いよ、ってなことが書いてあります。また、ページサイズが大きければTLBミスも少ないよ、ってな解説もあります。恐らくそんな理由です。

あるプロセスのページディレクトリテーブル

絵にしてみるとこんな感じでしょうか。間違ってるかも…。

サイズはアドレスの範囲を意味するのではなくてテーブル自体の大きさのことです。ページディレクトリテーブル（一段目のテーブル）も、ページテーブル（二段目のテーブル）も 4バイトx 1024要素なので同じ4KBですよ、って言いたかっただけです。

メーデー！メーデー！

今日はメーデーです。そんなことより、エクスプローラのネットワークドライブへの無駄なリトライがすごくイライラする。

あるマシンAでWindowsのネットワークドライブを設定（宛先をBとする）して、接続先であるマシンBを落とすと、当然そのネットワークドライブは使えなくなります。

そこまでは良いのですが、エクスプローラってば使えなくなったネットワークドライブにアクセスしようとすると10秒近くフリーズしてしまいます。TCP SYN+ACK待ちにしては諦めが早すぎるので、NetBIOSでしょうか？

さらに嫌なことに、ネットワークドライブと全く関係ない操作（例：フォーカスを戻す）でも、毎回ネットワークドライブを確認してはフリーズします。もうイライラして仕方ないです。

マシンAを起動した時点でマシンBが死んでいると、ネットワークドライブは切断されている扱いになって、上記の現象は起きません。その後マシンBを起動してもネットワークドライブは切断された扱いのままです。

切断されている状態だとネットワークドライブ上のファイルへのアクセスが軒並み失敗しますので、すぐにわかるかと思います。

しかしエクスプローラからネットワークドライブを見てしまうと再接続処理が走るようで、以降は接続された扱いになります。こうなるともうダメで、マシンBを落とすと上記のフリーズしまくり状態に突入します。

Sambaだとダメ

ネットワークドライブの接続先が Sambaの場合はフリーズ現象が発生します。接続先のマシンを落とすと、ネットワークドライブのプロパティには「ネットワークドライブ：NTFS（または未フォーマットとも）」などと表示されます。

一方で Windows XPの共有ドライブの場合はフリーズ現象が起こりません。接続先のマシンを落とすと、ネットワークドライブのプロパティには「切断されたネットワークドライブ」と表示されます。

どうもSambaはサーバ終了時に、接続中のクライアントに何かを通知すべきなのに、全部すっ飛ばして終了するみたいです。オプションでなんとかならんかなあ…。

原因不明

しかし、いつまでも未練がましく覚えているクライアント側も大概にしてほしいものです。なんとかしてネットワークドライブの記憶を消せないか探ってみました。

まず、以下のコマンドでARPのキャッシュをクリアしました。
arp -d *
しかし症状は変わらず。

次にNetBIOSのホスト名 <-> IPアドレスのキャッシュをクリアしました。
nbtstat -R
やはり直りません。

エクスプローラが何か覚えているのかもと explorer.exeを強制終了させ再起動しましたが、依然として直りません。

残るはSystemプロセス（pid: 4）が覚えている可能性がありますが、確かめる方法がわからんなあ。

黄金ウィーク

うちの会社は5/1と5/2が休みなので、今年のゴールデンウィークは6連休（5/1〜5/6）です。さらに4/29の祝日（昭和の日）を有給休暇（4/30）で繋いで8連休にする人が多いのではないでしょうか。

中には4/28も有給休暇にして 11連休（4/26〜5/6）でイ゛ェアアアア！！という猛者も居ます。

一方、自分は特に予定もなく今日も出社しておりました。普段と違うのは、チームの人が何人か居ないのと、良く知らない仕事（隣のチームの仕事の手伝い）が回ってきたくらいか…。

ちなみに隣のチームは修羅場ってて、ゴールデンウィークなんかねえよｗｗみたいな話をしている方がいました。恐ろしい子…！