Yoichi Kawasaki blog

Ubuntu 9.10 on my Dell XPS M1210

March 27th, 2010

Vista on Dell XPS M1210（CeleronM,1GMEM）というサイテーに遅いOSの上でvmwareやcolinuxを通じてLinuxを動かしているとそのあまりの遅さに端末を捨ててしまいたくなる衝動にかられていた。なのでたまにTV見ながら膝上に乗せて遊んであげていたけどその遅さ故に使うことが憚られその存在は忘れがちに。そこで試しに入れてみたUbuntu 9.10。デュアルブートではなく男らしくフルUbuntu。 Hibernateも問題なく動作しているしサクサク動いて快適。よみがえったよXPS M1210。

Posted in: Random / ランダムな話

Tags: colinux, dell, linux, ubuntu, vmware

簡単Boehm GCによるC/C++メモリリーク検知

No comments

yoichi

March 25th, 2010

Boehm GCはガベージコレクションの標準実装がないC/C++でガベージコレクションのようなことを実現可能にしてくれるライブラリ。一度確保されたリソースは明示的に解放処理が行われない限りメモリリークが発生してしまうけれどもBoehm GCで用意されている関数群（通常はGC_MALLOC）を使ってリソースを確保すれば不要になった段階で自動的に解放してくれる。ソースコード全体で統一してこのライブラリを利用していればオブジェクトの寿命管理の手間は減るだろうし自分がコードの責任者であるならば難しいところを枯れたライブラリにお任せできるので安心感はあるのだろう。ちなみにこのライブラリ、以前からその存在は知ってはいたけれどスマートポインタ派の自分としてはオブジェクトの寿命管理のためにこれを使うモチベーションはいまいち感じられない。

そんなBoehm GCは「Using the Garbage Collector as Leak Detector」で紹介されているようにメモリリーク検知用ユーティリティとしても使える。ドキュメントやソースコードを覗いてみて少し工夫すれば手軽に既存のコードに殆ど手を加えること無くメモリリークの検知ができそうだったので試しにサンプルコードを書いてみた。以下、Boehm GCのインストールからC/C++コードでのメモリリーク検知について。

Boehm GCインストール

まずは自分の環境(debina5.0.1″lenny”)にBoehm GCをインストールしてみる。 Boehm GCライブラリをつかって開発するにはlibgc-devとlibgc1c2が必要。もし自分の環境に合うパッケージが存在しない場合は直接ここから tar.gzボールをダウンロードして例のconfigure、make、make install。

