本棚本(表紙的に･･･)の著者の一人の中村成洋氏のミニGC
ミニGCの作り方
githubのソース
を参考にシングルスレッド版(Windows7 32bit)のマークスイープGCを作ってみた。
ルーツ選択部分はBoehmGCを参考にした。
レジスタ、スタック、グローバル変数の動作を慎重に吟味。
正しく動作している！のは当然として、参照が外れた時の動作がイメージ通りでなんか感動。
GC面白いなぁ･･･他のアルゴリズムなんかも実装してみたいところだけどちょっと時間がないや。
それにしても氏のソースは少しバグが多い気がする。
2012年2月19日日曜日
2012年2月10日金曜日
BoehmGC(3)
Windows7 32bit 環境での GC_register_dynamic_libraries() より抜粋。
抜粋というと語弊があるのでルーツ選別部分を出力してみた。
※が付いている箇所がルーツ対象。
下記の順番で No はマッピングされた番号。
・main 関数の引数 int argc
・main 関数の引数 char* argv[]
・main 関数内の自動変数
・未初期化外部変数
・初期化済外部変数
・未初期化静的変数
・初期化済静的変数
・main 関数内の自動変数
・ヒープ
なるほど！
抜粋というと語弊があるのでルーツ選別部分を出力してみた。
*** SYSINFO *** oem id : 0 page size : 4096 bytes min app address : 0x00010000 max app address : 0xbffeffff active processor mask : 0xff number of processors : 8 processor type : 0x24a allocation granularity: 65536 bytes processor level : 6 processor revision : 0x1a05 process id: 5908(current) No Addr Size(bytes) Pages AllocBase 状態 アクセス許可 タイプ/モジュール名 =================================================================================================== 000 0x00000000 65536 16 0x00000000 フリー アクセス不可 001 0x00010000 65536 16 0x00010000 コミット 読み書き可 マップ 002 0x00020000 65536 16 0x00020000 コミット 読み書き可 マップ 003 0x00030000 1003520 245 0x00030000 予約 プライベート 004 0x00125000 4096 1 0x00030000 コミット 読み書き可(ガード) プライベート 005 0x00126000 40960 10 0x00030000 コミット 読み書き可 プライベート 006 0x00130000 16384 4 0x00130000 コミット 読み込みのみ可 マップ 007 0x00134000 49152 12 0x00000000 予約余り アクセス不可 008 0x00140000 4096 1 0x00140000 コミット 読み込みのみ可 マップ 009 0x00141000 61440 15 0x00000000 予約余り アクセス不可 010 0x00150000 4096 1 0x00150000 コミット 読み書き可 プライベート 011 0x00151000 61440 15 0x00000000 予約余り アクセス不可 012 0x00160000 421888 103 0x00160000 コミット 読み込みのみ可 マップ 013 0x001c7000 36864 9 0x00000000 予約余り アクセス不可 014 0x001d0000 131072 32 0x00000000 フリー アクセス不可 015 0x001f0000 20480 5 0x001f0000 コミット 読み書き可 プライベート 016 0x001f5000 45056 11 0x001f0000 予約 プライベート 017 0x00200000 131072 32 0x00000000 フリー アクセス不可 018 0x00220000 262144 64 0x00220000 コミット 読み書き可 プライベート 019 0x00260000 786432 192 0x00220000 予約 プライベート 020 0x00320000 917504 224 0x00000000 フリー アクセス不可 021 0x00400000 4096 1 0x00400000 コミット 読み込みのみ可 イメージ 022 0x00401000 4096 1 0x00400000 コミット 実行/読み込みのみ可 イメージ 023 0x00402000 4096 1 0x00400000 コミット 読み込みのみ可 イメージ 024 0x00403000 4096 1 0x00400000 コミット 読み書き可 イメージ ※ 025 0x00404000 4096 1 0x00400000 コミット 読み込みのみ可 イメージ 026 0x00405000 45056 11 0x00000000 予約余り アクセス不可 027 0x00410000 1572864 384 0x00000000 フリー アクセス不可 028 0x00590000 12288 3 0x00590000 コミット 読み書き可 プライベート 029 0x00593000 53248 13 0x00590000 予約 プライベート 030 0x005a0000 1742536704 425424 0x00000000 フリー アクセス不可 031 0x68370000 4096 1 0x68370000 コミット 読み込みのみ可 イメージ 032 0x68371000 405504 99 0x68370000 コミット 実行/読み込みのみ可 イメージ 033 0x683d4000 176128 43 0x68370000 コミット 読み込みのみ可 イメージ 034 0x683ff000 4096 1 0x68370000 コミット 読み書き可 イメージ ※ 035 0x68400000 4096 1 0x68370000 コミット 書き込み時コピー イメージ 036 0x68401000 4096 1 0x68370000 コミット 読み書き可 イメージ ※ 037 0x68402000 4096 1 0x68370000 コミット 書き込み時コピー イメージ 038 0x68403000 12288 3 0x68370000 コミット 読み書き可 イメージ ※ 039 0x68406000 20480 5 0x68370000 コミット 読み込みのみ可 イメージ 040 0x6840b000 20480 5 0x00000000 予約余り アクセス不可 041 0x68410000 221380608 54048 0x00000000 フリー アクセス不可 042 0x75730000 4096 1 0x75730000 コミット 読み込みのみ可 イメージ 043 0x75731000 274432 67 0x75730000 コミット 実行/読み込みのみ可 イメージ 044 0x75774000 8192 2 0x75730000 コミット 読み書き可 イメージ ※ 045 0x75776000 16384 4 0x75730000 コミット 読み込みのみ可 イメージ 046 0x7577a000 24576 6 0x00000000 予約余り アクセス不可 047 0x75780000 5636096 1376 0x00000000 フリー アクセス不可 048 0x75ce0000 4096 1 0x75ce0000 コミット 読み込みのみ可 イメージ 049 0x75ce1000 806912 197 0x75ce0000 コミット 実行/読み込みのみ可 イメージ 050 0x75da6000 4096 1 0x75ce0000 コミット 読み書き可 イメージ ※ 051 0x75da7000 53248 13 0x75ce0000 コミット 読み込みのみ可 イメージ 052 0x75db4000 49152 12 0x00000000 予約余り アクセス不可 053 0x75dc0000 19726336 4816 0x00000000 フリー アクセス不可 054 0x77090000 4096 1 0x77090000 コミット 読み込みのみ可 イメージ 055 0x77091000 651264 159 0x77090000 コミット 実行/読み込みのみ可 イメージ 056 0x77130000 4096 1 0x77090000 コミット 読み書き可 イメージ ※ 057 0x77131000 4096 1 0x77090000 コミット 書き込み時コピー イメージ 058 0x77132000 8192 2 0x77090000 コミット 読み書き可 イメージ ※ 059 0x77134000 12288 3 0x77090000 コミット 書き込み時コピー イメージ 060 0x77137000 20480 5 0x77090000 コミット 読み込みのみ可 イメージ 061 0x7713c000 16384 4 0x00000000 予約余り アクセス不可 062 0x77140000 2228224 544 0x00000000 フリー アクセス不可 063 0x77360000 4096 1 0x77360000 コミット 読み込みのみ可 イメージ 064 0x77361000 876544 214 0x77360000 コミット 実行/読み込みのみ可 イメージ 065 0x77437000 4096 1 0x77360000 コミット 読み書き可 イメージ ※ 066 0x77438000 8192 2 0x77360000 コミット 書き込み時コピー イメージ 067 0x7743a000 4096 1 0x77360000 コミット 読み書き可 イメージ ※ 068 0x7743b000 4096 1 0x77360000 コミット 書き込み時コピー イメージ 069 0x7743c000 8192 2 0x77360000 コミット 読み書き可 イメージ ※ 070 0x7743e000 8192 2 0x77360000 コミット 書き込み時コピー イメージ 071 0x77440000 376832 92 0x77360000 コミット 読み込みのみ可 イメージ 072 0x7749c000 16384 4 0x00000000 予約余り アクセス不可 073 0x774a0000 1048576 256 0x00000000 フリー アクセス不可 074 0x775a0000 4096 1 0x775a0000 コミット 読み込みのみ可 イメージ 075 0x775a1000 61440 15 0x00000000 予約余り アクセス不可 076 0x775b0000 135528448 33088 0x00000000 フリー アクセス不可 077 0x7f6f0000 20480 5 0x7f6f0000 コミット 読み込みのみ可 マップ 078 0x7f6f5000 1028096 251 0x7f6f0000 予約 マップ 079 0x7f7f0000 8126464 1984 0x00000000 フリー アクセス不可 080 0x7ffb0000 176128 43 0x7ffb0000 コミット 読み込みのみ可 マップ 081 0x7ffdb000 20480 5 0x00000000 予約余り アクセス不可 082 0x7ffe0000 4096 1 0x7ffe0000 コミット 読み込みのみ可 プライベート 083 0x7ffe1000 61440 15 0x7ffe0000 予約 プライベート 084 0x7fff0000 57344 14 0x00000000 フリー アクセス不可 085 0x7fffe000 4096 1 0x7fffe000 コミット 読み書き可 プライベート 086 0x7ffff000 4096 1 0x7ffff000 コミット 読み書き可 プライベート 087 0x80000000 1073676288 262128 0x80000000 予約 プライベート 0xbfff0000 --- アクセス不許可 ---------------------------------------------------------------------------------------------------
※が付いている箇所がルーツ対象。
Stack: 0x0012ff4c No:005 Stack: 0x0012ff50 No:005 Stack: 0x0012ff44 No:005 BSS : 0x00403378 No:024 Data : 0x00403018 No:024 BSS : 0x004033a8 No:024 Data : 0x0040301c No:024 Stack: 0x0012ff40 No:005 Heap : 0x001f12a0 No:015
下記の順番で No はマッピングされた番号。
・main 関数の引数 int argc
・main 関数の引数 char* argv[]
・main 関数内の自動変数
・未初期化外部変数
・初期化済外部変数
・未初期化静的変数
・初期化済静的変数
・main 関数内の自動変数
・ヒープ
なるほど！
2012年2月8日水曜日
BoehmGC(2)
GC_push_roots から辿れる部分を追ってみた。
･･･改めてBoehmGCの偉大さを痛感した。
なんというべきか、あらゆるCPUとOSの歴史だなこれは。
windowsのみに着目しても頭痛がしそうだ(汗
テストプログラムを書くにしても、何のcpuか何のOSかスレッドの有無を
限定しないと話が進みそうにもないや。
とりあえずVCでもインストールするか。
･･･改めてBoehmGCの偉大さを痛感した。
なんというべきか、あらゆるCPUとOSの歴史だなこれは。
windowsのみに着目しても頭痛がしそうだ(汗
テストプログラムを書くにしても、何のcpuか何のOSかスレッドの有無を
限定しないと話が進みそうにもないや。
とりあえずVCでもインストールするか。
2012年2月7日火曜日
BoehmGC
Ubuntu側に落として簡単な動作確認。
参照が途切れるタイミングを見ていたが、当然の如くスタックもグローバル変数もバッチリ。
となると、実装方法は１つ。
念のためソースコードを追ってみるとコンパイルスイッチの嵐。
ざっくり見た感じだとデータセグメントを操作している。
x86の実装部分はまだ少し追ってみないと良く分からない部分があるけども。
参照が途切れるタイミングを見ていたが、当然の如くスタックもグローバル変数もバッチリ。
となると、実装方法は１つ。
念のためソースコードを追ってみるとコンパイルスイッチの嵐。
ざっくり見た感じだとデータセグメントを操作している。
x86の実装部分はまだ少し追ってみないと良く分からない部分があるけども。
2012年2月5日日曜日
メモリとか
とある分厚い本を読了。
海の向こうの技術はやっぱり凄いわ･･･。
直接関係はないがメモリー関連の本が欲しいなと物色したら
省メモリプログラミング―メモリ制限のあるシステムのためのソフトウェアパターン集
というものがあったので購入し読了。
非常によくまとまった良書と感じた。
続けてガベージコレクションに興味が沸く。
というのもGCについては上辺程度のことしか知らない。
Androidの場合だとDalvikさんがよろしくやってくれるので最低限のことしか気にしていなかったが
そもそものコンセプトであるメモリ管理に煩わされなくていいよと言われて、はいそうですかというのも
やっぱり気持ち悪い。
そんなわけで取っ掛かりとして
ガベージコレクションのアルゴリズムと実装
を購入しざっくり読了。
非常に分かりやすい解説でアルゴリズムはすんなりと頭に入った。
ただ、実装すると仮定した場合のルートについては理解が不十分なのでメモ書き。
■ヒープ
これはアロケータも含めての話となるのでルートとすることは簡単。
■スタック(関数の引数とかローカル変数)
GC初期化～直前のローカル変数のアドレス間を操作。
■レジスタ
GC直前にアセンブリかsetjmpでレジスタ取得を行い操作。
環境依存を考慮すると後者が一般的。
スタックとレジスタについては若干悩んだが、
・GCは不要とされるオブジェクトを破棄する
・GCされることで実行コード(スタックやレジスタ)に影響があっては困る
という点から、スタックやレジスタが有効とされるアドレスを参照しているならば
GCには破棄させないということで操作については納得した。
グローバル変数については気になることが色々あるのでオープンソースな実装を読んでいる。
Rubyの場合はrb_gc_register_addressで内部で保持するリストに登録してる感じのようだ。
C/C++ネイティブなものも知る必要があるのでBoehmGCも併読。
海の向こうの技術はやっぱり凄いわ･･･。
直接関係はないがメモリー関連の本が欲しいなと物色したら
省メモリプログラミング―メモリ制限のあるシステムのためのソフトウェアパターン集
というものがあったので購入し読了。
非常によくまとまった良書と感じた。
続けてガベージコレクションに興味が沸く。
というのもGCについては上辺程度のことしか知らない。
Androidの場合だとDalvikさんがよろしくやってくれるので最低限のことしか気にしていなかったが
そもそものコンセプトであるメモリ管理に煩わされなくていいよと言われて、はいそうですかというのも
やっぱり気持ち悪い。
そんなわけで取っ掛かりとして
ガベージコレクションのアルゴリズムと実装
を購入しざっくり読了。
非常に分かりやすい解説でアルゴリズムはすんなりと頭に入った。
ただ、実装すると仮定した場合のルートについては理解が不十分なのでメモ書き。
■ヒープ
これはアロケータも含めての話となるのでルートとすることは簡単。
■スタック(関数の引数とかローカル変数)
GC初期化～直前のローカル変数のアドレス間を操作。
■レジスタ
GC直前にアセンブリかsetjmpでレジスタ取得を行い操作。
環境依存を考慮すると後者が一般的。
スタックとレジスタについては若干悩んだが、
・GCは不要とされるオブジェクトを破棄する
・GCされることで実行コード(スタックやレジスタ)に影響があっては困る
という点から、スタックやレジスタが有効とされるアドレスを参照しているならば
GCには破棄させないということで操作については納得した。
グローバル変数については気になることが色々あるのでオープンソースな実装を読んでいる。
Rubyの場合はrb_gc_register_addressで内部で保持するリストに登録してる感じのようだ。
C/C++ネイティブなものも知る必要があるのでBoehmGCも併読。
2011年12月27日火曜日
アライメント
主にJavaを触っているのだが、よく考えればメモリー管理はよろしくやってくれるわけで･･･。
アドレスも見れないし見る必要がないコンセプトなのでいいやと思いつつも、何故かC++版を
書いてみたい衝動に駆られ、久しぶりにC/C++コンパイラーを起動した。
すぐに終わるだろうと考えていたが、環境がUbuntu-64bit(Android-Gingerbread以上)なことを
すっかり忘れていたため、予想外に時間が掛かってしまった。
C/C++関連は32bitOSにどっぷりと慣れていたからなぁ･･･。
64bitなのでポインターサイズは8bytes。
32bitなら気にせず unsigend int で済ましても問題がなかったところ。
uintptr_t、ptrdiff_t、size_t が環境によって自動的に変わるため、これを利用すればいい。
※オフセット値を2bytesで保持していたが、アドレスを直接持つように変更
アドレスも見れないし見る必要がないコンセプトなのでいいやと思いつつも、何故かC++版を
書いてみたい衝動に駆られ、久しぶりにC/C++コンパイラーを起動した。
すぐに終わるだろうと考えていたが、環境がUbuntu-64bit(Android-Gingerbread以上)なことを
すっかり忘れていたため、予想外に時間が掛かってしまった。
C/C++関連は32bitOSにどっぷりと慣れていたからなぁ･･･。
// アライメントの計算
uintptr_t alignment(uintptr_t rawAddress, size_t align){
align--;
return (rawAddress + align) & ~align;
}
void* allocateAligned(size_t size, size_t align){
// 2の羃乗でない場合はアサート
assert(((align - 1) & align) == 0);
// 実際に確保するサイズ(actual_size = request_size + (align - 1) + offset_size)
size_t actualSize = size + (align - 1) + sizeof(void*);
// アラインされていないメモリ確保
void* pRawAddress = malloc(actualSize);
if(pRawAddress == NULL)
return NULL;
// オフセットアドレスに生アドレスを書き込む
uintptr_t rawAddress = reinterpret_cast<uintptr_t>(pRawAddress);
uintptr_t alignedAddress = alignment(rawAddress + sizeof(void*), align);
ptrdiff_t offsetAddress = alignedAddress - sizeof(void*);
void** ppOffsetAddress = reinterpret_cast<void**>(offsetAddress);
*ppOffsetAddress = pRawAddress;
// アラインされたアドレスへのポインタを返す
return reinterpret_cast<void*>(alignedAddress);
}
void Allocator::freeAligned(void* p){
assert(p != NULL);
uintptr_t alignedAddress = reinterpret_cast<uintptr_t>(p);
uintptr_t offsetAddress = alignedAddress - sizeof(void*);
void** ppOffsetAddress = reinterpret_cast<void**>(offsetAddress);
// アラインされていないアドレスへのポインタで解放
free(*ppOffsetAddress);
}
64bitなのでポインターサイズは8bytes。
32bitなら気にせず unsigend int で済ましても問題がなかったところ。
uintptr_t、ptrdiff_t、size_t が環境によって自動的に変わるため、これを利用すればいい。
※オフセット値を2bytesで保持していたが、アドレスを直接持つように変更
登録:
投稿
(
Atom
)