kivantium活動日記

プログラムを使っていろいろやります

C/C++でのメモリリーク検出方法 〜AddressSanitizer, Valgrind, mtrace〜

C/C++でプログラムを書いているときに遭遇する厄介なバグの一つがメモリリークです。
今回はメモリリークを検出するのに使えるツールの使い方について書きます。

AddressSanitizer

コンパイルオプションをつけるだけで使えて出力も見やすいのでおすすめです。

AddressSanitizerはGCC 4.8以降かLLVM 3.1以降で使うことができます。
コンパイル時にオプションをつけるだけでメモリリークを検出してくれます。(若干実行時間が長くなります)

以下のメモリリークのあるプログラム leak.cpp を例に使い方を説明します。

int main() {
  int *a = new int[10];
}

newで作った動的配列をdeleteしていないのでメモリリークになります。

g++ -fsanitize=address -fno-omit-frame-pointer -g leak.cpp
./a.out

のようにオプションをつけてコンパイルして実行すると以下のような出力を得ます。(clangの場合もオプションは同じです)

=================================================================
==6027==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 40 byte(s) in 1 object(s) allocated from:
    #0 0x7f606cd7a6b2 in operator new[](unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x996b2)
    #1 0x4006f7 in main /home/kivantium/leak.cpp:2
    #2 0x7f606c93782f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: 40 byte(s) leaked in 1 allocation(s).

leak.cppの2行目のメモリリークの存在が分かりました。

詳細はAddressSanitizer · google/sanitizers Wiki · GitHubが詳しいです。

Valgrind

仮想機械の上でプログラムを実行することでメモリリークの検出などを行うツールです。実行ファイルだけあれば使える点が便利ですが、実行はけっこう遅くなります。

インストールは基本的には

sudo apt install valgrind

でできるはずですが、僕の環境ではlinux-tools-4.13.0-45-genericのインストールも必要でした。

int main() {
  int *a = new int[10];
}

をValgrindでチェックするには、

g++ -g leak.cpp
valgrind --leak-check=full ./a.out

を実行します。結果は、

==6911== Memcheck, a memory error detector
==6911== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==6911== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==6911== Command: ./a.out
==6911== 
==6911== 
==6911== HEAP SUMMARY:
==6911==     in use at exit: 72,744 bytes in 2 blocks
==6911==   total heap usage: 2 allocs, 0 frees, 72,744 bytes allocated
==6911== 
==6911== 40 bytes in 1 blocks are definitely lost in loss record 1 of 2
==6911==    at 0x4C2E80F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6911==    by 0x400607: main (leak.cpp:2)
==6911== 
==6911== LEAK SUMMARY:
==6911==    definitely lost: 40 bytes in 1 blocks
==6911==    indirectly lost: 0 bytes in 0 blocks
==6911==      possibly lost: 0 bytes in 0 blocks
==6911==    still reachable: 72,704 bytes in 1 blocks
==6911==         suppressed: 0 bytes in 0 blocks
==6911== Reachable blocks (those to which a pointer was found) are not shown.
==6911== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==6911== 
==6911== For counts of detected and suppressed errors, rerun with: -v
==6911== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

のようになり、2行目にメモリリークがあることが分かります。

他にも機能があるようなので機会があったら追記します。

mtrace

メモリリークの位置を絞って探すときに使えます。glibcに入っているので使える環境が多いですが出力が見にくいです。

mtraceを使うにはmcheck.hをインクルードして、調べる範囲にmtrace()muntrace()を書く必要があります。

例としては

#include <stdlib.h>
#include <mcheck.h>
 
int main() {
  mtrace();
  int *a = (int*) malloc(sizeof(int)*10);
  muntrace();
}

のようになります。

実行するには

gcc -g leak.c
export MALLOC_TRACE=./mtrace.log
./a.out
mtrace a.out mtrace.log

のようにログ出力先を環境変数に指定したあとにプログラムを実行し、バイナリとログファイルを引数に与えてmtraceを実行します。

出力は

Memory not freed:
-----------------
           Address     Size     Caller
0x0000000001456450     0x28  at /home/kivantium/leak.cpp:6

