プログラミング言語: Valgrindでメモリエラーを検出したり,プログラムの挙動を調べたり
田浦健次朗

(the page is encoded in UTF-8)
top page

予告

次回(6/27)の授業で,valgrindというツールを使う予定です.その場でインストールに手間取らないよう, 予めインストールしておいてください.

リンク

まずは

使用準備 (インストール)

以下は自分のマシンへインストールする手順です. そうしなくても,全てJupyter内で行うことも原理的には可能です.

Ubuntu (学科PC)

$ sudo apt-get install valgrind

Mac (Homebrew をインストールしている場合)

$ brew install --HEAD valgrind

Mac (MacPorts をインストールしている場合)

$ port install valgrind

Mac (ソースからビルドする場合)

パッチを当てなくてはいけないそうです.以下の手順でできるそうです (少し古い情報なので,今はましになっているかもしれません).
$ curl -O http://valgrind.org/downloads/valgrind-3.9.0.tar.bz2
$ tar xf valgrind-3.9.0.tar.bz2
$ cd valgrind-3.9.0
$ curl "http://bugsfiles.kde.org/attachment.cgi?id=83590" | patch -p0
$ curl "https://trac.macports.org/export/118697/trunk/dports/devel/valgrind/files/patch-compat-snowleo.diff" | patch -p0
$ ./autogen.sh
$ ./configure ## 必要に応じて, --prefix=... を指定
$ make CPPFLAGS=-D__private_extern__=extern
$ make install

Windows

無理です.VMwareなどを利用して,Linux環境を構築してください. 難しい場合は,SSHができる環境を容易しておいて下さい. こちらで準備した環境で演習ができるようにします.

memcheck

Valgrindのデフォルトのツールmemcheckは, 現在アプリケーションに割り当てられている領域を把握し, 割り当てられていない領域へのアクセスや, 未初期化データの利用, メモリリーク(終了時にfreeされていない領域)の検出を行う. もう少し具体的には,memcheckは以下の領域を把握している. そして,それらから外れた領域をアクセスすると, エラーとして検出する.

領域外へのアクセス検出

領域外へのアクセスの例として, スタックの少し外の領域をアクセスしてみよう. 例えば以下のようなプログラムを用いると良い.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char * foo() {
  char a[200];
  strcpy(a, "hello world cup\n");
  return a;
}

int main() {
  char * a = foo();
  char c = a[0];
  printf("a[0] = %c\n", c);
  printf("a = %s\n", a);
  return 0;
}
赤字で示した部分が, 「本来」やってはいけないアクセスである. 普通に走らせるとエラーは出ず, おそらく壊れた文字列が表示される.
$ ./a.out 
a[0] = h
a = hello wo^P
デバッグオプション(-g)をつけてコンパイルし, valgrindで実行し,そのエラーメッセージを解読してみよ.
$ gcc -O0 -g off_stack.c
$ valgrind ./a.out
  ...
注意:

mallocされた領域付近へのアクセス検出

メモリ破壊エラーの中で最もよくあるものが, mallocした領域をはみ出したアクセスおよび, freeした領域へのアクセスである. mallocした領域のすぐ前やすぐ後ろをアクセスするプログラムを書き, memcheckで検出し,エラーメッセージを解読せよ. なお,「mallocした領域をはみだしたアクセス」 といっても,いわゆる配列の添字オーバーフローチェックをやってくれるわけではない.
memcheckがやっているのは,あくまで, 各アドレスが現在割り当て中かどうかを把握し, 割り当て中でない領域へのアクセスを検出だけである. mallocした領域を「はみ出して」アクセスしたその場所が, 偶然割り当て中ということもあり得る. そのような場合のエラーまでは検出できない.

freeされた領域付近へのアクセス検出

前問と同様.だが,mallocして,すでにfreeした領域にアクセスするプログラムを書いてみよ.

未初期化データへのアクセスの検出

memcheckは,ローカル変数・配列や,mallocが返した領域に, 書き込みが一度でも行われたかどうかを管理している. そして,書き込みが行われていない領域を「未初期化領域」 として把握し,未初期化領域を元に計算された値で,条件分岐が行われたり, 未初期化領域がI/Oによって書き出されたりすることを検出する. 例えば以下のようなプログラムで,
#include <stdio.h>
#include <stdlib.h>

