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


# はじめに

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

[前回](https://qiita.com/kaityo256/items/9e78b507940b2292bf79)は比較的振る舞いがシンプルな、mallocが内部でmmapを呼ぶケースについて調べたが、今回は`malloc_chunk`構造体と実際に使われるメモリ配置がちっとも対応していないことを見てみる。

* [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)

# chunkについて

繰り返しになるが、mallocはメモリをチャンク(chunk)という単位で管理する。これは「ヘッダ＋ユーザが使える領域」なのだが、メモリを効率利用するために、チャンクのヘッダが他の使用中メモリを指していたり、`malloc_chunk`構造体のメンバが有効な値を持つかどうかが文脈依存だったりしてややこしい。

とりあえず`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;
};
```

今回は小さいサイズのmallocを扱うため、`fd_nextsize`や`bk_nextsize`は使われない。また、`mchunk_prev_size`が有効なのは使われていないチャンク、つまりfreeされた後なので、常に有効な値を持つメンバは`mchunk_size`だけである。

# small binについて

Glibc mallocでは、小さい領域はsmall binという方法で管理されている。詳しくは[mallocの旅(glibc編)](https://www.slideshare.net/kosaki55tea/glibc-malloc)でも見ていただくとして、ここで重要なのは、

* 小さいサイズのチャンクは、チャンクサイズ`size`と一つ前のチャンクのサイズ`prev_size`で管理されている。
* しかし、一つ前のチャンクは`prev_size`のところまで使っている。
* `prev_size`が有効な値を持っているかどうかは、`size`の最下位1ビットが立っているかどうかで判定する

ということ。今回は、実際に

* `malloc_chunk`構造体の場所がメモリ境界と一致していないこと
* `prev_size`の場所までユーザが使っていること

を確認してみる。

# 実際に追いかける

## プログラムから確認

まずはこんなソースを書いてみる。

```cpp:test.cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
const int N = 5;
char *buf[N];

typedef size_t INTERNAL_SIZE_T;
struct malloc_chunk {
  INTERNAL_SIZE_T mchunk_prev_size;
  INTERNAL_SIZE_T mchunk_size;
};

typedef struct malloc_chunk* mchunkptr;

void
show(char *buf){
  mchunkptr p = (mchunkptr)(buf-16);
  size_t prev_size = p->mchunk_prev_size;
  size_t size = p->mchunk_size;
  size_t chunk_size = (size>>2)<<2;
  printf("0x%lx->0x%lx (0x%lx):",p,p+chunk_size,chunk_size);
  if(size &1){
    printf("prev is used; prev_size = 0x%lX\n",prev_size);
  }else{
    printf("prev is not used: prev_size = 0x%lX\n",prev_size);
  }
}

void
show_all(void){
  for(int i=0;i<N;i++){
    show(buf[i]);
  }
}

int
main(void){
  size_t SIZE = 0x108;
  for(int i=0;i<N;i++){
    buf[i] = (char*)malloc(SIZE);
    std::fill(buf[i],buf[i]+SIZE,0xAA+0x11*i);
  }
  printf("----before free-----\n");
  show_all();
  free(buf[1]);
  printf("-----after free-----\n");
  show_all();
  buf[1] = (char*)malloc(SIZE*2);
  printf("-----alloc again-----\n");
  show_all();
  for(int i=0;i<N;i++){
    free(buf[i]);
  }
}
```

前回みたいに生でアドレスにアクセスしても良いのだが、雰囲気を出すために`malloc_chunk`構造体(の頭だけ)を定義し、`malloc`で受け取ったポインタから16バイトだけ戻った場所を`malloc_chunk*`にキャストしてやることにする。さらにglibcっぽさを出すため、

```cpp
typedef struct malloc_chunk* mchunkptr;
```

と、`malloc_chunk`へのポインタを`mchunkptr`にキャストしている。

このプログラムは順番に、

* 0x108(264)バイトの領域を5つ確保する。もらった領域をそれぞれ0xAAから0xEEで初期化する。
* 2番目の領域をfreeする
* 0x210(528)バイトを要求する

ということをやっている。それぞれのステップで、確保したポインタの16バイト前を`mchunkptr`だと思って、チャンクサイズや一つ前のチャンクサイズを表示している。

実行結果はこんな感じになる。

```shell-session
$ g++ test.cpp
$ ./a.out
----before free-----
0x602010->0x602120 (0x110):prev is used; prev_size = 0x0
0x602120->0x602230 (0x110):prev is used; prev_size = 0xAAAAAAAAAAAAAAAA
0x602230->0x602340 (0x110):prev is used; prev_size = 0xBBBBBBBBBBBBBBBB
0x602340->0x602450 (0x110):prev is used; prev_size = 0xCCCCCCCCCCCCCCCC
0x602450->0x602560 (0x110):prev is used; prev_size = 0xDDDDDDDDDDDDDDDD
-----after free-----
0x602010->0x602120 (0x110):prev is used; prev_size = 0x0
0x602120->0x602230 (0x110):prev is used; prev_size = 0xAAAAAAAAAAAAAAAA
0x602230->0x602340 (0x110):prev is not used: prev_size = 0x110
0x602340->0x602450 (0x110):prev is used; prev_size = 0xCCCCCCCCCCCCCCCC
0x602450->0x602560 (0x110):prev is used; prev_size = 0xDDDDDDDDDDDDDDDD
-----alloc again-----
0x602010->0x602120 (0x110):prev is used; prev_size = 0x0
0x602560->0x602780 (0x220):prev is used; prev_size = 0xEEEEEEEEEEEEEEEE
0x602230->0x602340 (0x110):prev is not used: prev_size = 0x110
0x602340->0x602450 (0x110):prev is used; prev_size = 0xCCCCCCCCCCCCCCCC
0x602450->0x602560 (0x110):prev is used; prev_size = 0xDDDDDDDDDDDDDDDD
```

まず、最初にmallocした直後の状態はこうなっている。
![malloc1.png](https://qiita-image-store.s3.amazonaws.com/0/79744/f16e2d51-583b-377a-6687-2c4603279e21.png "malloc1.png")

例えば、`buf[0]`のアドレスは0x602010である。その16バイト前がチャンクの先頭アドレスだが、いま有効なのはチャンクサイズだけであり、それは`buf[0] - 8`のアドレスに入っている。その値は0x110(272)バイトであり、要求サイズより8バイトだけ大きい。ユーザは`buf[i]`から0x108バイトが使えることが保証されている(赤い矢印)。また、チャンク的には、例えば最初のチャンクなら0x602000から0x110バイトだと認識されている(水色の矢印)が、見て分かる通りユーザがもらった領域と始点、終点ともに対応していない。これがmallocのわかりづらさの主要原因だと思う。

さて、`buf[i] - 8`にはそれぞれのチャンクのチャンクサイズが入っているが、実際の値は0x111である。しかし、チャンクサイズの下位3bitは別の意味を持つフラグなのであった。ここでは「前のチャンクが使用中であるか」のフラグがたっている(黄色い四角)。このフラグが立っている時には`buf[i] - 16`の`prev_size`は意味のある値が入っていない(ユーザが使っている)。実際に`buf[1]`を管理するチャンクの`prev_size`には`0xAAAAAAAAAAAAAAAA`という値が入っていて、これは`buf[0]`としてユーザが使っている。

さて、ここで`buf[1]`をfreeしよう。freeした直後はこんな状態になっている。

![malloc2.png](https://qiita-image-store.s3.amazonaws.com/0/79744/fae9aa2d-de14-f3ff-543b-579b1b1141ce.png "malloc2.png")

`buf[1]`の指す領域はfreeされたのでもはや中身は保証されないが、buf[1]の指す場所は0x602120のままになっている。ここで、新たに`buf[2]`に対応するチャンクの`prev_size`に、`buf[1]`に対応するチャンクサイズ0x110が書き込まれる(0x110)。さらに`buf[2]`のチャンクサイズの最下位ビットがクリアされ、直前のチャンクが使われていない(`prev_size`が有効な値を持つ)ことが示される。

次に、先程freeした`buf[1]`に0x210(528)バイトのmalloc要求を出そう。先程空いた領域にはハマらないため、こんな感じになる。

![malloc3.png](https://qiita-image-store.s3.amazonaws.com/0/79744/0ceda53c-0ddb-e964-55d1-4bd1037552a2.png "malloc3.png")

mallocは新たに0x602560という場所を返す。チャンクサイズは0x220バイトである。`prev_size`メンバのある場所は`buf[4]`が管理する領域にかぶっているから0xEEEEEEEEEEEEEEEEを表示している。

## gdbで動作を追いかける


先程のプログラムで確かにチャンクサイズとユーザが使う領域が一致しておらず、かつ`prev_size`は直前のチャンク使用時には意味のある値を持たず、直前のチャンクが未使用であればそのサイズが入ることがわかった。gdbでこれを追いかけても同じことがわかるだけなのだが、なんとなく実際にgdbで直接振る舞いを見た方がわかった気になるような人(＝俺)のため、一連の動作をgdbで追いかけてみる。

先程のプログラムを-gつきでコンパイルしてからgdbで開こう。

```shell-session
$ g++ -g test.cpp
$ gdb --tui -q ./a.out
```

繰り返しになるが、筆者はgdbのTUI推しである。まずはfreeの直前にブレークポイントをかけよう。

```gdb
(gdb) break 45
Breakpoint 1 at 0x4008a6: file test.cpp, line 45.
(gdb) r
snip
Breakpoint 1, main () at test.cpp:45
(gdb) 
```

ここで、`_int_free`にブレークポイントをかけて続行する。TUIモードを使っていれば「No Source Available」と言う表示が出るのでアセンブリを表示させよう。

```gdb
(gdb) break _int_free
Breakpoint 2 at 0x2aaaab516550
(gdb) n

Breakpoint 2, 0x00002aaaab516550 in _int_free () from /lib64/libc.so.6
(gdb) layout asm
```

こんな表示になるはず。

![gdb4.png](https://qiita-image-store.s3.amazonaws.com/0/79744/649c7b9b-ea68-e8d0-6864-52f0c975099a.png "gdb4.png")

さて、`_int_free`のソースはこんな感じになっている。

```cpp
static void
_int_free (mstate av, mchunkptr p, int have_lock)
```

つまり、第一引数が`malloc_state`へのポインタ(今回は`main_arena`になってるはず)、第二引数がfreeするためのチャンクのアドレスである。この第二引数を表示させてみる。これは`%rsi`に入っているはず。

```gdb
(gdb) print/x $rsi
$1 = 0x602110
```

先程の図にあった通り、`buf[1]`を管理するチャンクの先頭アドレスである0x602110が入っている。しかし、先程見たようにこのアドレスそのものは`buf[0]`が使っている。中身を表示させてみよう。

```gdb
(gdb) x/xw 0x602110
0x602110:       0xaaaaaaaa
```

`buf[0]`が自分の領域を0xAAで初期化しているので、それが見えている。

もちろん`malloc_chunk`の`mchunk_size`には意味のある値が入っている。それはチャンクの先頭アドレスから8バイト後に入っている。

```gdb
(gdb) x/xw 0x602118
0x602118:       0x00000111
```

チャンクサイズである0x110に、prev_usedフラグとして最下位ビット1を立てた0x111が格納されている。

さて、今`buf[1]`をfreeしようとしているのだが、その過程で`buf[2]`が管理するチャンクの、`prev_size`がセットされるはずである。そのアドレスは`buf[2]-0x10`、つまり0x602220であるはずなので、そこにウォッチポイントを置こう。

```gdb
(gdb) watch *0x602220 
Hardware watchpoint 3: *0x602220
```

この状態で続行すると、ちゃんと引っかかる。

```gdb
(gdb) n
Hardware watchpoint 3: *0x602220

Old value = -1145324613
New value = 272
0x00002aaaab51668a in _int_free () from /lib64/libc.so.6
(gdb) 
```

元々0xbbbbbbbb(-1145324613)だったところに、チャンクサイズである0x110(272)がセットされた。

# まとめ

mallocにおいて、小さいサイズのチャンクでは管理領域は8バイト(チャンクサイズ)だけで、freeされたらもう8バイト使って「一つ前のチャンクのサイズ」が書き込まれること、チャンクが管理する領域とユーザがもらった領域は始点も終点も一致していないことなどを確認した。こういうのはmalloc動画やそのスライド、参考文献などを見ればわかることなのだが、実際に動かしてみて、チャンクの先頭ポインタが意味のある情報を持っていないことを見たりすると、mallocのアレぶりを実感できる。

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

# 参考

* [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のソース