$ sudo apt-get install libgc-dev
$ sudo apt-get install libgc1c2
$ dpkg --list |grep libgc
ii libgc-dev 1:6.8-1.1 conservative garbage collector for C (develo
ii libgc1c2 1:6.8-1.1 conservative garbage collector for C and C++

**Cコードメモリリーク検知 – *alloc/freeをGC_関数に置換**

Boehm GCにはGC_MALLOC等のリソース確保系関数でリソース確保されたにもかかわらずGC_FREE等の解放系関数でリソース解放されずにリークしてしまっているオブジェクトを検知してそれらをレポートする機能がある。このメモリリーク検知レポートはGC_gcollect関数で実行される。ただしこのときメモリリーク検知レポート機能をオンにするためにはそもそもBoehm GC を-DFIND_LEAKオプションでコンパイルするか、または実行時にダイナミックにGC_find_leak=1をセットしてやる必要がある。

対象オブジェクト: GC_MALLOC等でリソース確保されたにもかかわらずGC_FREE等で解放されないオブジェクト
検知レポート実行関数： GC_gcollect
前提条件： -DFIND_LEAKオプションでコンパイルされたBoehmGC or 実行時にGC_find_leak=1をセット

「Using the Garbage Collector as Leak Detector」ではこのメモリリーク検知レポート機能を利用して実際のCコードのメモリリークを検知するために直接ヒープからメモリ確保、解放を行うための基本関数をBoehmGCの関数で置き換えるためのヘッダを用意している。

gc_detect_leaks.h

#define GC_DEBUG
#include "gc.h"
#define malloc(n) GC_MALLOC(n)
#define calloc(m,n) GC_MALLOC((m)*(n))
#define free(p) GC_FREE(p)
#define realloc(p,n) GC_REALLOC((p),(n))
#define CHECK_LEAKS() GC_gcollect()

試しにメモリリークを引き起こすコードに上記ヘッダをインクルードしたサンプルコード(t1.c)を用意してコンパイル+ 実行してみる。
サンプルコード: t1.c

#include <stdio.h>
#include "gc_detect_leaks.h"
int main() {
GC_find_leak = 1;
char *a;
while(1){
a = (char*)malloc(100);　　// t1.c: line7
//free(a);
CHECK_LEAKS();
}
}

[コンパイルと実行結果]
$ gcc -g -Wall t1.c -o t1 -I/usr/include/gc -L/usr/lib -lgc
$ ./t1
Leaked composite object at 0x805af90 (t1.c:7, sz=100, NORMAL)
Leaked composite object at 0x805af10 (t1.c:7, sz=100, NORMAL)
Leaked composite object at 0x805af90 (t1.c:7, sz=100, NORMAL)
...

無事メモリリークを検知。メモリリークの原因となっている箇所（t1.cの７行目）も特定されているので合格。ちなみに上記ヘッダでGC_DEBUGをdefineしているは理由はgc.hで定義されているGC_MALLOCをデバック用出力にモードにするため。以下gc.hの該当部分だけを略して抜粋。

gc6.8 – /usr/local/gc/gc.h

#ifdef GC_ADD_CALLER
# define GC_EXTRAS GC_RETURN_ADDR, __FILE__, __LINE__
...略...
#else
# define GC_EXTRAS __FILE__, __LINE__
...略...
#endif

# ifdef GC_DEBUG
# define GC_MALLOC(sz) GC_debug_malloc(sz, GC_EXTRAS)
... 略...
# else
# define GC_MALLOC(sz) GC_malloc(sz)
...略...
# endif

C++ コードメモリリーク検知 – gc/gc_cleanupクラスで継承

次にC++コードのメモリリーク検知を行う。C++のデータ構造の基本はクラス（細かいことを省けば構造体もクラス）でありクラスはnewオペレーターでメモリを動的に確保する。当然のことながらデフォルトのnewオペレータでリソース確保した場合はGC回収不能であるためBoehm GCが用意しているC++用ライブラリを利用する。gc_cpp.hをみるとこれは単なるCライブラリのラップクラス。以下のようにgcやgc_cleanupクラスをベースクラスとすることでGC回収可能なオブジェクトとして扱うことができる。

サンプルコード: t2.cpp

#include <stdio.h>
#define GC_DEBUG
#include "gc_cpp.h"
#define CHECK_LEAKS() GC_gcollect()
class Foo: public gc{};
int main() {
GC_find_leak = 1;
Foo *f;
while(1){
f =new Foo;　　　// t2.cpp: line10
// delete f;
CHECK_LEAKS();
}
}

[コンパイルと実行結果]
$ g++ -g -Wall t2.cpp -o t2 -I/usr/include/gc -L/usr/lib -lgc
$ ./t2
Leaked composite object at 0x805afe8 (/usr/include/gc/gc_cpp.h:274, sz=1, NORMAL)
Leaked composite object at 0x805afd0 (/usr/include/gc/gc_cpp.h:274, sz=1, NORMAL)
Leaked composite object at 0x805afe8 (/usr/include/gc/gc_cpp.h:274, sz=1, NORMAL)
....

これも無事メモリリーク検知はされている。ただしリーク箇所が/usr/include/gc/gc_cpp.hのL274行目を指している。これではリークの原因箇所がわからない。できればt2.cppのL10行目(f=new Foo)を指してもらいたい。さらにこの方法では単に既存のコードのメモリーリーク検知のみを行いたい場合でも、クラスをgc やgc_cleanupクラスで継承させるといったコードに手を加えていく作業が必要があるのでとても面倒でありコード量が多ければ多いほど手間がかかる。

C++コードメモリリーク検知 – new/deleteオペレータのオーバーロード

そこで既存のコードにあまり手を加えなくてもメモリリーク検知ができ、且つリークの原因箇所を特定できる方法を考えてみた。まずは既存のコードの手を加えないでメモリリーク検知する方法。クラスはリソースの確保、解放をそれぞれnew、 deleteオペレータで行うのでこれらをグローバルにオーバーロードしてやり内部のリソース確保、解放のための実装をGC関数で置き換えてやる。そしてそのヘッダを既存のコードにインクルードしてやれば既存のコードに手を加えないでメモリーリークの検知ができるのではないかと。ヘッダは以下のような感じ。

#define GC_DEBUG
#include "gc.h"
void* operator new(size_t size) {
return GC_MALLOC(size);
}
void* operator new[](size_t size) {
return GC_MALLOC(size);
}
void operator delete(void* p) {
if (p) GC_FREE(p);
}
void operator delete[](void* p) {
if (p) GC_FREE(p);
}

ただしこれだけではメモリリークの検知はできてもリークの原因箇所の特定が難しい。このままだと上記ヘッダのGC_MALLOC()コール箇所がリーク箇所としてレポートされてしまう。理想はnewオペレータをコールしている箇所がレポートされて欲しい。ということで次のように GC_debug_malloc()にnewオペレータコール箇所のファイル名と行を渡すように変更してみる。

gc_detect_leaks.h

#define GC_DEBUG
#include "gc.h"
void* operator new(size_t size, const char * s, int i) {
return GC_debug_malloc(size,s,i);
}
void* operator new[](size_t size, const char * s, int i) {
return GC_debug_malloc(size,s,i);
}
void operator delete(void* p) {
if (p) GC_debug_free(p);
}
void operator delete[](void* p) {
if (p) GC_debug_free(p);
}
# define new new(__FILE__, __LINE__)
# define CHECK_LEAKS() GC_gcollect()
int GC_find_leak = 1;

ためしにメモリリークを引き起こすC++コードに上記ヘッダをインクルードしたものを用意してコンパイル+ 実行してみる。今度はヘッダにint GC_find_leak = 1を含めているのでサンプルコードにGC_find_leak = 1をセットする必要はない。

サンプルコード: t3.cpp

#include <stdio.h>
#include "gc_detect_leaks.h"
class Foo{};
int main() {
Foo *f;
while(1){
f =new Foo; // t3.cpp: line7
// delete f;
CHECK_LEAKS();
}
}

[コンパイルと実行結果]
$ g++ -g -Wall t3.cpp -o t3 -I/usr/include/gc -L/usr/lib -lgc
$ ./t3
Leaked composite object at 0x805afe8 (t3.cpp:7, sz=1, NORMAL)
Leaked composite object at 0x805afd0 (t3.cpp:7, sz=1, NORMAL)
Leaked composite object at 0x805afe8 (t3.cpp:7, sz=1, NORMAL)
...

見事メモリリークを検知しnewオペレータをコールしている行がレポートされた。というわけでこのヘッダをインクルードするだけで他の既存のコードに手を加えることなくメモリリークを検知することができた。

最後に、今回使ったサンプルコードとここで紹介したヘッダを少し体裁を整えてgithubにあげておきました。ちなみにgithubにあげたgc_detect_leaks.hを使う際は-DGC_DETECT_MEM_LEAKでコンパイルすることをお忘れなく。

http://github.com/yokawasa/any/tree/master/boehmgc/

おわり

Posted in: Programming / プログラミング

Tags: boehm, c, cplusplus, debian, debug, gc

ページ置換アルゴリズム(Page Replacement Algorithms)のシュミレーション

No comments

yoichi

March 13th, 2010

システムのオペレーションをやっているとスラッシングが原因でサーバが一時的にサービス提供不能になっていまうなんてことがたまにある。スラッシングとは、例えば大量の処理リクエストが発生してしまい利用可能な物理メモリ量を大きく超えてしまった場合に起ったりする。OSのメモリ割り当て処理（ページアウト・イン）が追いつかないため全体のパフォーマンスが極端に低下、最悪固まってしまいlsすらできなくなる。この記事のタイトルにあるページ置換アルゴリズム（Page Replacement Algorithm）はこのページ割り当てを効率的に行うためのアルゴリズム群のことでどれを選択するかによってパフォーマンスが大きく左右される。ちなみにこのアルゴリズム群はページに限らずキャッシュやメモリプールなど限られたリソースを効率的に割り当てる場合には必ずといっていいくらい登場するものなのでプログラマとしては是非とも押さえておきたいところ。

前置きが少し長くなってきたのでここらで本題に入る。ページ置換アルゴリズムを調べていたときにumassの教材として作られたであろう置換アルゴリズムのシュミレーションツールを見つけた。JavaScript版とJava Applet版の2つ。アルゴリズム学習者にとっては目で見て挙動が確認できるので便利なはず。これ見て自分もなんとなく作ってみたくなったので勉強がてらにcで作ってみた。もちろんCUI。アルゴリズムはLRU、FIFO、OPTIMALの3つに絞った。これがc版ページ置換アルゴリズムシュミレーションツール。

http://github.com/yokawasa/any/raw/master/page_rep_algos/page_rep_algos.c

内容は、見つけたツールと同じで物理メモリのページ・フレームの数、置換アルゴリズム、そして今後メモリ割り当ての必要なページ番号の数列を指定して順番にそのページ番号に対して物理メモリの割り当てを行うといったもの。利用ページ番号が既に物理メモリの割り当てが既にされていればHit、されていなければMiss（ページフォルト発生）として過去に割り当てたページの置き換えを行い、最終的なページフォールト発生数とHit率を出力する。

以下、ツールのコンパイルとその使い方、そして各アルゴリズムの挙動をツールの実行結果とあわせて説明する。

ツールのコンパイルとその使い方

上記URLからソースコードを取得してからコンパイルを行う。

gcc -o page_rep_algos page_rep_algos.c

使い方はアルゴリズム、アクセスするページ番号の数列、ページフレーム数の3つのオプションを次のように指定。

./page_rep_algos [options]
Options are:
-a <アルゴリズム> LRU, FIFO または OPTIMAL
-p <ページ番号列> Page # sequences in which the pages are accessed by some program
in the order. max entry num is 100. (space between each)
-f <フレーム数> The number of page frames. max frame num is 10.
-h Display usage information (this message)

実行例:
./page_rep_algos -a LRU -p "0 1 2 3 2 1 4 3 6 0 9" -f 3

LRU（Least Recently Used）

LRUではその名のとおり「最も長く使われないページ」を置換の対象とする。なのでいつ追加されたということよりも最後にアクセスされてからどれだけ経過しているかを測り最も長いものから置換していく。例えばページフレーム数3でアクセスページ番号列を「0 1 2 3 2 1 4 1 6 0 2 1」とした場合、1つずつトレースすると次のような図になる。Faultとはページフォールト(Page Fault)のことでFaultのない場合はページHitしたことを意味する。

Page Referenceが4の時のページ置換計算を例にする。置換される前の各ページフレームPF[0]、PF[1]、PF[2]にはそれぞれページ番号3、1、2が割り当てられている。ページ番号4がアクセスされるタイミングでページ番号3、1、2がアクセスされていない期間はそれぞれ3、1、2となる。よって最も長くアクセスされていないPF[0](ページ番号3)が置換対象となる。ツールで実行してみると次のとおり。ページフォールトが9回で、Hit率25%。

[kawasaki@debian:~] $ ./page_rep_algos -a LRU -p "0 1 2 3 2 1 4 1 6 0 2 1" -f 3
0: 0 Miss
1: 0 1 Miss
2: 0 1 2 Miss
3: 3 1 2 Miss
2: 3 1 2 Hit
1: 3 1 2 Hit
4: 4 1 2 Miss
1: 4 1 2 Hit
6: 4 1 6 Miss
0: 0 1 6 Miss
2: 0 2 6 Miss
1: 0 2 1 Miss

Number of Page Frames = 3
Total Number of References = 12
Number of Hits = 3
Number of Page Fault = 9
HitRatio = 0.25

FIFO（First-In First-Out）

FIFOもその名のとおり「早く追加されたページ」を置換の対象とする。この場合はLRUと違っていつ追加されたということが重要であり最も早いものから置換していく。
LRUと同くサンプル( ページフレーム数3でアクセスページ番号列を「0 1 2 3 2 1 4 1 6 0 2 1」とした場合、1つずつトレースすると次のような図になる。

ツールで実行してみると次のとおり。ページフォールトが10回で、Hit率17%。

[kawasaki@debian:~] $ ./page_rep_algos -a FIFO -p "0 1 2 3 2 1 4 1 6 0 2 1" -f 3
0: 0 Miss
1: 0 1 Miss
2: 0 1 2 Miss
3: 3 1 2 Miss
2: 3 1 2 Hit
1: 3 1 2 Hit
4: 3 4 2 Miss
1: 3 4 1 Miss
6: 6 4 1 Miss
0: 6 0 1 Miss
2: 6 0 2 Miss
1: 1 0 2 Miss

Number of Page Frames = 3
Total Number of References = 12
Number of Hits = 2
Number of Page Fault = 10
HitRatio = 0.17

OPTIMAL

OPTIMALとは未来に対して「最も長い間使われないであろう」ページを置換の対象とする。LRUが過去に対して「最も長く使われないページ」であるのと対象的であるといえる。ただし、実行時に未来の計測をするのは不可能であり経験則でパターン分析ができているとか、今回のように予めパターンを指定する場合においてのみ有効である。理論上一番いいのはOPTIMALアルゴリズムといわれているが未来予測どうするのかといったところでしょうか。

Page Referenceが4の時のページ置換計算を例にする。置換される前の各ページフレームPF[0]、PF[1]、PF[2]にはそれぞれページ番号3、1、2が割り当てられている。ページ番号4がアクセスされるタイミングからページ番号3、1、2が未来にアクセスされるまでの期間はそれぞれ5以上、1、4となる。よって最も遠い未来までアクセスされないPF[0](ページ番号3)が置換対象となる。ツールで実行してみると次のとおり。ページフォールトが7回で、Hit率42%と最も高い。

[kawasaki@debian:~] $ ./page_rep_algos -a OPTIMAL -p "0 1 2 3 2 1 4 1 6 0 2 1" -f 3
0: 0 Miss
1: 0 1 Miss
2: 0 1 2 Miss
3: 3 1 2 Miss
2: 3 1 2 Hit
1: 3 1 2 Hit
4: 4 1 2 Miss
1: 4 1 2 Hit
6: 6 1 2 Miss
0: 0 1 2 Miss
2: 0 1 2 Hit
1: 0 1 2 Hit

Number of Page Frames = 3
Total Number of References = 12
Number of Hits = 5
Number of Page Fault = 7
HitRatio = 0.42

シュミレーションの結果、OPTIMALアルゴリズムのHit率が最も高く、これが最も置換効率がよいということになる。今回はインプットするサンプル数が少ないのでまともな結果を出すならばデータサンプルをもっと増やす必要があるのだろうけどこの辺で終わりにしておきます。

おわり。

Posted in: Programming / プログラミング

Tags: algorithm, c, fifo, lru, optimal

Google Reader CacheからItemを削除する方法

No comments

yoichi

February 27th, 2010

一度誤った投稿をしてしまいそれがGoogle Reader Cacheに保存されてしまうと削除は難しいようだ（参照 Google Reader FAQ: Deleted posts in my blog’s feed）。仮にその記事を削除したとしても同じ。というわけでいきなりこの記事のタイトル「Google Reader CacheからItemを削除する方法」はできないということになる。ただ、FAQでコメントされているように、どうしてもCacheから削除したい場合、削除はできないがアップデートはできるという特性を活かしダミー記事Itemでリプレースするという方法がある。Itemはguidをキーとして認識する。よって同一guidのダミーItemを用意しそいつでリプレースをかけることで何とか取り繕うことができる。

Google Reader Cached Item - Wrong Item

まずは誤って投稿した記事ItemがCacheされてしまった様子。タイトル・コンテンツともに空にもかかわらずキャッシュされてしまっている。仮にこのItemのguidがhttp://yk55.com/blog/?p=200とする。この誤ってキャッシュされてしまったItemを別の何かでリプレースするためのダミー記事を用意する。もちろんその記事には同一guidを指定してやる。

<item>
<title>[dummy] Google Reader CacheからItemを削除する方法</title>
<link>http://yk55.com/blog/2010/02/27/google-reader-cache-item-removal/</link>
<comments>http://yk55.com/blog/2010/02/27/google-reader-cache-item-removal/#comments</comments>
<pubDate>Sat, 27 Feb 2010 14:55:05 +0000</pubDate>
<dc:creator>yoichi</dc:creator>
<category><![CDATA[Uncategorized]]></category>
<category</category>
<guid isPermaLink="false">http://yk55.com/blog/?p=200</guid>
<description>~略~</description>
<content:encoded>~略~</content:encoded>
<wfw:commentRss>http://yk55.com/blog/2010/02/27/google-reader-cache-item-removal/feed/</wfw:commentRss>
<slash:comments>0</slash:comments>
</item>

これを追加したRSSフィードを公開することで時間がたてばフィードがクローリングされ、さきほどの間違ったItemがダミーItemでリプレースされる。以下が見事にリプレースされた結果。

Google Reader Cached Item - Replaced Item

あまりにもべたなやり方だけど、どうしてもなんとかしたい場合にはこの方法で。おわり。

Posted in: Random / ランダムな話, web / ウェブ関連

Tags: feed, xml

Dynamic Binding & VTable Concept in C++

No comments

yoichi

February 27th, 2010

たまにc++コードのコンパイル時にエラー文言でvtableというキーワードを見たことはないだろうか？Polymorphismという有名なワードに対しこのvtableはあまりにも目立たない存在だ。とはいえPolymorphismを実現するためになくてはならない（最）重要なポジションを占めているのがvtable。別にvtableを理解しなくともPolymorphismの理解はできる。ただし、骨太になりたいのならばPolymorphismを実現するためにどのようにvtableが使われているのかを理解しておくべきである。

UPCASTING

Virtual関数との比較のためにVirtual関数を持たないクラス継承を説明する。以下のようにvirtual関数を持たないSuperClassをSubClassが継承する。 SuperClassを継承したSubClassの参照をSuperClassポインタ変数に入れた場合は、子クラスへの参照がUPCASTされ親クラスへの参照として扱われる。実行結果はSuperClassへの参照へとUPCASTされるのでSuperClassの関数の内容が表示される。

#include <iostream>
using std::cout;
using std::endl;
class SuperClass {
public:
void func() { cout << "SuperClass::func()" << endl; }
};
class SubClass : public SuperClass {
public:
void func() { cout << "SubClass::func()" << endl; }
};
int main(int argc, char **argv ) {
SubClass sub;
SuperClass *super =⊂
super->func();
return 0;
}

[実行結果]
SuperClass::func()

VIRTUAL FUNCTION, VTABLE, and VPOINTER

次にVirtual関数の例を説明する。さきほどの例ではUPCASTによりSubClassクラスではなくSuperClassクラスのfunc関数がcallされた。ここではSuperClassの関数にvirtualをつけた場合のfunc関数の振る舞いを確かめてみる。virtual関数func1、func2をもつSuperClassを継承した3つのSubClassを用意する。これら3つはそれぞれfunc1、func2両方とも、func1のみ、func2のみをoverrideしている。実行結果はSubClassでvirtual関数をoverrideした場合はその内容が、そうでない場合はSuperClassの内容が表示される。

#include <iostream>
using std::cout;
using std::endl;
class SuperClass {
public:
virtual void funcA() { cout << "SuperClass::funcA()" << endl; };
virtual void funcB() { cout << "SuperClass::funcB()" << endl; };
};
class SubClass1 : public SuperClass {
public:
void funcA() { cout << "SubClass1::funcA()" << endl; }
void funcB() { cout << "SubClass1::funcB()" << endl; }
};
class SubClass2 : public SuperClass {
public:
void funcA() { cout << "SubClass2::funcA()" << endl; }
};
class SubClass3 : public SuperClass {
public:
void funcB() { cout << "SubClass2::funcB()" << endl; }
};
int main(int argc, char **argv ) {
SubClass1 sub1; SubClass2 sub2; SubClass3 sub3;
cout << "***************SubClass1***************" << endl;
SuperClass *super =&sub1;
super->funcA(); super->funcB();
cout << "***************SubClass2***************" << endl;
super =&sub2;
super->funcA(); super->funcB();
cout << "***************SubClass3***************" << endl;
super =&sub3;
super->funcA();super->funcB();
return 0;
}

[実行結果]
***************SubClass1***************
SubClass1::funcA()
SubClass1::funcB()
***************SubClass2***************
SubClass2::funcA()
SuperClass::funcB()
***************SubClass3***************
SuperClass::funcA()
SubClass2::funcB()

virtualな関数の場合はコンパイラは型ではなくてオブジェクトのポインタを見ていて実行時にどのfuncが実行されるべきかを判断する。非virtual関数の時と違いコンパイラーはコンパイル時にはどのfuncが呼ばれるのか判別できない。この実行時にどのfuncが呼ばれるのか決定することをDynamic Bindingと呼ぶ。そしてこのDynamic BindingはVirtual Function table(Vtable)と呼ばれるメカニズムによって実現される。ようやく本題。

Vtableとはvirtual関数を持っているクラスや親クラスで定義されているvirtual関数をoverrideしたクラスに対してコンパイラーが作成する（その名のとおり）仮想テーブルである。コンパイラーはvirtual関数を持っている/virtaul関数をoverrideしているクラスにのみクラスごとのVtableを作成してその中にbindすべき関数ポインターを持っている。
またこのVtableを指すポインタのことをvpointerと呼ぶ。コンパイラはVtableを持っているクラスに対してvpointerを隠しメンバー変数として追加する。さらにコンストラクタにそのvpointer変数の初期化を行うコードを追加する。よってオブジェクトが作成されるとき隠しメンバー変数vpointerは対応するVtableアドレスで初期化され、実行時の実行関数の決定は内部でvpointerを通じてVtableをlookupすることで実現される。　（参照: wikipedia:vtable implementation）

Vtableに作成される関数ポインターは、そのクラスで持っているvirtual関数のポインター、親クラスで定義されているvirtaul関数をoverrideした関数のポインター、また親クラスでvirtual定義されている関数をoverrideしない場合はその親のvirtual関数ポインタが含まれることになる。上記サンプルにあるSuperClass, SubClass[1-3]に対するオブジェクトとvpointer、vtableとそのvtableに含まれる関数ポインターの関係を図にすると以下のようになる。

上図を元にサンプル中のSubClass1::funcAのDynamic Bindingイメージを式化してみると次のような感じになる・ vptr1はSubClass1のvpointerとする。あくまでイメージであり(vptr->)は実際は見えません。

SubClass1 sub1;
SuperClass *super =&sub1;
super->vptr->funcA(); // SubClass1::funcA(),

g++ -fdump-class-hierarchのダンプ結果

最後にg++の-fdump-class-hierarchオプションによるVtableのダンプ結果を見てみる。上記サンプルファイルをvtable.cppとして次のようにコンパイルを行う。　（参考: Options for Debugging Your Program or GCC）

 g++ -fdump-class-hierarchy vtable.cc -o vtable

これでコンパイルが終わりvtable実行ファイルができあがる。また同一ディレクトリにvtable.cpp.002t.classという名前のファイルが出来上がる。このファイルにVtableのダンプ結果が出力されている。各クラスのVtable中を見るといまいち意味のわからないものはあるが上図のとおりの関数が含まれており、また各クラスにはvptrを見つけることができる。

Vtable for SubClass1
SubClass1::_ZTV9SubClass1: 4u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI9SubClass1)
8 SubClass1::funcA
12 SubClass1::funcB

Class SubClass1
size=4 align=4
base size=4 base align=4
SubClass1 (0xb7254a80) 0 nearly-empty
vptr=((& SubClass1::_ZTV9SubClass1) + 8u)
SuperClass (0xb707c1e0) 0 nearly-empty
primary-for SubClass1 (0xb7254a80)

Vtable for SubClass2
SubClass2::_ZTV9SubClass2: 4u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI9SubClass2)
8 SubClass2::funcA
12 SuperClass::funcB

