Valgrind による動的解析

# はじめに
* 動的解析ツールの一つである「Valgrind」について紹介します。

# 動的解析とは
* ソフトウェアのテスト技法で、対象のソフトウェアを実行するかに着目し2つの分類があります。

|種類|説明|例|
|---|---|---|
|静的テスト|ソースを実行せずに欠陥をチェックする|レビュー、コンパイラによるチェック|
|動的テスト|ソースを実行して欠陥をチェックする|テスターによる機能テスト、ツールによるチェック|

* 特に、ツールを用いて静的テストを行う場合は「静的解析」、動的テストを行う場合は「動的解析」と呼ばれます。

|種類|例|
|---|---|
|静的解析|コンパイラ、CppCheckやSourcetrail|
|動的解析|Valgrind|

# Valgrindとは
* オープンソースの動的解析ツールに「Valgrind」があります。
* [公式ページ](https://valgrind.org/) によると、以下のプラットフォームで利用できます。
    * Linux
    * Solaris
    * Android
    * Mac OS

## 機能
* 主に以下のツールがあります。

|種類|説明|
|---|---|
|Memcheck|主にC言語、C++プログラムを対象に、メモリマネジメントに伴う問題をチェックする|
|Cachegrind|キャッシュプロファイラプログラム。CPUの I1, D1 and L2キャッシュについて詳細なシュミレーションを実行する。||
|Callgrind|Cachegrindの拡張版でコールグラフを作成し、可視化できる。||
|Massif|ヒープメモリのプロファイラ||
|Helgrind|スレッドデバッガ||
|DRD|マルチスレッドのC言語、C++プログラムにおけるエラーを検知する。||

# Memcheck の実行例
## 対象
* Memcheck の例として、以下の問題点がある C++ プログラムを使用します。
  * char配列が固定サイズのため、5文字以上で「バッファオーバーフロー」が生じます。
  * new[] で割り当てたヒープメモリを delete[] で解放していないため、「メモリリーク」が生じます。

```
#include <iostream>
#include <string>

int main() {
    char *input = nullptr;
    input = new char[ 5 ];
    std::cin >> input;
    std::cout << 入力値: << input << std::endl;
}
```

## 実行内容
* ビルドしたプログラムに対して標準入力で「12345」を入力します。
* その際、以下でメモリマネジメントのチェックを行います。
  * 「--leak-check=full」で、プログラムの実行後のメモリリークを検知します。
  * 「-s」で検知したエラーの一覧を最後に出力します。

```
valgrind --leak-check=full -s ./Sample
```

## 実行結果
* 「Invalid write of size 1」, 「Invalid read of size 1」より、1サイズ分、不正なメモリブロックの読み書きが実行されたことが分かります。
* 「LEAK SUMMARY」の「definitely lost」より、割り当てたメモリブロックがプログラムの終了時点で解放されなかったことを指しています。
* なお、g++ (gcc) で「-g」のオプションを付与してビルドしたプログラムの場合、Memcheck の実行時にエラー箇所の行番号も出力します。

<details><summary>Memcheck</summary><div>

```
==4952== Memcheck, a memory error detector
==4952== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==4952== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==4952== Command: ./Sample
==4952== 
12345
==4952== Invalid write of size 1
==4952==    at 0x491E56E: std::basic_istream<char, std::char_traits<char> >& std::operator>><char, std::char_traits<char> >(std::basic_istream<char, std::char_traits<char> >&, char*) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==4952==    by 0x109215: main (in /usr/local/bin/valgrind/Sample)
==4952==  Address 0x4daec85 is 0 bytes after a block of size 5 alloc'd
==4952==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4952==    by 0x1091FE: main (in /usr/local/bin/valgrind/Sample)
==4952== 
==4952== Invalid read of size 1
==4952==    at 0x483EF54: strlen (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4952==    by 0x498EB1D: std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==4952==    by 0x10923A: main (in /usr/local/bin/valgrind/Sample)
==4952==  Address 0x4daec85 is 0 bytes after a block of size 5 alloc'd
==4952==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4952==    by 0x1091FE: main (in /usr/local/bin/valgrind/Sample)
==4952== 
入力値:12345
==4952== 
==4952== HEAP SUMMARY:
==4952==     in use at exit: 5 bytes in 1 blocks
==4952==   total heap usage: 4 allocs, 3 frees, 74,757 bytes allocated
==4952== 
==4952== 5 bytes in 1 blocks are definitely lost in loss record 1 of 1
==4952==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4952==    by 0x1091FE: main (in /usr/local/bin/valgrind/Sample)
==4952== 
==4952== LEAK SUMMARY:
==4952==    definitely lost: 5 bytes in 1 blocks
==4952==    indirectly lost: 0 bytes in 0 blocks
==4952==      possibly lost: 0 bytes in 0 blocks
==4952==    still reachable: 0 bytes in 0 blocks
==4952==         suppressed: 0 bytes in 0 blocks
==4952== 
==4952== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
==4952== 
==4952== 1 errors in context 1 of 3:
==4952== Invalid read of size 1
==4952==    at 0x483EF54: strlen (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4952==    by 0x498EB1D: std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==4952==    by 0x10923A: main (in /usr/local/bin/valgrind/Sample)
==4952==  Address 0x4daec85 is 0 bytes after a block of size 5 alloc'd
==4952==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4952==    by 0x1091FE: main (in /usr/local/bin/valgrind/Sample)
==4952== 
==4952== 
==4952== 1 errors in context 2 of 3:
==4952== Invalid write of size 1
==4952==    at 0x491E56E: std::basic_istream<char, std::char_traits<char> >& std::operator>><char, std::char_traits<char> >(std::basic_istream<char, std::char_traits<char> >&, char*) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==4952==    by 0x109215: main (in /usr/local/bin/valgrind/Sample)
==4952==  Address 0x4daec85 is 0 bytes after a block of size 5 alloc'd
==4952==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4952==    by 0x1091FE: main (in /usr/local/bin/valgrind/Sample)
==4952== 
==4952== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
```
</div></details>

<details><summary>Memcheck (g++にて-gオプションでビルドした場合)</summary><div>

```
==9843== Memcheck, a memory error detector
==9843== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9843== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==9843== Command: ./Sample
==9843== 
12345
==9843== Invalid write of size 1
==9843==    at 0x492056E: std::basic_istream<char, std::char_traits<char> >& std::operator>><char, std::char_traits<char> >(std::basic_istream<char, std::char_traits<char> >&, char*) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==9843==    by 0x109140: main (Sample.cpp:6)
==9843==  Address 0x4db0c85 is 0 bytes after a block of size 5 alloc'd
==9843==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9843==    by 0x10912E: main (Sample.cpp:5)
==9843== 
==9843== Invalid read of size 1
==9843==    at 0x483EF54: strlen (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9843==    by 0x4990B1D: std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==9843==    by 0x109167: main (Sample.cpp:7)
==9843==  Address 0x4db0c85 is 0 bytes after a block of size 5 alloc'd
==9843==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9843==    by 0x10912E: main (Sample.cpp:5)
==9843== 
入力値:12345
==9843== 
==9843== HEAP SUMMARY:
==9843==     in use at exit: 5 bytes in 1 blocks
==9843==   total heap usage: 4 allocs, 3 frees, 74,757 bytes allocated
==9843== 
==9843== 5 bytes in 1 blocks are definitely lost in loss record 1 of 1
==9843==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9843==    by 0x10912E: main (Sample.cpp:5)
==9843== 
==9843== LEAK SUMMARY:
==9843==    definitely lost: 5 bytes in 1 blocks
==9843==    indirectly lost: 0 bytes in 0 blocks
==9843==      possibly lost: 0 bytes in 0 blocks
==9843==    still reachable: 0 bytes in 0 blocks
==9843==         suppressed: 0 bytes in 0 blocks
==9843== 
==9843== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
==9843== 
==9843== 1 errors in context 1 of 3:
==9843== Invalid read of size 1
==9843==    at 0x483EF54: strlen (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9843==    by 0x4990B1D: std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==9843==    by 0x109167: main (Sample.cpp:7)
==9843==  Address 0x4db0c85 is 0 bytes after a block of size 5 alloc'd
==9843==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9843==    by 0x10912E: main (Sample.cpp:5)
==9843== 
==9843== 
==9843== 1 errors in context 2 of 3:
==9843== Invalid write of size 1
==9843==    at 0x492056E: std::basic_istream<char, std::char_traits<char> >& std::operator>><char, std::char_traits<char> >(std::basic_istream<char, std::char_traits<char> >&, char*) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==9843==    by 0x109140: main (Sample.cpp:6)
==9843==  Address 0x4db0c85 is 0 bytes after a block of size 5 alloc'd
==9843==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9843==    by 0x10912E: main (Sample.cpp:5)
==9843== 
==9843== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
```
</div></details>


# Massif の実行例
## 対象
* 続いて、Massif の例として以下のメモリ使用量をプロファイリングします。
  * 1行ごとに読み込んだテキストファイルを標準出力します。

```
#include <iostream>
#include <fstream>
#include <string>

int main() {
    std::ifstream ifs( "./sample.txt" );
    if ( !ifs ) {
        std::cerr << "ファイルオープンエラー" << std::endl;
        return 1;
    }

    std::string str = "";
    while ( getline( ifs, str ) ) {
        std::cout << str << std::endl;
    }

    return 0;
}
```

## 実行内容
* 「--tool=massif」で Massif を使用します。
* 「--time-unit」でプロファイリング時に使用する時間の単位を指定します。今回は、実行時間が短いプログラムで有用とされている「B」を指定し、ヒープやスタックに割り当てられたまたは解放されたバイトを表示します。
* 「--stacks=yes」でスタックもプロファイリングします。
* 「ms_print」で、Massif の実行後に出力される「massif.out.pid」からメモリ消費量のグラフを表示します、

```
valgrind --tool=massif --time-unit=B --stacks=yes ./SampleM
ms_print massif.out.pid
```

## 実行結果
* ピーク時に、約82.96KB のメモリが使用されています。
* また、ヒープやスタックに割り当てられたまたは解放されたバイトの合計が約3.317MBとのことです。
* 「Number of snapshots」ではヒープやスタックの推移が表示されています。48番目がピークです。

<details><summary>Massif</summary><div>

```
--------------------------------------------------------------------------------
Command:            ./SampleM
Massif arguments:   --time-unit=B --stacks=yes
ms_print arguments: massif.out.9470
--------------------------------------------------------------------------------


    KB
82.96^                                                                ##      
     |                                                                # ::::  
     |                                                                # ::::  
     |                                                       :::::::::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
     |                                                       ::: :: ::# ::::: 
   0 +----------------------------------------------------------------------->MB
     0                                                                   3.317

Number of snapshots: 55
 Detailed snapshots: [2, 48 (peak)]

--------------------------------------------------------------------------------
  n        time(B)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  0              0                0                0             0            0
  1         83,280            3,712                0             0        3,712
  2        134,240            1,328                0             0        1,328
00.00% (0B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.

--------------------------------------------------------------------------------
  n        time(B)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  3        199,968            1,136                0             0        1,136
  4        296,704            1,328                0             0        1,328
  5        352,768            1,328                0             0        1,328
  6        422,848            1,328                0             0        1,328
  7        517,456            1,328                0             0        1,328
  8        585,848            1,176                0             0        1,176
  9        627,720            1,432                0             0        1,432
 10        694,312            1,416                0             0        1,416
 11        762,088            1,384                0             0        1,384
 12        838,552            1,368                0             0        1,368
 13        906,328            1,400                0             0        1,400
 14        974,256            1,584                0             0        1,584
 15      1,067,512            1,400                0             0        1,400
 16      1,130,512            1,328                0             0        1,328
 17      1,193,584            1,328                0             0        1,328
 18      1,256,656            1,328                0             0        1,328
 19      1,319,728            1,328                0             0        1,328
 20      1,382,800            1,328                0             0        1,328
 21      1,445,872            1,328                0             0        1,328
 22      1,508,944            1,328                0             0        1,328
 23      1,572,016            1,328                0             0        1,328
 24      1,635,088            1,328                0             0        1,328
 25      1,698,160            1,328                0             0        1,328
 26      1,761,232            1,328                0             0        1,328
 27      1,824,304            1,328                0             0        1,328
 28      1,911,904            1,328                0             0        1,328
 29      1,967,968            1,328                0             0        1,328
 30      2,024,032            1,328                0             0        1,328
 31      2,080,096            1,328                0             0        1,328
 32      2,136,160            1,328                0             0        1,328
 33      2,192,224            1,328                0             0        1,328
 34      2,248,288            1,328                0             0        1,328
 35      2,304,352            1,408                0             0        1,408
 36      2,360,496            1,328                0             0        1,328
 37      2,416,696            1,176                0             0        1,176
 38      2,472,856            1,144                0             0        1,144
 39      2,529,208            1,176                0             0        1,176
 40      2,585,272            1,624                0             0        1,624
 41      2,683,960           72,920           72,704             8          208
 42      2,743,880           73,336           72,704             8          624
 43      2,799,960           73,352           72,704             8          640
 44      2,856,080           73,392           72,704             8          680
 45      2,912,176           74,720           72,704             8        2,008
 46      2,996,696           74,392           72,704             8        1,680
 47      3,052,760           73,832           72,704             8        1,120
 48      3,135,528           84,952           82,392            40        2,520
96.99% (82,392B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->85.58% (72,704B) 0x48FAC19: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
| ->85.58% (72,704B) 0x4011B89: call_init.part.0 (dl-init.c:72)
|   ->85.58% (72,704B) 0x4011C90: call_init (dl-init.c:30)
|     ->85.58% (72,704B) 0x4011C90: _dl_init (dl-init.c:119)
|       ->85.58% (72,704B) 0x4001139: ??? (in /usr/lib/x86_64-linux-gnu/ld-2.31.so)
|         
->09.64% (8,192B) 0x495FDD3: std::basic_filebuf<char, std::char_traits<char> >::_M_allocate_internal_buffer() (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
| ->09.64% (8,192B) 0x4964006: std::basic_filebuf<char, std::char_traits<char> >::open(char const*, std::_Ios_Openmode) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
|   ->09.64% (8,192B) 0x496493F: std::basic_ifstream<char, std::char_traits<char> >::basic_ifstream(char const*, std::_Ios_Openmode) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
|     ->09.64% (8,192B) 0x109362: main (in /usr/local/bin/valgrind/SampleM)
|       
->01.21% (1,024B) 0x4AD4E83: _IO_file_doallocate (filedoalloc.c:101)
| ->01.21% (1,024B) 0x4AE504F: _IO_doallocbuf (genops.c:347)
|   ->01.21% (1,024B) 0x4AE40AF: _IO_file_overflow@@GLIBC_2.2.5 (fileops.c:745)
|     ->01.21% (1,024B) 0x4AE2834: _IO_new_file_xsputn (fileops.c:1244)
|       ->01.21% (1,024B) 0x4AE2834: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1197)
|         ->01.21% (1,024B) 0x4AD6540: fwrite (iofwrite.c:39)
|           ->01.21% (1,024B) 0x4987783: std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
|             ->01.21% (1,024B) 0x109430: main (in /usr/local/bin/valgrind/SampleM)
|               
->00.56% (472B) in 1+ places, all below ms_print's threshold (01.00%)

--------------------------------------------------------------------------------
  n        time(B)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 49      3,219,624           83,384           82,392            40          952
 50      3,261,536           83,392           82,392            40          960
 51      3,303,408           83,488           82,392            40        1,056
 52      3,345,280           83,312           82,392            40          880
 53      3,387,392           74,624           73,728            16          880
 54      3,477,944            1,544            1,024             8          512
```
</div></details>

# 参考資料
* [Valgrind](https://valgrind.org/)
* [Valgrind User Manual](https://www.valgrind.org/docs/manual/manual.html)