スタックについて勉強したのでまとめてみた

これまでちゃんと理解してこなかった低レイヤーをちゃんと理解したいと思い、まずはスタックを勉強しましたのでまとめておこうと思います。

## まずプロセスのメモリのレイアウトはどうなっているのか
スタックとはそれぞれのプロセスに割り当てられているメモリ領域の中の一部のメモリ領域のことです。

プロセスのメモリはざっくりこんな感じのレイアウトになります。
![スクリーンショット 2022-12-12 5.34.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2982597/b58bb373-18e2-c8bb-ad1d-87cb8a9e7b2d.png)
(100, 0はメモリのアドレスです。上に行くほど大きく、下に行くほど小さくなるという図です。)

一番下から簡単に説明すると (他セクションの名称と表記を合わせるためにここではstackと表記しています）
`code (text)` : ここはtextセクションと呼ばれる領域で、ここには私たちが実際に高級言語で書いたコードがコンパイルされここに保持されます。
`initialized data` : ここはdataセクションと呼ばれる領域で、ここには初期値を持つデータが保持されます。
`uninitialized data` : ここはbssセクションと呼ばれる領域で、ここには初期値を持たないデータが保持されます。
`heap` : ここはstackと並んでよく知られているヒープ領域です。
`stack` : そして一番上にstackがあります。

## スタックの特徴
スタックとは「積み上がる」ということを意味しています。その名の通りスタックは上に積み上がっていくという特徴があります。
そしてさらに `FILO (First In Last Out)` であるという特徴もあります。つまりスタックが上に積み上がっていき、積み上がったスタックの上に積み上がっている方が先に消費されていくということです。
積み上がっていくスタックは、大きいアドレスから順番に割り当てられていきます。順番に割り当てられていき、図で線を引いた位置までスタックは積み上がっていきます。
ちなみにこの線、スタックの大きさの上限は設定可能な値となります。
そしてこのスタックを割り当てられるサイズを超えて割り当てを行おうとしてしまうと、用語として知っている方も多いかと思いますが、スタックオーバーフローが発生します。

## スタックとは何に使うのか
スタックは以下の4つのものを保持しておくために使います。
1. パラメータ
2. リターンアドレス (どこに戻ればいいのかを指しているアドレス)
3. ベースポインタ (後ほど説明します)
4. ローカル変数

## 実際にどんな感じで割り当てられていくのか
例えば次のようなコードを書いたとします。
```C:main.c
int fn3(int x, int y)
{
    int fn3_x = 109;
    int fn3_y = 110;
    return x + y + fn3_x + fn3_y;
}

int fn2(int x, int y)
{
    int fn2_x = 106;
    int fn2_y = fn3(107, 108);
    return x + y + fn2_x + fn2_y;
}

int fn1(int x, int y)
{
    int fn1_x = 103;
    int fn1_y = fn2(104, 105);
    return x + y + fn1_x + fn1_y;
}

int main()
{
    int x = 100;
    int y = fn1(101, 102);
    return 0;
}
```

```
100: main ローカル変数 x
99: main ローカル変数 y
98: fn1 引数 x
97: fn1 引数 y
96: main へのリターンアドレス
95: main のベースポインタ
94: fn1 ローカル変数 fn1_x 
93: fn1 ローカル変数 fn1_y
92: fn2 引数 x
91: fn2 引数 y
90: fn1 へのリターンアドレス
89: fn1 のベースポインタ
88: fn2　ローカル変数 fn2_x
87: fn2 ローカル変数 fn2_y
86: fn3 引数 x
85: fn3 引数 y
84: fn2 へのリターンアドレス
83: fn2 のベースポインタ
82: fn3 ローカル変数 fn3_x
81: fn3 ローカル変数 fn3_y
```
(左の数字はメモリのアドレスと考えてください)

こんな感じでしょうか。
この例だと、 `100-98` , `98-92` , `92-86` , `86-80` がそれぞれ関数の呼び出しに対応しています。このそれぞれの呼び出しに対応しているスタックのメモリの範囲を `スタックフレーム` と呼びます。
つまり `100-98` が `main` のスタックフレーム、 `98-92` が `fn1` のスタックフレームという感じです。
ここで2つ新たに用語が出てきます。
1つ目は、 `スタックポインタ` です。これはスタックの一番上のアドレスを指します。これは参照する時点の常にスタックの一番上です。
そして2つ目は、先ほど上で `ベースポインタ` という用語を挙げましたが、その用語の説明です。ベースポインタとは関数内で次の関数を呼び出した時点でのスタックポインタを指します。つまりその時点での一番上のアドレスを指します。上の例でも関数を呼び出し、リターンアドレスをスタックに保持すると同時に、ベースポインタも保持するようにしていました。
このベースポインタは何に使うのかというと、ローカル変数や引数への参照に使います。基本的には４バイトでデータを扱うため、ベースポインタから４バイトを引いたり足したりしたアドレスを参照して、ローカル変数や引数の値を参照することになります。

そしてこのようにスタックが積み上がっていき、積み上がったらあとは上で説明したようにFILOなので、逆からどんどん参照していくだけとなります。

`EBP` という現在実行中の関数のベースポインタを指すレジスタがあるのですが、そこでベースポインタを把握しています。その `EBP` を上のスタックの割り当てのイメージの、 `95, 89, 83` のアドレスにある呼び出し元のベースポインタのアドレスで更新していくことによって、常に実行中の関数のベースポインタを見失わずに処理できているわけです。

とこのようにスタックは `push (スタックに積み上げることをプッシュといいます)` され、　`pop (スタックから積み下ろすことをポップといいます)` されていきます。(*ただ実際にはpushやpopをいちいちやるわけではなく、スタックポインタを動かしてしまうはずです)
ただ、実際にはコンパイラによってスタックにデータを保持するのではなく、レジスタにデータを保持させるケースもありますのであくまでこれは基本的なスタックの考え方の説明です。

具体的にどのような処理が行われるのか確認したい場合は、以下のオブジェクトファイルで確認できます。
実際先ほどの上の例のC言語のコードを見てみるとこのようになっています。

```
gcc -c main.c -o main.o
```

```
objdump -d main.o
```

```
main.o:	file format mach-o 64-bit x86-64

Disassembly of section __TEXT,__text:

0000000000000000 <_fn3>:
       0: 55                           	pushq	%rbp
       1: 48 89 e5                     	movq	%rsp, %rbp
       4: 89 7d fc                     	movl	%edi, -4(%rbp)
       7: 89 75 f8                     	movl	%esi, -8(%rbp)
       a: c7 45 f4 6d 00 00 00         	movl	$109, -12(%rbp)
      11: c7 45 f0 6e 00 00 00         	movl	$110, -16(%rbp)
      18: 8b 45 fc                     	movl	-4(%rbp), %eax
      1b: 03 45 f8                     	addl	-8(%rbp), %eax
      1e: 03 45 f4                     	addl	-12(%rbp), %eax
      21: 03 45 f0                     	addl	-16(%rbp), %eax
      24: 5d                           	popq	%rbp
      25: c3                           	retq
      26: 66 2e 0f 1f 84 00 00 00 00 00	nopw	%cs:(%rax,%rax)

0000000000000030 <_fn2>:
      30: 55                           	pushq	%rbp
      31: 48 89 e5                     	movq	%rsp, %rbp
      34: 48 83 ec 10                  	subq	$16, %rsp
      38: 89 7d fc                     	movl	%edi, -4(%rbp)
      3b: 89 75 f8                     	movl	%esi, -8(%rbp)
      3e: c7 45 f4 6a 00 00 00         	movl	$106, -12(%rbp)
      45: bf 6b 00 00 00               	movl	$107, %edi
      4a: be 6c 00 00 00               	movl	$108, %esi
      4f: e8 00 00 00 00               	callq	0x54 <_fn2+0x24>
      54: 89 45 f0                     	movl	%eax, -16(%rbp)
      57: 8b 45 fc                     	movl	-4(%rbp), %eax
      5a: 03 45 f8                     	addl	-8(%rbp), %eax
      5d: 03 45 f4                     	addl	-12(%rbp), %eax
      60: 03 45 f0                     	addl	-16(%rbp), %eax
      63: 48 83 c4 10                  	addq	$16, %rsp
      67: 5d                           	popq	%rbp
      68: c3                           	retq
      69: 0f 1f 80 00 00 00 00         	nopl	(%rax)

0000000000000070 <_fn1>:
      70: 55                           	pushq	%rbp
      71: 48 89 e5                     	movq	%rsp, %rbp
      74: 48 83 ec 10                  	subq	$16, %rsp
      78: 89 7d fc                     	movl	%edi, -4(%rbp)
      7b: 89 75 f8                     	movl	%esi, -8(%rbp)
      7e: c7 45 f4 67 00 00 00         	movl	$103, -12(%rbp)
      85: bf 68 00 00 00               	movl	$104, %edi
      8a: be 69 00 00 00               	movl	$105, %esi
      8f: e8 00 00 00 00               	callq	0x94 <_fn1+0x24>
      94: 89 45 f0                     	movl	%eax, -16(%rbp)
      97: 8b 45 fc                     	movl	-4(%rbp), %eax
      9a: 03 45 f8                     	addl	-8(%rbp), %eax
      9d: 03 45 f4                     	addl	-12(%rbp), %eax
      a0: 03 45 f0                     	addl	-16(%rbp), %eax
      a3: 48 83 c4 10                  	addq	$16, %rsp
      a7: 5d                           	popq	%rbp
      a8: c3                           	retq
      a9: 0f 1f 80 00 00 00 00         	nopl	(%rax)

00000000000000b0 <_main>:
      b0: 55                           	pushq	%rbp
      b1: 48 89 e5                     	movq	%rsp, %rbp
      b4: 48 83 ec 10                  	subq	$16, %rsp
      b8: c7 45 fc 00 00 00 00         	movl	$0, -4(%rbp)
      bf: c7 45 f8 64 00 00 00         	movl	$100, -8(%rbp)
      c6: bf 65 00 00 00               	movl	$101, %edi
      cb: be 66 00 00 00               	movl	$102, %esi
      d0: e8 00 00 00 00               	callq	0xd5 <_main+0x25>
      d5: 89 45 f4                     	movl	%eax, -12(%rbp)
      d8: 31 c0                        	xorl	%eax, %eax
      da: 48 83 c4 10                  	addq	$16, %rsp
      de: 5d                           	popq	%rbp
      df: c3                           	retq
```

実際に見てみるとやはり結構レジスタが使われていたりと、上のイメージで説明した内容と違う箇所はありますね。
ちなみに関数の返り値などはどうしているのかと思った方がいるかもしれませんが、それは `EAX` レジスタなどによって扱われるようです。

## 最後にちょっとプログラムで実験
ここまでのスタックの理解を元に、ちょっとプログラムで実験してみます。

```C
#include <stdio.h>

int main()
{
    char x = 'x';
    char y = 'y';
    char input[4];

    printf("Type any word here: ");
    scanf("%s", input);
    printf("\n%c", x);
    printf("\n%c\n", y);

    return 0;
}
```

このプログラムを実行してみます。

"abc"と入れてみます。
```
Type any word here: abc
```
```
Type any word here: abc

x
y
```
このようになりました。特に問題はないですね。

もう一回やてみます。
今度は、"abcdefgh"と入れてみます。
```
Type any word here: abcdefgh
```
```
Type any word here: abcdefgh

f
e
```
となってしまいました。

上で見たように、ローカル変数はスタックに大きいアドレスから順番に並ぶようになっているため、指定したサイズ `4` を超える入力をそのまま配列の値として入れるようにしてしまうと、配列の先頭のアドレスから順番にアドレスを遡って書き換えてしまうためこのようなことが発生します。
<font color="Tomato">(*ローカル変数の並びはスタックに大きいアドレスから順番に並ぶとは限らないとのことですので、あくまでスタックの書き換えが発生してしまうことがあるという参考として読んでいただければと思います。詳しくはいただいた[こちらのコメント](https://qiita.com/uchidak/items/8efbf0190fb7f1e9bdda#comment-ca457e7938ef24cf30bd)の内容をご参照ください。)</font>

こうならないように

```C
scanf("%3s", input);
```

のように入力値として受け取る上限を決め打ちしておくこともできます。
ただ受け取る入力値の長さに上限を決めることで解決しない場合、つまり動的にメモリ領域を確保したい場合には、ヒープメモリを使う必要があります。
<font color="Tomato">(*こちらの回避策としてヒープ領域を使う以外にも、C99で仕様に追加された可変長配列や、非標準の関数であるalloca等を使う方法というのもあるとのことです。詳しくはいただいた[こちらのコメント](https://qiita.com/uchidak/items/8efbf0190fb7f1e9bdda#comment-ca457e7938ef24cf30bd)の内容をご参照ください。)</font>

```C
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char x = 'x';
    char y = 'y';
    char *input;
    input = (char *) malloc(4);

    printf("Type any word here: ");
    scanf("%s", input);
    printf("\n%c", x);
    printf("\n%c\n", y);

    return 0;
}
```

これなら

```
Type any word here: abcdefgh

x
y
```

のようにスタックの値が遡って書き変わってしまうことはありません。メモリ領域が違うからです。

ただしヒープ領域にメモリを確保したとしても、次のような書き方、入力値の入れ方をするとメモリが書き変わってしまいますので、ヒープ領域を確保しておけばそれでOKという話ではありませんので注意が必要です。

```C
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char *input;
    input = (char *) malloc(4);
    char *input2;
    input2 = (char *) malloc(4);
    printf("\n%p", input);
    printf("\n%p", input2);

    printf("\nType any word here: ");
    scanf("%s", input2);

    printf("\n%s", input2);

    printf("\nType any word here again: ");
    scanf("%s", input);

    printf("\n%s\n", input2);

    return 0;
}
```

```

0x6000036f0040
0x6000036f0050
Type any word here:
```
`input2` ポインタは、 `input` の16バイトの先にいるみたいなので

```

0x6000036f0040
0x6000036f0050
Type any word here: abcd

abcd
Type any word here again: abcdefghijklmnopq

q
```

と17文字入力したら、結果の通り `input2` の値が書き変わってしまいます。

## おわり
普段C言語などよりもさらに高級な言語で開発していると、このようなメモリの管理のされ方やメモリリークについて特に気にせずに開発できてしまいますが、今回メモリ管理の奥深さを知ることができました。
メモリの話だけでも、物理メモリを拡張して扱うための仮想メモリの仕組み、ページングという仕組みなどまだまだ奥が深いですが、今回はスタックについてのまとめでした。

————————————
【オープンロジイベント情報】
<12/15(木)19:30〜>
「CTO・VPoEぶっちゃけトーク！　〜失敗から学ぶエンジニア組織論〜」
過去の失敗談をセキララに語りつつ、オープンロジでどんな組織をつくっていくかが語られる予定なので、ご都合合う方は是非ご参加ください！
https://openlogi.connpass.com/event/265230/
————————————