のようになります。

C++

#include <mcheck.h>
 
int main() {
  mtrace();
  int *a = new int[10];
  muntrace();
}

のように書いた場合、出力は

Memory not freed:
-----------------
           Address     Size     Caller
0x00000000008b5060     0x28  at 0x7fe1589bbe78

のようになってしまい、どの行が問題だったのか分かりません。addr2lineを使って

addr2line -e a.out 0x7fe1589bbe78

とすればどの行か分かる場合もあるようですが、僕の環境では分かりませんでした。
C++ではかなり使いにくいようです……

2018年6月



読んだ本

The Three-Body Problem

The Three-Body Problem

非常に人気のある中国SF。原題は三体 (Wikipedia)。ヒューゴー賞などを受賞しているが、まだ日本語訳が出ていないため英語版で読んだ。

私の百合はお仕事です! 3 (百合姫コミックス)

私の百合はお仕事です! 3 (百合姫コミックス)

どんどん弱っていくくるみちゃんが見ていてつらい。
量子コンピュータと量子通信〈1〉量子力学とコンピュータ科学 (量子コンピュータと量子通信 1)

量子コンピュータと量子通信〈1〉量子力学とコンピュータ科学 (量子コンピュータと量子通信 1)

カドラプロのおすすめ。量子ゲートなどの具体例から入るので他の本よりも分かりやすかった。2巻から急に難しくなって全然読めていない。
工学のための関数解析 (工学のための数学)

工学のための関数解析 (工学のための数学)

前原さんのおすすめ。行間が狭いところは良いが、紹介された新しい概念の工学での使い所がいまいち分からなかった。
お兄ちゃんはおしまい! (IDコミックス)

お兄ちゃんはおしまい! (IDコミックス)

科学者の妹に女の子にされたお兄ちゃんの話。お兄ちゃんがかわいい。

制約付き最適化問題をD-Waveと同じ方法で解く

まだ古典コンピュータで消耗してるの?

イジングモデルとQUBO

D-Waveが提供しているのは量子アニーリングを使った量子コンピュータです。
量子アニーリング方式では次の形の最適化問題を高速に解くことができます。
 {\displaystyle \text{min.}\ \sum_{i \lt j} J_{ij} s_{i} s_{j} - \sum_{i=1}^{N} h_i s_i }
ここで J_{ij}, h_{i} \in \mathbb{R} s_i \in \{1, -1\}です。

1と-1よりは0と1の方が扱いやすいので、 x_i = (s_i+1)/2と変数変換して得られる以下のQUBO (Quadratic unconstrained binary optimization) という形に変形してから使うことが多いようです。
 {\text{min. } \displaystyle \sum_{i=1}^{N} c_i x_i + \sum_{i=1}^{N} \sum_{j=1}^{i} q_{ij} x_i x_j }

制約付き最適化問題とQUBO

QUBOでは変数間の制約がありませんでしたが、実際には  x_1+x_2=1 のような制約が必要になることがあります。
その場合、最適化したい関数 f(x)と十分大きい \lambda > 0を使って
 {\displaystyle \text{min.} f(x) + \lambda (x_1+x_2-1)^2 }
を解けば、(実行可能解が存在するなら)最小値を取るときには自動的に制約が満たされることになるので、QUBOの形で制約付き最適化問題が解けることになります。
なお、QUBOには x_i^2 の項がありませんが、 x_i は0または1なので  x_i^2=x_i が成り立ち、2乗の項が出てきてもQUBOの形に変形することができます。

qbsolv

qbsolv はD-Waveが開発しているQUBOのソルバです。
設定すればD-Waveの実機上でも動かせるようですが、デフォルトではローカル環境でのシミュレーションを使って解く設定になっているようです。
ここではコマンドライン環境を使います。

コンパイル

git clone https://github.com/dwavesystems/qbsolv.git
cd qbsolv
mkdir build; cd build
cmake ..
make

qbsolvは.quboファイルを読み込んでその解を出力します。
.quboファイルの仕様は以下の通りです。(READMEより引用)

