mallocの動作を追いかける(fastbins編)

# はじめに

[maIIoc動画](https://www.youtube.com/watch?v=0-vWT-t0UHg)見てますか？＞挨拶

今更ですけど、「○○＞挨拶」というフォーマット、古いとかもう通り越して、今時の若い人は知らないんでしょうね。このフォーマットの創始者が誰か知らないですが、広めたのは[僕秩](http://www.dfnt.net/)なんじゃないでしょうか。少なくとも僕が知ったのはそこです。っていうかさっき僕秩見てみたら、まだやってましたねこの挨拶。

というわけで、今回はmallocにおけるfastbinsのあたりを追います。あまり詳しくないので間違ってたらマサカリを歓迎します。

これまでのmalloc記事。

* [mallocの動作を追いかける(mmap編)](https://qiita.com/kaityo256/items/9e78b507940b2292bf79) 
* [mallocの動作を追いかける(prev_size編)](https://qiita.com/kaityo256/items/2e9a368a5b627daa2ff6)
* [mallocの動作を追いかける(main_arenaとsbrk編)](https://qiita.com/kaityo256/items/94a84dbe922eb5996a27)
* [mallocの動作を追いかける(fastbins編)](https://qiita.com/kaityo256/items/ca54b1b921d8ab96cb82) ← イマココ
* [mallocの動作を追いかける(マルチスレッド編)](https://qiita.com/kaityo256/items/bf6563361c502bbf062e) 
* [mallocの動作を追いかける(環境変数編)](https://qiita.com/kaityo256/items/fc9a27d0df1371246951)

# fastbins

mallocは、小さいメモリ確保要求に関しては、サイズに応じてビンに切って、そのサイズ毎にリンクリストを作成する。これにより、そのサイズについては必ずbest-fit allocator、つまり要求サイズぴったりのチャンクを見つけてくる。まずはそのリンクリストを直接見てみよう。

こんなコードを書いてみる。

```cpp:test.cpp
#include <cstdio>
#include <cstdlib>

int
main(void){
  const int N = 3;
  char *buf[N];
  printf("---before free---\n");
  for(int i=0;i<N;i++){
    buf[i] = (char*)malloc(1);
    printf("buf[%d]->0x%lx\n",i,buf[i]);
  }
  for(int i=0;i<N;i++){
    free(buf[i]);
  }
  printf("---after free---\n");
  for(int i=0;i<N;i++){
    printf("buf[%d]->0x%lx:0x%lx\n",i,buf[i],*(size_t*)(buf[i]));
  }
}
```

ただ、サイズ1のmallocを3回繰り返し、それをfreeするだけのコードである。ただし、freeした後に、先程mallocで確保したポインタが指す中身を表示している。実行結果はこうなる。

```shell-session
$ g++ test.cpp
$ ./a.out
---before free---
buf[0]->0x602010
buf[1]->0x602030
buf[2]->0x602050
---after free---
buf[0]->0x602010:0x0
buf[1]->0x602030:0x602000
buf[2]->0x602050:0x602020
```

例えば、`buf[1]`の指すアドレスは0x602030であり、そこにはfreeの後に0x602000というアドレスが入っていることがわかる。

これは、`malloc_chunk`構造体の、`fd`メンバに対応している。`malloc_chunk`構造体はこんな形をしている。

```cpp:
struct malloc_chunk {

    INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
    INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */

    struct malloc_chunk* fd;         /* double links -- used only if free. */
    struct malloc_chunk* bk;

/* Only used for large blocks: pointer to next larger size.  */
    struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
    struct malloc_chunk* bk_nextsize;
};
```

この`struct malloc_chunk* fd`が、ちょうどmallocが返してくるポインタの位置である。mallocの返してくる位置と、チャンクで管理される場所がずれているのは[以前の記事](https://qiita.com/kaityo256/items/2e9a368a5b627daa2ff6)で見たとおり。小さいサイズのチャンクがfreeされる時、この`fd`の位置に「一つ前のチャンク」の位置がセットされる。小さいサイズでは`fd`しか使わない前方参照リンクになっている。図解するとこんな感じになっている。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/79744/5eb48f67-83bc-4ff7-942f-25281289502d.png)

さて、前方参照リストなので、どこかに「一番最初の場所」を保存しておかないといけない。それが`main_arena->fastbinsY`に保存されている。今回は最小サイズなので`main_arena->fastbinsY[0]`、つまり`<main_arena+8>`の場所に保存されている。この値が更新されていくのをgdbで追いかけてみよう。まずは14行目にブレークポイントを置いて、そこまで実行する。

```shell-session
$ g++ -g test.cpp
$ gdb -q ./a.out
Reading symbols from /path/to/a.out...done.
(gdb) b 14
Breakpoint 1 at 0x4007aa: file test.cpp, line 14.
(gdb) r
Starting program: /path/to/a.out 
---before free---
buf[0]->0x602010
buf[1]->0x602030
buf[2]->0x602050

Breakpoint 1, main () at test.cpp:14
14	    free(buf[i]);
(gdb) 
```

最初のfreeの直前まできた。この状態で`main_arena`の最初の方をダンプしてみる。

```shell-session
(gdb) x/4xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000001	0x00000000	0x00000000
```

それぞれ、
* `mutex` (4バイト)
* `flags` (4バイト)
* `fastbinsY[0]` (8バイト)

の16バイトが表示されている。見て分かる通り、`flags`が立っているだけで、fastbinsY[0]の値は空である。

continueしてから同じことをしてみる。

```shell-session
(gdb) c
Continuing.

Breakpoint 1, main () at test.cpp:14
14	    free(buf[i]);
(gdb) x/4xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000000	0x00602000	0x00000000
(gdb) 
```

これは最初のfreeが実行された直後である。最初のmallocで0x602010が割り当てられた。そのチャンクの先頭は0x10バイト前の0x00602000であり、その場所がキャッシュされている。

さらに続けてみる。

```shell-session
(gdb) c
Continuing.

Breakpoint 1, main () at test.cpp:14
14	    free(buf[i]);
(gdb) x/4xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000000	0x00602020	0x00000000
```

値が更新され、`buf[1]`に対応するチャンクがキャッシュされた。

また続ける(今度はcontinueではなくnext)。

```shell-session
(gdb) n
13	  for(int i=0;i<N;i++){
(gdb) x/4xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000000	0x00602040	0x00000000
(gdb) 
```

`buf[2]`に対応するチャンクがキャッシュされた。ここからたどることで、サイズ1〜24のメモリ、すなわち、チャンクサイズ32バイトのチャンクをたどることができる。

次にチャンクサイズ32バイトのmalloc要求が来た時は、キャッシュされたアドレス+0x10を返し、一つリストを辿って繋ぎ変えれば良い。

先程のコードで、3回freeされた直後はこうなっている。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/79744/4d6ea6ca-b731-a41c-63d6-80e95ef58e26.png)

この状態で`main_arena->fastbinsY[0]`の守備範囲のチャンクのメモリ要求が来たら、ユーザには`main_arena->fastbinsY[0]`の指すチャンクを返し(実際にmallocが返すのはそのアドレスに0x10を足したもの)、ユーザに返すチャンクの`fd`が指していた一つ前のチャンクにつなぎ替える。

図にするとこんな感じ。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/79744/60f642b3-a0a3-aef3-a2b2-40b3da2393d3.png)

# global_max_fast

さて、fastbinsは24バイトから16バイトずつ管理されており、配列としては10個用意されているため、24,40,...,168バイトまでのビンがありそうな気がする。それを確認するため、こんなコードを書いてみよう。まずは[前回](https://qiita.com/kaityo256/items/94a84dbe922eb5996a27)も定義した`main_arena`表示用の構造体定義を作る。

```cpp:malloc.h
struct malloc_state{
  int mutex;
  int flags;
  size_t *fastbinsY[10];
  size_t *top;
  size_t *last_remainder;
};
typedef malloc_state* mstate;
mstate ma = (mstate)0x2aaaab813e80;
```

ただし、前回は`main_arena`という名前を使ったが、これだとgdbで確認したときに本当の`main_arena`を見たいときに不便だったので、`ma`という名前にしてみた。

これを使って、こんなコードを書いてみる。

```cpp:test2.cpp
#include <cstdio>
#include <cstdlib>
#include "malloc.h"
void
dump_ma(void){
  for(int i=0;i<10;i++){
    printf("fastbins[%d]:%lx\n",i,ma->fastbinsY[i]);
  }
}
const int N = 10;
int
main(void){
  char *buf[N];
  for(int i=0;i<N;i++){
    buf[i] = (char*)malloc(24+i*16);
  }
  for(int i=0;i<N;i++){
    printf("--------\n");
    printf("free(buf[%d])\n",i);
    free(buf[i]);
    dump_ma();
  }
}
```

これは、24バイトから16バイトずつ増やしながら10回mallocして、それを一個ずつfreeしながら`main_arena->fastbinsY`の値をダンプするコードである。無論、最終的には10個のチャンクアドレスがキャッシュされることを期待しているが、実行してみるとこうなる。

```shell-session
$ g++ -g test2.cpp
$ ./a.out
--------
free(buf[0])
fastbins[0]:602000
fastbins[1]:0
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[1])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[2])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[3])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[4])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[5])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[6])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:6021b0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[7])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:6021b0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[8])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:6021b0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[9])
fastbins[0]:0
fastbins[1]:0
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
```

`buf[6]`をfreeするまでは期待通りの動作だが、`buf[7]'をfreeしてもそのアドレスはキャッシュされず、`buf[9]`をfreeしたら全部ゼロクリアされてしまった。

実は、mallocは`global_max_fast`という変数を持っており、このサイズでfastbinsの登録を打ち切っている。さらに、ある程度以上のfreeにより、mallocのガーベジコレクションである`malloc_consolidate`が走る。これによりfastbinsの値がクリアされる。その様子を見てみよう。

まず、global_max_fastの値を見てみる。

プログラム実行開始直後はその値は0である。

```shell-session
$ g++ -g test2.cpp
$ gdb ./a.out
(gdb) b main
Breakpoint 1 at 0x40078b: file test2.cpp, line 14.
(gdb) r
Breakpoint 1, main () at test2.cpp:14
14	  for(int i=0;i<N;i++){
(gdb) p global_max_fast
$1 = 0
```

しかし、一度mallocが呼ばれた後は値がセットされている。18行目あたりで止めて表示してみよう。

```shell-session
(gdb) b 18
Breakpoint 2 at 0x4007c7: file test2.cpp, line 18.
(gdb) c
Continuing.

Breakpoint 2, main () at test2.cpp:18
18	    printf("--------\n");
(gdb) p global_max_fast
$2 = 128
```

128バイトが上限になっている。ユーザの要求メモリ120バイト+ヘッダ8の128バイト、つまり`main_arena->fastbinsY[6]`の守備範囲までがfastbinsの対象となっており、それ以上はキャッシュされない。

さらに、`malloc_consolidate`が呼ばれる様子も確認しよう。gdbで再実行して、`dump_ma`にブレークポイントをかけて、まずはそこまで実行する。

```shell-session
$ gdb ./a.out
(gdb) b dump_ma
Breakpoint 1 at 0x400748: file test2.cpp, line 6.
(gdb) r
Breakpoint 1, dump_ma () at test2.cpp:6
6	  for(int i=0;i<10;i++){
(gdb) 
```

止まったところで新たに`malloc_consolidate`にもブレークポイントを置いて、何度かcontinueする。

```shell-session
(gdb) b malloc_consolidate
Breakpoint 2 at 0x2aaaab5152f0
(gdb) c
Continuing.
fastbins[0]:602000
fastbins[1]:0
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[1])

Breakpoint 1, dump_ma () at test2.cpp:6
6	  for(int i=0;i<10;i++){
(gdb) c
Continuing.
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[2])

Breakpoint 1, dump_ma () at test2.cpp:6
6	  for(int i=0;i<10;i++){

(snip)

(gdb) c
Continuing.
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:6021b0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[9])

Breakpoint 2, 0x00002aaaab5152f0 in malloc_consolidate () from /lib64/libc.so.6
```

`free(buf[9])`が実行された時に`malloc_consolidate`が呼ばれたことがわかる。その直後、fastbinsは全てクリアされる。

# まとめ

ユーザ要求で120バイト、チャンクサイズで128バイトまでの小さい領域については、最後にfreeされたチャンクがキャッシュされ、そこから前方参照リンクでチャンクがつながっており、高速にmalloc/freeができることを見た。おそらく「同じサイズの構造体を何度もmalloc/freeする」状態に対処するための工夫だと思われる。fastbinsは10個分用意されているのに、なぜか`global_max_fast`は128バイトに設定されており、結果としてビンを7つしか使っていない理由はよくわからない。

どうでもいいけど、なんかfreeしたメモリ領域を表示してmallocが何やってるかの背景を探るの、なんか背徳感がある。この管理領域を利用してなんか不正なことができる気がするし、実際そういうことをしたのが[GHOST脆弱性](http://labs.timedia.co.jp/2015/01/how-to-use-ghost.html)なのであった。

[続く](https://qiita.com/kaityo256/items/bf6563361c502bbf062e)

# 参考

* [malloc動画](https://www.youtube.com/watch?v=0-vWT-t0UHg) 元動画(ってなに？)
* [mallocの旅(glibc編)](https://www.slideshare.net/kosaki55tea/glibc-malloc) 上の動画のスライド
* [malloc(3)のメモリ管理構造](http://www.valinux.co.jp/technologylibrary/document/linux/malloc0001/) 説明がわかりやすい記事。
* [malloc.c](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html) mallocのソース
* [A Memory Allocator](http://gee.cs.oswego.edu/dl/html/malloc.html) mallocマスター、Doug Lea氏によるmalloc解説。やや記述は古いがmallocの思想が垣間見えて興味深い。
* [GHOST 脆弱性は如何様に使うのか](http://labs.timedia.co.jp/2015/01/how-to-use-ghost.html) GHOSTの脆弱性にmallocの管理領域が使われたことの解説。