Class SubClass2
size=4 align=4
base size=4 base align=4
SubClass2 (0xb7254b80) 0 nearly-empty
vptr=((& SubClass2::_ZTV9SubClass2) + 8u)
SuperClass (0xb707c3c0) 0 nearly-empty
primary-for SubClass2 (0xb7254b80)

Vtable for SubClass3
SubClass3::_ZTV9SubClass3: 4u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI9SubClass3)
8 SuperClass::funcA
12 SubClass3::funcB

Class SubClass3
size=4 align=4
base size=4 base align=4
SubClass3 (0xb7254c40) 0 nearly-empty
vptr=((& SubClass3::_ZTV9SubClass3) + 8u)
SuperClass (0xb707c528) 0 nearly-empty
primary-for SubClass3 (0xb7254c40)

おわり

Posted in: Programming / プログラミング

Tags: cplusplus, gcc, polymorphism, vpointer, vtable

Ubuntu 9.10 on my Dell XPS M1210

簡単Boehm GCによるC/C++メモリリーク検知

Boehm GCインストール

**Cコードメモリリーク検知 – *alloc/freeをGC_関数に置換**

C++ コードメモリリーク検知 – gc/gc_cleanupクラスで継承

C++コードメモリリーク検知 – new/deleteオペレータのオーバーロード

ページ置換アルゴリズム(Page Replacement Algorithms)のシュミレーション

ツールのコンパイルとその使い方

LRU（Least Recently Used）

FIFO（First-In First-Out）

OPTIMAL

Google Reader CacheからItemを削除する方法

Dynamic Binding & VTable Concept in C++

UPCASTING

VIRTUAL FUNCTION, VTABLE, and VPOINTER

g++ -fdump-class-hierarchのダンプ結果

Recent Posts

Categories

About me and blog

Find me else where

Subscribe me