qbsolv "qubo" input file format

   A .qubo file contains data which describes an unconstrained
quadratic binary optimization problem.  It is an ASCII file comprised
of four types of lines:

1) Comments - defined by a "c" in column 1.  They may appear
    anywhere in the file, and are otherwise ignored.

2) One program line, which starts with p in the first column.
    The program line must be the first non-comment line in the file.
    The program line has six required fields (separated by space(s)),
    as in this example:

  p   qubo  topology   maxNodes   nNodes   nCouplers

    where:
  p         the problem line sentinel
  qubo      identifies the file type
  topology  a string which identifies the topology of the problem
            and the specific problem type.  For an unconstrained problem,
            target will be "0" or "unconstrained."   Possible, for future
            implementations, valid strings might include "chimera128"
            or "chimera512" (among others).
  maxNodes   number of nodes in the topology.
  nNodes     number of nodes in the problem (nNodes <= maxNodes).
            Each node has a unique number and must take a value in the
            the range {0 - (maxNodes-1)}.  A duplicate node number is an
            error.  The node numbers need not be in order, and they need
            not be contiguous.
  nCouplers  number of couplers in the problem.  Each coupler is a
            unique connection between two different nodes.  The maximum
            number of couplers is (nNodes)^2.  A duplicate coupler is
            an error.

3) nNodes clauses.  Each clause is made up of three numbers.  The
            numbers are separated by one or more blanks.  The first two
            numbers must be integers and are the number for this node
            (repeated).  The node number must be in {0 , (maxNodes-1)}.
            The third value is the weight associated with the node, may be
            an integer or float, and can take on any positive or negative
            value, or zero.

4) nCouplers clauses.  Each clause is made up of three numbers.  The
            numbers are separated by one or more blanks.  The first two
            numbers must be different integers and are the node numbers
            for this coupler.  The two values (i and j) must have (i < j).
            Each number must be one of the nNodes valid node numbers (and
            thus in {0, (maxNodes-1)}).  The third value is the strength
            associated with the coupler, may be an integer or float, and can
            take on any positive or negative value, but not zero.  Every node
            must connect with at least one other node (thus must have at least
            one coupler connected to it).

Here is a simple QUBO file example for an unconstrained QUBO with 4
nodes and 6 couplers.  This example is provided to illustrate the
elements of a QUBO benchmark file, not to represent a real problem.

        | <--- column 1
        c
        c  This is a sample .qubo file
        c  with 4 nodes and 6 couplers
        c
        p  qubo  0  4  4  6
        c ------------------
        0  0   3.4
        1  1   4.5
        2  2   2.1
        3  3   -2.4
        c ------------------
        0  1   2.2
        0  2   3.4
        1  2   4.5
        0  3   -2
        1  3   4.5678
        2  3   -3.22

最短路問題をQUBOで解く

制約付き最適化問題の例として、最短路問題をQUBOに変換して解きます。
良い子のみんなはダイクストラなどを使いましょう。

f:id:kivantium:20180617163419p:plain
今回考えるグラフ

最短路問題を最適化問題として解く時は、辺  e_i を通るときは  x_i=1、通らない時は  x_i=0 として、重みの和  \sum w_i x_i が最小になるようにする問題と見ます。( w_i は辺  e_i の重み)
これだけだと何も辺を選ばないのが最適になってしまうので、辺の選び方が経路になるように各頂点に制約を加えます。

  •  v_0 からは1辺が出ていくので  x_0 + x_2 = 1
  •  v_1 に入って来る辺の数と出て行く辺の数は等しいので  x_0 - x_1 = 0
  •  v_2 には1辺が入ってくるので  x_1 + x_2 = 1

 (w_0, w_1, w_2) = (1, 1, 3) とすると、この最短路問題を解くためのQUBOは、
 {\displaystyle \text{min. } x_0 + x_1 + 3x_2 + \lambda \{(x_0+x_2-1)^2 + (x_0-x_1)^2+(x_1+x_2-1)^2\} }
となります。
 \lambda=100として、 x_i^2=x_iに気をつけながら変形すると
 {\displaystyle \text{min. } x_0 + x_1 +  (-197)x_3 + (-200) x_0x_1+200x_0x_2+200x_1x_2 }
