まっつーのブログ

本の感想や振り返りなど雑多に書いてます

第3章 プログラムのマシン･レベルの表現

CS:APP コンピュータ･システム

3章について
この章では、コンパイラによって生成されるマシン･コードの読み方や、マシン語レベルでの基本的な命令パターンについて学ぶことができます。
プログラムがマシン上でどのように表現されるかを理解することで、より良いコードが書けるそうです。
以下まとめです。


高水準言語と低水準言語

  • 高水準言語 : 人間寄りの言語、特定のマシンに依存しない (C, Java, Python など普段目にするものは大概こっち)

  • 低水準言語 : マシン寄りの言語 、特定のマシンに依存する(アセンブリ, 機械語)

高水準言語は、最適化コンパイラを用いるだけで、効率的に書かれたアセンブリ･コードと同等の効率が得られる場合がある。

また、マシン･コードを学ぶことで、コンパイラの最適化を理解し、潜在的なコードの非効率性を解析できる。

近年だと、アセンブリを書く能力より、読んで理解できることの方が重要になってきているという。


マシン･レベル･コード

フォーマットと振る舞いは 命令セット･アーキテクチャ(ISA)により定義されている。


プログラム･カウンタ(PC) : 次に実行すべき命令メモリ中のアドレスを示す。

整数レジスタ･ファイル : アドレス(Cのポインタ)や整数データを保持する。

条件コード・レジスタ : 算術または論理演算命令の状態を保持する。

ディスアセンブラ : マシン･コードからアセンブリに近いフォーマットを生成する。


CPU

CPUは64ビットの数値を格納する16本の汎用レジスタ･セットを持つ。

レジスタは16ビット、32ビット、64ビットと拡大されている。

符号拡張

符号付の数値を表現するビット列が格納領域のビット幅より短い場合に、隙間を適切に埋めること。

-10を2の補数表現で表す。
8ビット
11110110
16ビットに符号拡張
11111111 11110110 = -10
符号拡張しない場合
00000000 11110110 = 246(値が変わってしまう)


データ移動

命令の中で最も多く使用されるのは、データを別のところへコピーする命令である。

#include <stdio.h>

// xpをyに書き換えてから、元のxpの値を返す
long exchange(long *xp, long y)
{
    long x = *xp;
    *xp = y;
    return x;
}

int main()
{
    long xp = 100;
    long y = 42;
    long ret = exchange(&xp, y);
    // xp=42, y=42, ret=100
    printf("xp=%ld, y=%ld, ret=%ld\n", xp, y, ret);
    return 0;
}

mov命令を使ってデータ移動を行う。

_exchange:
movq    (%rdi), %rax   ## xをメモリから読み出し、その値を%raxへ格納する。
movq    %rsi, (%rdi)   ## yを%rdiにあるxpへ書き込む
ret    ##関数がコールされたポイントへ戻る命令


ジャンプ命令

その名の通り、別の処理にジャンプさせることができる。

主に if-else などの条件分岐に使用される。

つまりアセンブリでは、シンプルな条件分岐も goto 文のように書かれているらしい。


  • 直接ジャンプ: ジャンプターゲットが命令の一部としてエンコードされている。

  • 間接ジャンプ: ジャンプターゲットがレジスタかメモリから読み込まれる。

  • 条件付きジャンプ: 他に条件コードに応じてジャンプを実行する。(直接ジャンプのみ)

直接ジャンプ
jmp .L1    ##　.L1をラベルとして扱う。

間接ジャンプ
jmp *%rax   ##　%raxレジスタの値がジャンプターゲット。
jmp *(%rax) ##　%raxレジスタの値をアドレスとしてジャンプターゲットをメモリから読み込む。


データ転送と制御転送

  • データ転送 : 代入などの処理

  • 制御転送 : if-else文などの条件分岐


データ転送は制御転送よりも効率的

制御転送の場合、評価されるまで次の命令が分からないため次の命令を予測をする。

しかし、予測をミスした場合、命令をやり直す必要があるためコストがかかる。

そのため、データ転送のほうが効率的となる。