int main() {
  double * p = malloc(sizeof(double) * 10);
  if (p[0] < 1) {
    printf("p[0] < 1\n");
  } else {
    printf("p[1] >= 1\n");
  }
  return 0;
}
p[0]が,mallocされて以降, 一度も値がかかれずに読み出されている, したがって, if (p[0] < 1) ... という文が,「初期化されていない値を元にした条件分岐」 であることを検出する. なお,memcheckは,未初期化データを読みだしたり, それを他の変数に入れただけではエラーとはしない. それがプログラムの制御に影響を及ぼしたり, その値がプログラムの外に出力されるときにエラーを出す.

メモリリークの検出

memcheckはプログラム終了時に,leakした領域 = mallocされ, freeされていない領域を報告してくれる.(valgrind出力の, HEAP SUMMARY, LEAK SUMMARYというセクション). また,--leak-check=full という オプションで,leakしたブロックがどこで割り当てられたものかも表示してくれる.
領域をleakさせるプログラムを書いて,memcheckして, エラーメッセージを表示してみよ.

callgrind

Valgrindは,プログラムの命令列中に新しい命令を挿入できる, binary instrumentation frameworkで,実はmemcheckはその一つの応用に過ぎない. callgrindは,プログラムのcallgraph (関数の間の呼び出し関係), cacheミス率,分岐予測ミス率などを表示するツールである.

キャッシュシミュレーション

ここではcallgrindをキャッシュシミュレーションのツールとして用いる.
使い方:
$ valgrind --tool=callgrind --cache-sim=yes command
実行例:
$ valgrind --tool=callgrind --cache-sim=yes hostname
==1303== Callgrind, a call-graph generating cache profiler
==1303== Copyright (C) 2002-2013, and GNU GPL'd, by Josef Weidendorfer et al.
==1303== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==1303== Command: hostname
==1303== 
--1303-- warning: L3 cache found, using its data for the LL simulation.
==1303== For interactive control, run 'callgrind_control -h'.
nanamomo
==1303== 
==1303== Events    : Ir Dr Dw I1mr D1mr D1mw ILmr DLmr DLmw
==1303== Collected : 205077 51545 21116 914 2820 660 905 2107 598
==1303== 
==1303== I   refs:      205,077
==1303== I1  misses:        914
==1303== LLi misses:        905
==1303== I1  miss rate:    0.44%
==1303== LLi miss rate:    0.44%
==1303== 
==1303== D   refs:       72,661  (51,545 rd + 21,116 wr)
==1303== D1  misses:      3,480  ( 2,820 rd +    660 wr)
==1303== LLd misses:      2,705  ( 2,107 rd +    598 wr)
==1303== D1  miss rate:     4.7% (   5.4%   +    3.1%  )
==1303== LLd miss rate:     3.7% (   4.0%   +    2.8%  )
==1303== 
==1303== LL refs:         4,394  ( 3,734 rd +    660 wr)
==1303== LL misses:       3,610  ( 3,012 rd +    598 wr)
==1303== LL miss rate:      1.2% (   1.1%   +    2.8%  )
また,callgrind.out.pidというファイルができる. そのファイルの先頭には,シミュレートされたキャッシュの構成が書かれている.
$ head -20 callgrind.out.1320 
version: 1
creator: callgrind-3.10.0.SVN
pid: 1320
cmd:  hostname
part: 1


desc: I1 cache: 32768 B, 64 B, 8-way associative
desc: D1 cache: 32768 B, 64 B, 8-way associative
desc: LL cache: 4194304 B, 64 B, 16-way associative

desc: Timerange: Basic block 0 - 49169
desc: Trigger: Program termination

positions: line
events: Ir Dr Dw I1mr D1mr D1mw ILmr DLmr DLmw
summary: 205080 51545 21116 915 2820 660 906 2107 598

  ...