となります。(間違ってたらごめんなさい)

これを.quboファイルにすると

p  qubo  0  3  3  3
c ------------------
0  0   1
1  1   1
2  2   -197
c ------------------
0  1   -200
0  2   200
1  2   200

となります。

./qbsolv -i test.qubo

のように実行すると

3 bits,  find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec
110
-198.00000 Energy of solution
0 Number of Partitioned calls, 1 output sample 
 0.02363 seconds of classic cpu time

となり、 (x_0, x_1, x_2) = (1, 1, 0) という正しい答えが得られました。

 w_0=3にすると答えが

3 bits,  find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec
001
-197.00000 Energy of solution
0 Number of Partitioned calls, 1 output sample 
 0.02023 seconds of classic cpu time

に変わるので正しそうな挙動をしています。

2018年5月

5月はとても忙しかったのに特に進捗がなくてつらい

IguanaTex

  • LaTeX記法で数式を書くためのアドイン

IguanaTex - A Free Latex Add-In for PowerPoint on Windows

OBS Studio

  • YouTubeなどで生放送をするのに使えるソフト

Open Broadcaster Software | ホーム

Bulma

CSSフレームワーク。Bootstrapっぽくないものを作りたいと言ったら教えてもらった。

ナミキ商事

化合物データベースが充実しているらしい?

その他



Open Babelのビルドとインストール

Open Babel は化学で使われる分子フォーマット間の変換によく使われるソフトです。

開発されたばかりの機能を使うためには自分でビルドしてインストールする必要があるのですが、Pythonバインディングコンパイルするところにハマったのでメモしておきます。 基本的にはInstall Open Babelを見ればいいです。 環境はUbuntu 16.04を使いました。

必要なライブラリのインストール

sudo apt install cmake python3-dev libxml2-dev zlib1g-dev libeigen2-dev libcairo2-dev

ビルドとインストール

git clone https://github.com/openbabel/openbabel.git
cd openbabel
mkdir build
cd build
cmake .. -DPYTHON_BINDINGS=ON
make
sudo make install
echo 'export PYTHONPATH=/usr/local/lib:$PYTHONPATH' >> ~/.bashrc
source ~/.bashrc

pythonを起動して import pybel を実行してエラーが起きなければ成功です。

問題点

この方法でインストールできるのはaptで入れたpython 2.7だけで、Python 3やpyenvで入れたPythonではリンクに失敗します。 General discussion - OpenBabel for Python 3?Python 3向けにインストールする方法が書いてありますが、今のところうまくいっていません。 成功したら追記します。

C++で使う

インストールすると obabelなどの通常のコマンドラインツールが使えるようになります。

より複雑なことをするにはC++Pythonなどでコードを書くことになります。 以下に標準入力からSMILESを読んで、3次元座標を計算した後、標準出力にSDFを吐くコード例を示します。 エラー処理は省略しています。

#include <iostream>

#include <openbabel/mol.h>
#include <openbabel/obconversion.h>
#include <openbabel/builder.h>

int main(int argc,char **argv) {
    OpenBabel::OBConversion conv(&std::cin, &std::cout);
    OpenBabel::OBMol mol;
    OpenBabel::OBBuilder builder;

    conv.SetInAndOutFormats("SMI", "SDF");
    conv.Read(&mol);
    builder.Build(mol);
    conv.Write(&mol);
}

コンパイルは以下のように行います。ディレクトリは環境によって異なるかもしれません。

g++ -I /usr/local/include/openbabel-2.0/  -L /usr/local/lib/openbabel/2.4.90/ hoge.cpp  -lopenbabel

Makefileの例を示します。ディレクトリ名は適宜変更してください。

CC = g++
CXXFLAGS = -I /usr/local/include/openbabel-2.0/
LDFLAGS = -L /usr/local/lib/openbabel/2.4.90/
LDLIBS = -lopenbabel

all: hoge fuga

SMILESをstringで指定する例

#include <iostream>
#include <string>
#include <sstream>