例外として、そもそも代入にコストがかかる場合は、制御転送のほうが効率的。

また、ポインタのデリファレンスなどが行われるリスクがあるからため使えない場合もある。

使用ケースは限られてるけど、プロセッサよっては効率的に処理できるよってことですね。


プロシージャ

関数やメソッド、ルーチンみたいなもの。

プロシージャ呼び出しにかかるコストを最小化するために、3つメカニズムを利用している。

  1. 呼び出す際、PCはコードの開始アドレスを指すようにセットする。
  2. レジスタを介してデータを受け渡す。
  3. 実行開始時にローカル変数のための領域を割り当て、戻る際にその領域を開放する。

この仕組みのおかげで、再帰的に呼び出す場合でも、それぞれのローカル変数が干渉しないってことみたいですね。


レジスタ

呼び出し先退避レジスタ : レジスタ値の上書きできない。

呼び出し元退避レジスタ : レジスタ値の上書きできる。(関数でポインタを引数として渡す場合など)


ポインタ演算

配列のアクセス添字表現は、ポインタにも適用できる。

つまりA[i] という配列参照は、*(A+i),*(i+A),i[A]と等価である。

#include <stdio.h>

int main()
{
    char *a = "hello";

    printf("%c, %c, %c, %c\n", a[1], *(a+1), *(1+a), 1[a]);
    return 0;
}

$ ./a.out 
e e e e

1[a]みたいにアクセスする機会はなさそうですが、雑学として知っていると面白いかもしれませんね。


配列の格納
  • メモリ上で配列要素は、行優先順で格納される。
行    要素     アドレス
A[0] A[0][0]   XA
     A[0][1]   XA + 4
A[1] A[1][0]   XA + 8
     A[1][1]   XA + 12


このメモリの並びを知っていると非効率なコードを回避できる。

for(i = 0; i < 1000; i++){
    for(j = 0; j < 1000; j++){
       res1 += a1[i][j] + a2[i][j]; // 連続したアドレスにアクセスするため速い
       res2 += a1[j][i] + a2[j][i]; // アクセスが毎回バラバラなため遅い
    }
}


構造体と共用体

構造体 : 配列の実装に似ており、要素はメモリ上の連続領域に格納される。

共用体: 複数の要素がすべてが同じブロックに対応する。

struct S3 {
    char   c;
    int    i[2];
    double v;
};
union U3 {
    char   c;
    int    i[2];
    double v;
};

型  c  i  v　　　サイズ
S3  0  4 　16  24
U3  0  0  0   8 / / 総サイズは要素の最大サイズとなる(この場合double(8バイト))

共用体は使い方によっては、メモリ使用量を抑えることができる。

またすべてが同じブロックに対応するため、どのメンバを指すかによって、キャストにも使える。


アラインメント制約

オブジェクトのアドレスは、ある定数 K (2, 4, 8のいずれか)の整数倍の値となる。

Intelは性能改善のため、データをメモリ上でアラインメントすることを推奨しているみたい。


バッファ･オーバーフロー

スタック上に格納された文字配列に対し、サイズを超えた文字列を格納してしまうと起きる。

他の保持情報が改ざんされるので、システムのセキュリティ攻撃使われることもある。


セキュリティ対策

スタック･ランダマイゼーション : プログラムの実行ごとにスタックの場所を変化させる。

スタック･プロテクト : カナリア値とよばれる値をスタック･フレーム内に挿入し、プログラム実行時後に変更されている場合は、エラーを発生させる。

セキュリティ画一性 : 古いマシンだと、スタックの場所がほぼ一定のため、1台のスタック･アドレスが特定されると、多くのマシンが攻撃可能となってしまうこと。


感想

これまでアセンブリに触れていなかったので、新しい発見ばかりで面白かったです。
さっくりとまとめていますが、実際の内容はこの100倍くらい学ぶことがあると思います。
各命令セットの詳細やC言語で書かれたコードに対応するアセンブリ･コードなど、とても興味深い内容でした。
練習問題もたくさんあり、まだ解いていないものもあるので、引き続き勉強してみようと思います。