例えばこの出力(青字部分)から, という構成がシミュレートされたことがわかる.
なお,このキャッシュ構成は実際に動かしているCPUを元に自動的に 決められているが,レベル数は2と決まっている.学科PCを含め,最近の多くのCPUは, 3レベルのキャッシュを搭載する.上記では,実際のCPUのレベル2キャッシュが省略され, レベル1とレベル3がシミュレートされている.
また,callgrindがやっていることは, あくまでプログラムがアクセスしたアドレスの系列から, キャッシュミス率をシミュレートしていることであり, 実際にCPUが起こしたキャッシュミス数を取得するような, いわゆるプロファイラとは異なる. したがって,CPUが実際に用いているキャッシュ置換のアルゴリズム, プリフェッチのかけ方などが異なって, 実際のCPUとはずれた値が出てくる可能性もある. 一方で結果は決定的で,キャッシュの構成を手動で変更することもできるという利点がある.

キャッシュミス率の把握とシミュレーション: 基本

キャッシュミス率を定量的に把握するため, 単純なプログラムを書いてそのキャッシュミス率を予測, そしてシミュレートしてみよう. このプログラムは,
$ gcc -O3 scan.c
$ ./a.out n s N
として起動すると以下の動作をする.
このときにキャッシュミスを何回おこすか(または同じことだが, キャッシュミス率), それが,n, sに応じてどのように変わるかを自分で予想, そしてcallgrindでシミュレートしてみよ.
nsD1ミス数
48064
51264
54464
57664

キャッシュミス率の把握とシミュレーション: 中級

キャッシュミスについて理解しているかどうかを確かめる ひとつの方法は,このようなプログラムで, キャッシュミスがほぼ0からほぼ1に急激にかわる領域を問うてみることである. 前問の内容を消化して,以下の問いに答えよ.
s=64で,nを変えた時,LLミス数が非常に小さい (最初にアクセスした時以外ほぼミスをしていないと思われる) 最大のn (= mとする)と,LLミス率がほぼNになる(ほぼ毎回ミスをしていると思われる) 最小のn (= Mとする)をそれぞれ予想し,実際にそうなるか確かめてみよ.
つまり,以下の表のmおよびMを求めよ.
nsLLミス数
<=m64
>=M64ほぼN

キャッシュミス率の把握とシミュレーション: 発展1

ストライドs=1024としてnをある値(= mとする) から一つずつ大きくしていくと, キャッシュミス数はほぼ0からほぼNまで,急激に増加した. mを求めよ.自分で予想した上で実験で確かめよ.
つまり,以下の表のmを求めよ.
nsD1ミス数
m 1024
m+11024
m+21024
m+31024
m+41024ほぼN

キャッシュミス率の把握とシミュレーション: 発展2

sもいろいろ変えて, 「キャッシュミス率がほぼ1になるような」n, sの組み合わせの中で, nがなるべく小さいものを,D1およびLLそれぞれに対して見つけよ.
つまり,以下の表のn1, s1, n2, s2 (n1, n2はなるべく小さいもの)を求めよ.
nsD1ミス数LLミス数
n1 s1ほぼN
n2 s2
ほぼN

先読み

一般的にnが大きくなってアクセスされるデータがキャッシュをはみ出すようになるとキャッシュミス率は悪くなるが, プロセッサはそれを緩和する機構として先読みという機構を備えている. 具体的には,まさにこのプログラムのように, 一定の幅(ストライド)でデータをアクセスする場合に, この先アクセスされるデータを前もってキャッシュに入れるようにする. なお,普通,先読みはレベル2, レベル3キャッシュに対して行われ, レベル1キャッシュに対する先読みは行われないようである. callgrindにはこの効果をシミュレートするオプションとして, --simulate-hwpref=yesというオプションがある. D1, LLのキャッシュミス率が大きくなるような設定で, このオプションを適用して,キャッシュミス率の変化を見てみよ. また,プログラムを変更して,先読みの効果がない (--simulate-hwpref=yesを指定しても, キャッシュミス率が減らない)ようにしてみよ. オプションとして,LLキャッシュミス率が大きな場合と,ほぼ0の場合で, どのくらい性能が違うか測定してみよ.

チャレンジ問題

ここに, gnuplotプログラムのソースコードに,わざとバグを注入したものがある. valgrind (memcheck)とgdbを用いてこのプログラムのバグを発見・修正せよ.
手順: チャレンジ: