x86-64プロセッサのスタックを理解する

# はじめに
x86-64プロセッサにおけるスタックについて記載します。
使用したプロセッサ / OS / gcc / gdbは以下です。

```
Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz 64bit
Ubuntu14.04 64bit
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2
GNU gdb (Ubuntu 7.7-0ubuntu3) 7.7
```

プロセッサにはスタックを操作するためのレジスタや命令があります。
スタックは主に次のデータを格納するために使用します。

- リターンアドレス
- ベースポインタ
- 引数
- ローカル変数

# スタック
スタックとは後入れ先出し(LIFO;Last In First Out)方式のデータ保存領域です。
データをスタックに入れる操作を**push**といいます。
データをスタックから取り出す操作を**pop**といいます。
popで取り出すデータは最近pushしたデータです。これがLIFOといわれる理由です。

具体例を示します。最初スタックに61,27,67のデータがあるとします。
push 20するとスタックのトップにデータが追加されます。
popするとスタックのトップのデータが削除されて取り出されます。

![image](https://qiita-image-store.s3.amazonaws.com/0/84205/8ad4e8e0-e4df-b260-2bda-b633b4b86db2.png)

スタックという言葉には**干し草の山**という意味があります。
干し草の山(スタック)に干し草(データ)を積み上げたり(push)
干し草を取り出したり(pop)する光景をイメージすると覚えやすいのではないでしょうか。

# レジスタ
スタックに影響するレジスタを説明します。

- ss  : スタックセグメント
- rsp : スタックポインタ
- rbp : ベースポインタ

ssはスタックが配置されるメモリ領域を指定します。OSが設定します。

rspはスタックのトップのメモリアドレスです。
push命令でデクリメントされ、pop命令でインクリメントされます。

rbpは関数内においてスタック領域を扱う処理の基準となるメモリアドレスです。
関数の先頭で次の処理を行います。

1. 呼び出し元のrbpをスタックにpushする
2. rspをrbpに代入する

関数内部ではrbpを基準にしてスタック領域を扱います。

関数の最後で次の処理を行います。

1. rbpをrspに代入する(*)
2. popしてrbpを呼び出し元の値に戻す
3. retq命令で呼び出し元に戻る

上記処理を行うことで呼び出し元では関数呼び出し前後でrsp/rbpは変化しません。
1./2.はleaveq命令で一度に行えます。
(*)ローカル変数確保などでrspを更新した場合にrbpに戻すために行います。

# 命令
スタックに影響する命令を説明します。

## push
次の処理を行います。

1. rspをデクリメントします。
2. rspのメモリアドレスに値を書き込みます。

処理順番は1.→2.であることに注意してください。
スタックはメモリアドレスの値の小さい方向に延びていきます。

## pop
次の処理を行います。

1. rspのメモリアドレスから値を読み出します。
2. rspをインクリメントします。

処理順番は1.→2.であることに注意してください。

## callq
次の処理を行います。

1. rspをデクリメントします。
2. rspのメモリアドレスに**ripの次のアドレス**を書き込みます。
3. ripに呼び出し先のアドレスを設定します。

## retq
次の処理を行います。

1. rspのメモリアドレスから値を読み出してripに設定します。
2. rspをインクリメントします。

# 具体例
簡単なソースコードをgdbでdisassembleして
スタックの動作を確認します。

## ソースコード
main関数から足し算をするadd関数を呼び出します。

```c:test.c
int add(int a1, int a2, int a3, int a4, int a5, int a6,
	int a7, int a8, int a9, int a10)
{
	int c;
	c = a1+a2+a3+a4+a5+a6+a7+a8+a9+a10;
	return c;
}

int main(int argc, char *argv[])
{
	int ret = add(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    return ret;
}
```

## makefile
デバッグ情報あり(gオプション)、最適化なし(O0)でmakeします。
(*)半角space 4個をタブ文字に置き換えてください。

```:makefile
CFLAGS=-I. -g -O0 -Wall -Werror
INCS=#test.h
OBJS=test.o
LIBS=#-lpthread -lm
TARGET=test

%.o: %.c $(INCS)
	$(CC) $(CFLAGS) -c -o $@ $<

$(TARGET): $(OBJS)
	$(CC) $(CFLAGS) -o $@ $^ $(LIBS)

clean:
	rm -rf $(TARGET) *.o
```

## gdb
main関数の先頭の命令で処理を停止します。
命令のアドレスは直値指定しています。適宜変更してください。
disassembleコマンドでmain関数、add関数のアセンブリコードを出力します。

```
gdb ./test
b *0x40053d
r
disassemble
disassemble add
```

## アセンブリコード
main関数、add関数のアセンブリコードについて説明します。

それぞれの説明を行う前に関数呼び出しにお決まりの処理である
Function prologue / epilogueを説明します。
呼び出し元に影響を与えないで呼び出し先の処理を行うことを目的としたものです。

### Function prologue
関数の先頭にある次の2命令は**Function prologue**と呼ばれるお決まりの処理です。

**push   %rbp**
呼び出し元のrbpをスタックにpushします。

**mov    %rsp,%rbp**
rbpにrspをコピーします。
関数内ではrbpを基準メモリアドレスとします。

2命令後のスタック状態は次の通りです。

![image](https://qiita-image-store.s3.amazonaws.com/0/84205/22f9e034-0383-e092-56de-72b8a1460cbe.png)

**caller addr**は呼び出し元のアドレスです。
呼び出し元のcallq命令の次の命令のアドレスです。
caller addrは呼び出し元のcallq命令でスタックにpushされます。

### Function epilogue
関数の最後の2命令は**Function epilogue**と呼ばれるお決まりの処理です。

**leaveq**
leaveq命令は次の命令と同じです。

```
mov    %rbp,%rsp
pop    %rbp
```
rspにrbpをコピーして呼び出し元のrbpをスタックからpopします。
つまりFunction prologueの逆処理を行っています。

leaveq命令後のスタック状態は次の通りです。

![image](https://qiita-image-store.s3.amazonaws.com/0/84205/579a1aca-47ab-eaa5-9264-26da0f5ad21b.png)

**retq**
スタックからcaller addrをpopしてripに代入します。
これにより呼び出し元に戻ります。

### main
main関数の処理を説明します。
add関数にも言えることですが最適化されていないため不要な処理が多いです。

```
=> 0x000000000040053d <+0>:	push   %rbp
   0x000000000040053e <+1>:	mov    %rsp,%rbp
   0x0000000000400541 <+4>:	sub    $0x40,%rsp
   0x0000000000400545 <+8>:	mov    %edi,-0x14(%rbp)
   0x0000000000400548 <+11>:	mov    %rsi,-0x20(%rbp)
   0x000000000040054c <+15>:	movl   $0xa,0x18(%rsp)
   0x0000000000400554 <+23>:	movl   $0x9,0x10(%rsp)
   0x000000000040055c <+31>:	movl   $0x8,0x8(%rsp)
   0x0000000000400564 <+39>:	movl   $0x7,(%rsp)
   0x000000000040056b <+46>:	mov    $0x6,%r9d
   0x0000000000400571 <+52>:	mov    $0x5,%r8d
   0x0000000000400577 <+58>:	mov    $0x4,%ecx
   0x000000000040057c <+63>:	mov    $0x3,%edx
   0x0000000000400581 <+68>:	mov    $0x2,%esi
   0x0000000000400586 <+73>:	mov    $0x1,%edi
   0x000000000040058b <+78>:	callq  0x4004ed <add>
   0x0000000000400590 <+83>:	mov    %eax,-0x4(%rbp)
   0x0000000000400593 <+86>:	mov    -0x4(%rbp),%eax
   0x0000000000400596 <+89>:	leaveq 
   0x0000000000400597 <+90>:	retq   
```

次の命令でローカル変数の領域を確保しています。0x40バイト確保しています。
rspを減らしているだけです。main関数内ではrbpからrspの間のメモリを使用します。

```
sub    $0x40,%rsp
```
main関数の引数は呼び出し元で次のようにレジスタに設定されます。
argc -> edi
argv -> rsi

edi,rsiの値をローカル変数の領域にコピーします。

```
mov    %edi,-0x14(%rbp)
mov    %rsi,-0x20(%rbp)
```

第1から第6までの引数はedi,esi,edx,ecx,r8d,r9dにコピーします。
第7引数以降はスタックにコピーします。

```
movl   $0xa,0x18(%rsp)
movl   $0x9,0x10(%rsp)
movl   $0x8,0x8(%rsp)
movl   $0x7,(%rsp)
mov    $0x6,%r9d
mov    $0x5,%r8d
mov    $0x4,%ecx
mov    $0x3,%edx
mov    $0x2,%esi
mov    $0x1,%edi
```

この時点でのスタックの状態は次の通りです。

![image](https://qiita-image-store.s3.amazonaws.com/0/84205/f163afa9-4347-bbe0-9478-a1149f57b49c.png)

add関数をコールします

```
callq  0x4004ed <add>
```

eaxに戻り値が返ります。ローカル変数の領域にコピーします。

```
mov    %eax,-0x4(%rbp)
```

eaxにmain関数の戻り値を設定します。

```
mov    -0x4(%rbp),%eax
```

### add

```
   0x00000000004004ed <+0>:	push   %rbp
   0x00000000004004ee <+1>:	mov    %rsp,%rbp
   0x00000000004004f1 <+4>:	mov    %edi,-0x14(%rbp)
   0x00000000004004f4 <+7>:	mov    %esi,-0x18(%rbp)
   0x00000000004004f7 <+10>:	mov    %edx,-0x1c(%rbp)
   0x00000000004004fa <+13>:	mov    %ecx,-0x20(%rbp)
   0x00000000004004fd <+16>:	mov    %r8d,-0x24(%rbp)
   0x0000000000400501 <+20>:	mov    %r9d,-0x28(%rbp)
   0x0000000000400505 <+24>:	mov    -0x18(%rbp),%eax
   0x0000000000400508 <+27>:	mov    -0x14(%rbp),%edx
   0x000000000040050b <+30>:	add    %eax,%edx
   0x000000000040050d <+32>:	mov    -0x1c(%rbp),%eax
   0x0000000000400510 <+35>:	add    %eax,%edx
   0x0000000000400512 <+37>:	mov    -0x20(%rbp),%eax
   0x0000000000400515 <+40>:	add    %eax,%edx
   0x0000000000400517 <+42>:	mov    -0x24(%rbp),%eax
   0x000000000040051a <+45>:	add    %eax,%edx
   0x000000000040051c <+47>:	mov    -0x28(%rbp),%eax
   0x000000000040051f <+50>:	add    %eax,%edx
   0x0000000000400521 <+52>:	mov    0x10(%rbp),%eax
   0x0000000000400524 <+55>:	add    %eax,%edx
   0x0000000000400526 <+57>:	mov    0x18(%rbp),%eax
   0x0000000000400529 <+60>:	add    %eax,%edx
   0x000000000040052b <+62>:	mov    0x20(%rbp),%eax
   0x000000000040052e <+65>:	add    %eax,%edx
   0x0000000000400530 <+67>:	mov    0x28(%rbp),%eax
   0x0000000000400533 <+70>:	add    %edx,%eax
   0x0000000000400535 <+72>:	mov    %eax,-0x4(%rbp)
   0x0000000000400538 <+75>:	mov    -0x4(%rbp),%eax
   0x000000000040053b <+78>:	pop    %rbp
   0x000000000040053c <+79>:	retq   
```

Function prologue後のスタックの状態は次の通りです。

![image](https://qiita-image-store.s3.amazonaws.com/0/84205/b2d7868b-2fe5-22b7-5985-a26ba5e17210.png)

第1から第6までの引数をスタックにコピーします

```
mov    %edi,-0x14(%rbp)
mov    %esi,-0x18(%rbp)
mov    %edx,-0x1c(%rbp)
mov    %ecx,-0x20(%rbp)
mov    %r8d,-0x24(%rbp)
mov    %r9d,-0x28(%rbp)
```
引数をレジスタeaxに読込んでedxに対して足し込んでいきます。
最後はeaxに合計値を入れます。

```
mov    -0x18(%rbp),%eax
mov    -0x14(%rbp),%edx
add    %eax,%edx
mov    -0x1c(%rbp),%eax
add    %eax,%edx
mov    -0x20(%rbp),%eax
add    %eax,%edx
mov    -0x24(%rbp),%eax
add    %eax,%edx
mov    -0x28(%rbp),%eax
add    %eax,%edx
mov    0x10(%rbp),%eax
add    %eax,%edx
mov    0x18(%rbp),%eax
add    %eax,%edx
mov    0x20(%rbp),%eax
add    %eax,%edx
mov    0x28(%rbp),%eax
add    %edx,%eax
```

第7以降の引数はスタック上に置かれているため、
rbpに対してプラスのoffsetで参照していることに注意してください。

```
mov    0x10(%rbp),%eax
add    %eax,%edx
mov    0x18(%rbp),%eax
add    %eax,%edx
mov    0x20(%rbp),%eax
add    %eax,%edx
mov    0x28(%rbp),%eax
```

結果をスタックにコピーします。

```
mov    %eax,-0x4(%rbp)
```

結果をeaxにコピーします。eaxは戻り値です。

```
mov    -0x4(%rbp),%eax
```

この時点のスタックの状態は次の通りです。

![image](https://qiita-image-store.s3.amazonaws.com/0/84205/c4764ff0-4a69-bdbf-3cc0-150a419394ec.png)

呼び出し元のrbpをスタックからpopします。
leaveqではありませんがrspが変化していないためpopだけでOKです。

```
pop    %rbp
```

# 参照

[x86 calling conventions](https://en.wikipedia.org/wiki/X86_calling_conventions)
[Function_prologue](https://en.wikipedia.org/wiki/Function_prologue)