#include <openbabel/mol.h>
#include <openbabel/obconversion.h>
#include <openbabel/builder.h>

int main(int argc, char** argv){
  std::string smiles = "FCl(=O)=O";
  std::stringstream ss(smiles);
  OpenBabel::OBConversion conv(&ss, &std::cout);
  conv.SetInAndOutFormats("smi", "sdf");
  OpenBabel::OBMol mol;
  conv.Read(&mol);

  OpenBabel::OBBuilder builder;
  builder.Build(mol);

  conv.Write(&mol);
}

2018年4月後半

何もしないうちに4月が過ぎ去ろうとしている……

書いたもの

RVM の特許回避について


その他






リズと青い鳥」感想

タイムラインでの評判が非常に良かったので見てきました。
ネタバレですが、別にネタバレして面白さが失われる映画というわけでもないと思います。

時系列はユーフォ2期の続きで、鎧塚先輩とフルートの人の話です。
ユーフォ2期では何も言わずに部活やめておきながら今さら戻ってくるなんて、みたいな僕としてはどうでもいいことを問題にしていたのであまり面白く思えませんでした。
この映画では自分の道を歩んでいくことが最も良いと決断できるようになった過程をきれいに描いていて良かったです。

友情・愛情をテーマにした作品には自分の自己実現を犠牲にして相手と一緒にいることを選ぶものが多くて自分としては腑に落ちませんでした。
この作品では、相手と離れることになったとしても自己実現することが相手を大事にすることなのだという結論を出していて大変納得できました。

結局ぼくは自己実現の欲求の追求を価値あるものだと思っていて、人間関係の欲求を重視していないのでしょう。
欲求が満たされない初期状態にいる主人公が物語内での行動を通して欲求を満たしていくところを自分に重ね合わせることで自分も満足するというのが物語の一つの楽しみかたなのだと思います。(いま考えた)
バトルものやパニックものでは安全の欲求、恋愛ものでは社会欲求と愛の欲求(欲求段階説)、というように満たされない欲求はジャンルによって異なります。
安全欲求が満たされるものはそれだけで十分なのですが、自分には愛の欲求が薄いのでそれが満たされただけで終了してしまう作品はいまいちだと感じるのかもしれません。

ユーフォでは高坂麗奈さんが好きなのですが、それはまさにトランペットを通して自己実現をしようとしているからなのでしょう。
この映画ではよりよい音楽のために先輩であっても容赦なく指摘していくシーンや、オーボエの演奏が遠慮していると言った後に見せつけるようにトランペットを吹くシーンがとても良かったです。

arXivのリンクを貼ったら展開するSlack bot

Slackにはリンクを貼ったときに展開 (unfurl) する機能があります。
f:id:kivantium:20180418193058p:plain

この展開はリンクが貼られたときにoEmbedサーバー, Twitterカード/Facebook Open Graph, HTML metaタグの順に見にいくことで行われています
しかし、arXivにはその情報がないのでリンクを貼っても展開されません。

そこでリンクを貼ったら展開するSlackボットを作りました。

仕組み

SlackのReal Time Messaging APIを使ってメッセージを監視しておき、arxivへのリンクが貼られたら情報を取得して、Slackのattachmentという機能でタイトルとabstractの最初の140文字を取得してそれっぽく表示します。

使い方

https://slack.com/apps/A0F7YS25R-bots から自分のワークスペースに新しいbotを作成してAPI Tokenを下のコードの伏せ字になっている部分にコピペします。
必要なチャンネルにbotをinviteしておき、下のコードを実行しておくとarxivのリンクが貼られたときに展開してくれます。サーバーとかでずっと動かしておいてください。
f:id:kivantium:20180418200140j:plain

gist.github.com

bot名が表示されてほしくないんだけど

わかる。

Twitterの展開みたいな展開を行うためにはEvents APIをサポートするAppを作る必要があるのですが、そのためにはリンクが貼られたときにSlackがそのイベントを送信するURLを用意する必要があってとても面倒くさいのでやめました。

頑張りたい人は
api.slack.com
を読んでください。

特定商取引法に定められた事項は請求により遅滞なく提供する