CSAPP 第三章 プログラムのマシン・レベルの表現
32ビットマシンから64ビットマシンになって使えるメモリの数が
2^32 = 4,294,967,296 = 4gb
↓
2^64 = 18,446,744,073,709,551,616 = 18 exa byte
になった。指数関数なので圧倒的スケール力で倍増されていることがわかった
x86-64とはx86アーキテクチャを64bitように拡張した命令セットアーキテクチャ
命令セットとは
コンピュータのハードウェアに対して命令を伝えるための言葉の語彙
"x86"という用語は、命令セットアーキテクチャとそれを実装したマイクロプロセッサの両方の意味がある
x86
なぜx86なのか
intelの8086アーキテクチャが元になっている
↓
なぜ8086なのか
最初のintelのcpuが4004だった。それは4bit-wideのALUが4chipセットされているCPUだったから。
そこから8bitのcpuが登場したため8008が登場する。
その後8008を大幅に改良した8080が登場する(8008の改良という意味で8を反転させた。)
ちなみに8008の次は8080である。
次に8085が発売、これは5V単一電源の5から由来している。
そこから8086に行き着くわけだが、intelは16bitのマイクロプロセッサを開発していた。4bitからの傾向としては160016となるのが通例だが、CPUの型番か4桁でしか表すことができない。
そのため、8085の後継機である + 16bitのマイクロプロセッサという理由で8086
と命名された。
コンパイルしたアセンブリコードをみるときは-S
オプションとする
.oファイルの中身は機械語で表される
その機械語を逆アセンブリ、つまりアセンブリ言語に翻訳するときはOBJDUMPコマンドを使用する
例objdump -d mstore.o
x86アーキテクチャは元々16bit用のISAとして扱われていたので16bitデータ型のことを「ワード」と呼ぶ。
それに際して32bitのデータ型を「ダブルワード」、64bitを「クワドワード」と呼ぶ。
アセンブリ内での表し方
Cの宣言 | Intelデータ型 | アセンブリでの接尾辞 | サイズ |
---|---|---|---|
char | バイト | b | 1 |
short | ワード | w | 2 |
int | ダブルワード | l | 4 |
long | クワドワード | q | 8 |
char * | クワドワード | q | 8 |
ちなみにダブルワードがlなのはlong(長い)という意味
mov : データを移動する命令
movb, movw, movl, movqなどのワードサイズ違う命令が存在する。
movにおいてどちらのオペランドにもメモリの参照を指定することはできない。
あるメモリから他のメモリの位置に値をコピーするのは、2命令が必要となる
movz : 0拡張を伴うデータ移動命令(move zero)
movs : 符号拡張を伴うデータ移動命令(move sign extend)
※movlは特性として必ず0拡張を行う。
つまり、movl %rax などの8byte用の空間にlong wordを移動する命令を実行するときに、raxに入る値の上位4byteは必ず0になる。
もし符号拡張を行いたい場合はmovslq命令を使用する。
またcltq = movslq %eax %rax
と同一であり、エイリアス的な役割を果たす
おそらくconvert long word to quad wordの略
movはdestの方にサイズを合わせる必要がある。
つまり、mov (%rax) %dx
ならばmov→movwとするべき
mov命令が実行可能な5つの形式について
movは両引数にメモリ参照などを指定できないことから、5つの決まった可能な形式が存在する。
movl $0x4050, %eax Immediate--Register 4bytes
movw %bp, %sp Register--Register 2bytes
movb (%rdi,%rcx), %al Memory--Register 1byte
movb $-17, (%rsp) Immediate--Memory 1byte
movq %rax, -12(%rbp) Register--Memory 8bytes
型が違うときのアセンブリの挙動
符号拡張、ゼロ拡張を行う
この辺の細かい仕様についてはコンパイラとCPUの関係でだいぶ変換方式が変わってくる。
なので細かいところがこうなっていると覚えるのではなくざっくりこういう感じなのか、とわかるくらいの理解でちょうどよい。
実際に使う部分はおそらく、アセンブリを読む力があれば一旦は大丈夫。
pushq
データをスタック領域にプッシュ(確保)する命令
popq
データをスタック領域からポップ(開放)する命令
%rspはスタックポインタを表すレジスタである。スタックポインタのトップの要素のアドレスを保持する。
x86ではスタック領域は大きいアドレスから小さいアドレスに確保していく。
なのでpushすることにより、%rspアドレスをデクリメント
popすることでアドレスを、%rspインクリメントすることによりスタック領域を管理している。
pushする際には、最初に確保するアドレスをrspから引いてから値をmovする
subq $8 %rsp
movq %rbp, (%rsp)
逆にpopする場合は、最初に値をmovしてからrspを足す
movq (%rsp), %rax
addq $8, %rsp
これにより他の使用済みメモリ領域を干渉しないようにする
lea vs mov
movはメモリ参照を行うが、leaはメモリ参照を行わない。
ex)
rax 0x10
rdx 0x20
----------
0x10 0x5
0x20 0xA
50 0xff
51 0xee
上記のような配置を取っている場合、計算結果が異なる。
mov (%rax, %rdx,2), %rcx : %rcx -> 0xff
lea (%rax, %rdx,2), %rcx : %rcx -> 50
これはmovがメモリ参照を自動で行ってしまうからである。
movのsrcの計算結果は50。
movは参照を行うので、50のメモリを参照することで値0xff
を取ってくる。
逆にleaはメモリ参照を行わない。
srcの計算結果は同様に50。ただmovのようにそのメモリが指している値まで見に行くことはない。
そのためrcxに格納される値は50となる。
これがわかりやすい
leaはメモリ参照を行わないという性質から、レジスタの演算に用いられる。
movでこれをやってしまうとレジスタに格納されている値を値とみなさずメモリアドレスと見てしまう場合があり、演算結果が狂ってしまう場合がある。
0x100 0xFF
0x108 0xAB
0x110 0x13
0x118 0x11
%rax 0x100
%rcx 0x1
%rdx 0x3
このようなメモリ/レジスタの値が存在した場合の各計算の答えは以下のようになる。
命令 | dest | 値 |
---|---|---|
addq %rcx, (%rax) | 0x100 | 0x100 |
subq %rdx, 8(%rax) | 0x108 | 0xA8 |
imulq $16, (%rax, %rdx, 8) | 0x118 | 0x110 |
incq 16(%rax) | 0x110 | 0x14 |
ポイントは第2引数の計算結果は全てどのdestで計算されるかということのみに
フォーカスを当てているということ。
xorは値に0をセットするときにつかえる。
なぜならxがいかなる数値であってもx^x = 0
が成立するからである。
他の文法でこれを実現するのはmov $0 %rax
などが挙げられる
64bit同士の乗算/除算は128bitまで計算結果が及ぶ事がある。
そのため、x86では64bit同士の乗算/除算を行う際には、%rdi, %raxの2つの64bit容量のメモリを使用することでこれを成立させる。
計算結果が64bitをこえない場合はcqtoなどを使って、ゼロ埋め or Sign Extended埋めをする
条件コード
整数レジスタに加えてCPUは1ビットの条件コード・レジスタのセットを管理する。
CF: Carry flag
符号なし演算でオーバフローを検出したときに使用する
ZF: ゼロフラグ
直近の演算で0を生成
SF: 符号フラグ
直近の演算が負の値を生成
OF: 2の補数の値がオーバフローをおこした。
マシン命令には同じ条件を満たすものが存在する。
例えばsetg(set greater)とsetnle(set not less or equal)は同じ条件なので、同じマシン命令となる。
その場合どちらの命令を使用するかはコンパイラなどが決定する
算術論理演算の方法は、例えばaとbでの比較をしているとする。
この場合、t = a - b
とすることでtの値を定義する。
これにより、tに何かしらの条件フラグを与える。
例えばseteset when equal
を確認したい場合は、t = a - b でtが0つまりZFフラグが立っていることを確認すればよい。
ジャンプ命令
命令は記載されている順番に従って実行することが出来るが、
ジャンプ命令はプログラムの全く新しい場所に移動することが出来る。
ジャンプ先は一般的にラベルで指定される
ジャンプは関節演算が使用可能なので、メモリから値を読み取る事もできる。
条件付きmove
cmovgeのようなcmp * movを組み合わせた命令が存在する。
この命令が存在する理由としては速度向上が挙げられる。
最新のプロセッサでは、パイプラインなどを用いて処理を並行して高速に動かすようなアルゴリズムが存在する。
並行に動かすための条件として、並行動かす全ての箇所の前提条件が揃っているかどうかが挙げられる。
例えばあるif文の中身などを並行処理したい場合、if文内での命令を事前に決定できた方が他の処理を待たずに実行することが出来る。
つまり変数定義などを事前にしておくことで、プロセッサが並行に動けるようなプログラムの最適化が可能となる。
このことから、ジャンプ命令による条件分岐によって処理系が変わる処理よりも、事前に条件分岐がどちらのパターンであっても事前に処理を記載しておくほうが、現代のプロセッサでは処理が早い場合が多分にある。
このことからcmovは使用される。cmovはシンプルな条件分岐命令であり事前に作成しておいた変数を戻り値などに格納するために使われる。
プロシージャ
関数、サブルーチンなどの総称
プロシージャのメカニズム
-
制御の受け渡し
Qを呼び出すときに、PCを呼び出し元→Qに移動。
Qから戻る際にPCをQ→呼び出し元に移動 -
データの受け渡し
引数/戻り値によって呼び出し元と呼び出し先でデータを共有する -
メモリの割当と開放
Qは実行開始時にローカル変数を割り当てて、終了と同時にそれを開放する
スタック(stack) とは、C言語プログラムがプログラムの制御に必要な情報や関数のローカル変数を置くメモリ領域です。
スタックフレーム (stack frame)とは、C言語のプログラムが関数を呼び出すときにスタックにデータを積みますが、そのデータをまとめた呼び方です。
x86ではプロシージャがメモリを必要とする際には、まずレジスタに領域を確保する。
レジスタに収まりきらない場合は、スタックに領域を確保する。
プロシージャの呼び出し
LIFOによってスタック領域にデータが積み上がっていく
callによって確保した領域の先頭アドレスに値を渡し
retによって呼び出し元のアドレスを返す
データの受け渡し
スタック領域のアドレスだけではなく、プロシージャは引数/戻り値の制御も受付なければならない。
そのための領域はレジスタに格納される。
x86では最大6つまでの整数型引数をレジスタを介して受け渡す事ができる
ただ以下のようにもある
引数は、レジスタで渡すこともできますが、今回はスタックを使って渡すことにします。 x86はレジスタが少ないのでスタックで引数をやりとりするのが普通だからです。
https://vanya.jp.net/os/x86call/
引数の格納についてはまずレジスタに格納%rdi ~ %rsi
その次に、rsp レジスタポインタから + 8(ここはプロシージャのスタックフレームに依存する気がする)
long swap_add(long *xp, long *yp)
{
long x = *xp;
long y = *yp;
*xp = y;
*yp = x;
return x + y;
}
long caller()
{
long arg1 = 534;
long arg2 = 1057;
long sum = swap_add(&arg1, &arg2);
long diff = arg1 - arg2;
return sum * diff;
}
このコードにおけるcallerのアセンブリは以下のようになる
_caller: ## @caller
## %bb.0:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movq $534, -16(%rbp) ## imm = 0x216
movq $1057, -8(%rbp) ## imm = 0x421
leaq -16(%rbp), %rdi
leaq -8(%rbp), %rsi
callq _swap_add
movq -16(%rbp), %rcx
subq -8(%rbp), %rcx
imulq %rcx, %rax
addq $16, %rsp
popq %rbp
retq
構造体における値の参照方法
配列のときと特に変わらず先頭アドレス + (型のサイズ) * 位置
で表現出来る
struct rec{
char i;
long j;
int a[k]
int *p
}
上記のような構造体が存在するときにa[10]番目の値にアクセスしたいときは
recのアドレスをrとすると以下でアクセスすることが可能
a[4] = *(r + 1(iの型のサイズ) + 8(jの型のサイズ) + 4(aの型のサイズ) * 10(要素数))
アセンブリでは上のような計算式を用いてleaq命令で特定の値にアクセスする
testq = %rdi , %rdi
jne
この表現はrdi != NULL
を表す
CMP命令とTEST命令の違い
元になる命令が異なる
cmp S1, S2 → S2 - S1
test S1, S2 → S1 & S2
そのためtestは論理積を取る。
結果が0の場合はZFを立て、0以外の場合は1を立てる
共用体
単一のオブジェクトを複数の型として参照できるようになる。
構造体では複数の要素がメモリ上の別々のブロックに対応するのに対して、共用体では全てが同じブロックに対応する。
struct S3 {
char c;
int i[2];
double v;
}
union U3 {
char c;
int i[2];
double v;
}
上記の様な宣言があったときに、S3/U3の総サイズと各要素のオフセットは次の通りになる。
(構造体のオフセットがバイト数と異なるのはアライメントによるもの)
型 | c | i | v | サイズ |
---|---|---|---|---|
S3 | 0 | 4 | 16 | 24 |
U3 | 0 | 0 | 0 | 8 |
共用体を使うメリットとしてはメモリの大きさを小さく出来るという点
アライメントがないアセンブリコードはx86では問題なく動作するが、Intel AMD系プロセッサにおけるマルチメディア操作を実現するSSE命令のいくつかは、アライメントがないと正しく動作しない場合がある。
よって全てのコンパイラは以下を保証しなければならない。
- malloc, calloc, realloc, allocaによって生成された全てのブロックの開始アドレスは16の倍数でなくてはならない
- 関数のスタックフレームは16バイト境界アライメントを満たす
ポインタの特徴
-
ポインタは全て対応する型を持つ
ポインタ自体はアドレスを指しているのにも関わらず、対応する型が存在する。
ただしvoid *
は汎用ポインタを指す。
アセンブリではポインタの型は存在しないので、C言語側が人がわかりやすいように提供している機能だと言える -
各ポインタは一つの値を持つ。
ポインタが何も指していない場合はNULL(0)という特殊な値を用いる -
ポインタ型に対するキャストは型を変換するが値は変更しない
char *a = '1';
int * b = a
上記のような暗黙的な型変換をしても値は変更されない。
面白い仕様が
char *pにおいて、
(int *) p + 7 → p+28となり
(int *) (p + 7) → p + 7となる
これは優先順位はキャスト→加算
なので
前者はキャストされてからポインタが加算されている。