2013-03-26

脱BoehmGCへの道 実装編(3)

ちょぼちょぼ動くようになってきたのだが、やはり一筋縄ではいかないなぁと言うのが正直な感想。

とりあえず現状で問題になっているもの。
  1. eq?なハッシュテーブル
  2. 昇格された領域にあるオブジェクトから参照されているオブジェクトの移動
1.はシンボル等のアドレスが変わると起きる問題。とりあえず急場でGC中に見つけたテーブルを全てリハッシュをするようにしたけど、これだと何の移動も起きなかったテーブルも影響するし、見つけられなかったテーブルは大変なことになる。けど、うまいやり方が思いつかない。

2.は昇格したオブジェクトから参照されているオブジェクトが移動した場合に起きる問題。とりあえず、理解を整理するための図が以下:
             Eden              |             Survivor
+------------------------------+------------------------------------+
|                              |             obj B                  |
|                              |            +-----+                 |
|             +----------------+------------+--*  |                 |
|        +----+----+           |            +-----+    +-------+    |
|        |  obj A  |           |            |  *--+----+ obj C |    |
|        +---------+           |            +-----+    +-------+    |
+------------------------------+------------------------------------+
obj Bはまぁ配列でも構造体でもなんでもいいんだけど、要するにポインタを格納するオブジェクト。っで1回目のGCで生き残って昇格したんだけど、次のGCとの合間に若い世代のオブジェクトobj Aを内に宿すことになったと。(具体的にはコードベクタが参照する識別子のルックアップを終えてglocを対象の場所に入れるとこれが起きる。まぁ、他にもあるだろう。)

っで、GCが起きると困ることになる。だれが移動先を解決するのかと・・・

実際はこの手のものはある程度解決されてるんだけど、どうも見逃しがあるっぽい。

コードベクタはクロージャとVMで同じものが共有されてるから、クロージャ側だけ更新してやればいいはずなんだけどなぁ、何を見落としてるんだろう・・・

2013-03-23

詳解SBCL - Genesis

今日が土曜だということをすっかり忘れて「明日書く」なんて書いてしまった。自分の言動を曲げるのは好きじゃないので、家事の合間の時間で書く(土曜は以外にも忙しい)。

 GenesisとはSBCLがビルド時に生成するCコードのことだと思えばいい。実際にビルドプロセスを走らせると、src/runtimeディレクトリ以下にgenesisディレクトリが作成され、Lisp構造体からconfig.hまで必要な設定が生成される。要するにconfigureスクリプトである。

ビルド時に生成するなら設定とか環境依存の値だけでもいいような気がするが、なぜLispオブジェクトの構造体まで生成するのだろうか?

この辺実はまじめにソース(及びコメント)を読んでいないので推測の域を出ないのではあるが、たとえば世代別GCで使われているgeneration構造体あたりのコメントがなぞを解く鍵になるだろう(大げさ)。要約すると、コメントには以下のような記述がある。
注意:これの変更をしたら、Lisp側のコードも変更するように!もしくはそこにあるFIXMEに書かれてるようにしてくれ。
っで、FIXMEを見る。
 注意:GENERATION(とPAGE)はLisp内で定義されてGenesisでヘッダーに書き出されるべきだ。こことgencgc.cで二重定義なってやがる。
まぁ、要するにランタイム以外の部分って全部Lispで書かれてるから、メンテナンス性を考えると一箇所で定義した方がいいよねって理由だと思う。

これだけだと、「ふ~ん」で終わりそうなので(いや、実際書くほどのことはないのだ)、世代別GCに関係するGenesisを多少紹介。src/compiler/x86/parms.lispにLispオブジェクトが割り当てられるヒープ領域がある。定義はこんな感じ。
#!+win32   (!gencgc-space-setup #x22000000 nil nil #x10000)
#!+linux   (!gencgc-space-setup #x01000000 #x09000000)
#!+sunos   (!gencgc-space-setup #x20000000 #x48000000)
#!+freebsd (!gencgc-space-setup #x01000000 #x58000000)
#!+openbsd (!gencgc-space-setup #x1b000000 #x40000000)
#!+netbsd  (!gencgc-space-setup #x20000000 #x60000000)
#!+darwin  (!gencgc-space-setup #x04000000 #x10000000)
!gencgc-space-setupsrc/compiler/generic/parms.lispに定義がある。第一引数はスモールスペースのアドレス(どこで使われてるかは確認してない)、第二引数が動的領域の開始アドレスである。これはX86の固有設定だが、他のアーキテキチャにも同様の定義があり、固定値を使っている。

合計4つになるとも思ってなかったけど、これをきっかけにSBCLのソースコードも怖くない、と思って読み手が増えることを願って。

2013-03-22

詳解SBCL - 世代別GC(3)

昨日はルートのマーキングまで書いたので、今日はいよいよ実際にオブジェクトを動かすところ、つまりSBCLの世代別GCの肝の部分に触れていこう。

【scavenge】
この処理がすべての処理の鍵であるといってもまぁ、過言ではないだろう。とりあえず中身を見ていこう。(src/runtime/gc-common.cより、一部整形及び削除)
void scavenge(lispobj *start, sword_t n_words)
{
    lispobj *end = start + n_words;
    lispobj *object_ptr;
    sword_t n_words_scavenged;

    for (object_ptr = start; object_ptr < end; object_ptr += n_words_scavenged) {

        lispobj object = *object_ptr;

        if (forwarding_pointer_p(object_ptr))
            lose("unexpect forwarding pointer in scavenge: %p, start=%p, n=%l\n",
                 object_ptr, start, n_words);

        if (is_lisp_pointer(object)) {
            if (from_space_p(object)) {
                /* It currently points to old space. Check for a
                 * forwarding pointer. */
                lispobj *ptr = native_pointer(object);
                if (forwarding_pointer_p(ptr)) {
                    /* Yes, there's a forwarding pointer. */
                    *object_ptr = LOW_WORD(forwarding_pointer_value(ptr));
                    n_words_scavenged = 1;
                } else {
                    /* Scavenge that pointer. */
                    n_words_scavenged =
                        (scavtab[widetag_of(object)])(object_ptr, object);
                }
            } else {
                /* It points somewhere other than oldspace. Leave it
                 * alone. */
                n_words_scavenged = 1;
            }
        } else if (fixnump(object)) {
            /* It's a fixnum: really easy.. */
            n_words_scavenged = 1;
        } else {
            /* It's some sort of header object or another. */
            n_words_scavenged =
                (scavtab[widetag_of(object)])(object_ptr, object);
        }
    }
    gc_assert_verbose(object_ptr == end, "Final object pointer %p, start %p, end %p\n",
                      object_ptr, start, end);
}
与えられたstartの中身を順番に見ていき、Lispオブジェクトでかつ既に移動されたものならば移動先に置き換える、まだならscavtabテーブルに格納された実際の処理に処理を委譲する。*object_ptrが何を指すのか今一理解できなくて、SBCLのGCはどう動いているのだろうなんて疑問に思ったのは秘密である(well if you have read my articles or twitter, you know...)。ここで、ポイント(と僕が思う部分)は与えられたstartは必ずヒープ領域を指すことだろう。また、特に何もしなくてもオブジェクトの割り付けられたメモリ境界を指すということだ。これは、scavengeが呼ばれる部分を見れば分かるのだが、事前にページもしくはリージョンの開始位置を計算しているのと、割り付けられたオブジェクトの位置を直接渡していることに起因する。詳しくはsrc/runtime/gencgc.cにあるgarbage_collect_generationを参照されたい(多分後で多少触れるけど)。

ではscavtabには何が入っているのだろうか?

この辺は実は非常に読みやすくて、scav_のプリフィックスがついた関数がsrc/runtime/gc-common.cにある。それらを眺めればどの処理がどのオブジェクトに対応しているのか大体わかるという寸法。実際の振り分けは、widetag_ofが適切にオブジェクトからタグを取り出すのでそれにしたがっている。また、テーブルの設定も同様に行われる。タグが255もあるのでテーブルの設定はすごく長い処理になっているのはまぁご愛嬌だろう(src/runtime/gc-common.cgc_init_tables参照)。

とりあえず、一つ中身を見てみよう。Lispといえばでリストを見る。
static sword_t scav_list_pointer(lispobj *where, lispobj object)
{
    lispobj first, *first_pointer;

    gc_assert(is_lisp_pointer(object));

    /* Object is a pointer into from space - not FP. */
    first_pointer = (lispobj *) native_pointer(object);

    first = trans_list(object);
    gc_assert(first != object);

    /* Set forwarding pointer */
    set_forwarding_pointer(first_pointer, first);

    gc_assert(is_lisp_pointer(first));
    gc_assert(!from_space_p(first));

    *where = first;
    return 1;
}
処理としては非常に簡単で、与えられたリストobjecttrans_listでコピー、その後whereが指すポインタと入れ替える。trans_listはリストの指すcarcdrを単にコピーしているだけで、その中身までは見ない(コード貼り付けると無駄に長くなるので割愛)。これによってリニアタイムの処理になる。

では、リストの中身が指すポインタは一体誰が救うのか?

ここまで読んでいれば勘のいい人は既に分かっているだろうが、scavengeである。実際にscavengeは以下の3つの段階で呼ばれる。
  1. 割り込みハンドラ、バインディングスタック及びSBCLの静的領域の回収
  2. GC対象外の世代の回収
  3. 新しい世代の回収
の3つである。ものすごく簡単に言えば、GC対象のヒープ領域以外のヒープをすべて回収し、GC対象の領域でピン止めされたページ以外はごみとするという感じである。

これで大まかなSBCLのGCの流れは終了。書き忘れたこととかあるかな?

今日はここで時間切れ。Genesisについては明日触れることにする。

2013-03-21

Bignumの最適化

事の発端は以下の記事
#:g1: XCLがSBCLより速いところ
最終的に行き着くのはBignumのexptでそいつが遅いことは実は分かっていた(手元のマシンで測ると、Gaucheで20秒ちょっと、Sagittariusでは30秒以上かかっていた)。っで、まぁ、遅いのは気に入らないので何とかならないかと無い知恵と頭をフル回転させることにした。

大抵Bignumが遅い一番の理由はメモリである。で、実装を見てみると豪華に作っては捨てるを繰り返していたのでここを何とかしようと頑張ってみた。ちょっとしたベンチマーク。
(import (time))
(time (begin (expt (* 100000 100000) #x2FFFF) 1))
乗数が半端なくでかい場合という感じのもの。結果(上が0.4.3、下が開発版)。
% sash test.scm

;;  (begin (expt (* 100000 100000) 196607) 1)
;;  147.578838 real    147.4670 user    0.000000 sys

% ./build/sash.exe test.scm

;;  (begin (expt (* 100000 100000) 196607) 1)
;;  28.751352 real    28.68900 user    0.016000 sys
大きく効果があった感じがする(とは言っても5倍か)。ついでにこの記事の元になったベンチマーク結果。
% sash test.scm

;;  (begin (^^ 10 6) 1)
;;  33.010235 real    33.01000 user    0.000000 sys

% ./build/sash.exe test.scm

;;  (begin (^^ 10 6) 1)
;;  4.867294 real    4.867000 user    0.000000 sys
7倍程度の高速化。まぁ、何が悲しいかと言えば、これでもYpsilonに並んだ程度なのと、Mosh(gmp)より50倍程度遅いことか。ま、SBCLに並んだということで満足してしまおう・・・

詳解SBCL - 世代別GC(2)

今日はいよいよメモリの割付とGCについて。朝の暇な時間を使っているのでGCは最後まで書けないかも。

【メモリ割付】
SBCLではメモリの割付はリージョンを通して行うというのは昨日書いた。それをすると何がうれしいかという話である。
たとえばBoehm GCではメモリは要求サイズをフリーリストから取ってくる。もちろん実際にはもっと最適化されていて、(記憶が正しかったら)8、16、24、といった感じでよく使われる小さいオブジェクトと大きいオブジェクトで別に管理している。っで、8バイトなら8バイト領域のフリーリストから取ってくるのでメモリがフィットするかどうかを調べる必要がないといった感じ(だったはず)。
では、SBCLではどうか?多くのコピーGCと同じくメモリの割付は先頭メモリのポインタを返すだけである。なので(おそらく)高速に動く。もちろん、ページ単位でメモリの割付を行うのでリージョンが管理しているアドレスの末尾を超えるようなサイズのチェック等はある。
実際に割付のコードを見てみよう。 (src/runtime/gencgc.cより、一部整形及び削除)
static inline lispobj *
general_alloc_internal(sword_t nbytes, int page_type_flag, struct alloc_region *region,
                       struct thread *thread)
{
    void *new_obj;
    void *new_free_pointer;
    os_vm_size_t trigger_bytes = 0;

    if (nbytes > large_allocation)
        large_allocation = nbytes;

    /* maybe we can do this quickly ... */
    new_free_pointer = region->free_pointer + nbytes;
    if (new_free_pointer <= region->end_addr) {
        new_obj = (void*)(region->free_pointer);
        region->free_pointer = new_free_pointer;
        return(new_obj);        /* yup */
    }
              :
    /* 削除 (GC起動用コード)*/
              :
    new_obj = gc_alloc_with_region(nbytes, page_type_flag, region, 0);

    return (new_obj);
}


/* Allocate bytes.  All the rest of the special-purpose allocation
 * functions will eventually call this  */
void *
gc_alloc_with_region(sword_t nbytes,int page_type_flag, struct alloc_region *my_region,
                     int quick_p)
{
    void *new_free_pointer;

    if (nbytes>=large_object_size)
        return gc_alloc_large(nbytes, page_type_flag, my_region);

    /* Check whether there is room in the current alloc region. */
    new_free_pointer = my_region->free_pointer + nbytes;

    if (new_free_pointer <= my_region->end_addr) {
        /* If so then allocate from the current alloc region. */
        void *new_obj = my_region->free_pointer;
        my_region->free_pointer = new_free_pointer;

        /* Unless a `quick' alloc was requested, check whether the
           alloc region is almost empty. */
        if (!quick_p &&
            void_diff(my_region->end_addr,my_region->free_pointer) <= 32) {
            /* If so, finished with the current region. */
            gc_alloc_update_page_tables(page_type_flag, my_region);
            /* Set up a new region. */
            gc_alloc_new_region(32 /*bytes*/, page_type_flag, my_region);
        }

        return((void *)new_obj);
    }

    /* Else not enough free space in the current region: retry with a
     * new region. */
    gc_alloc_update_page_tables(page_type_flag, my_region);
    gc_alloc_new_region(nbytes, page_type_flag, my_region);
    return gc_alloc_with_region(nbytes, page_type_flag, my_region,0);
}
前提条件として要求サイズは8の倍数(src/runtime/alloc.cで切り上げられる)である必要がある。gc_alloc_internalを見ると分かるが、要求されたサイズが末尾アドレスを超えない場合は先頭アドレスを返し、末尾アドレスを増やす。超える場合は新たにリージョンの割付を行い、やはり先頭アドレスを返す(gc_alloc_with_region)。
Boehm GCと違いSBCLではヒープから割り付けられるオブジェクトはLispオブジェクトのみと割り切っている(はずな)ので、メモリはヘッダ情報等を持つことはない。 逆に、consを除く全てのオブジェクトはヘッダ情報を持っていて、そこからオブジェクトのサイズ等を割り出すことが可能である(はず、自信ない・・・)。
まぁ、メモリの割付なんてそう面白いところはないので、適当に切り上げて次へ(逃走ともいう)。

【GC】
さて、ようやく本題のGCである。SBCLではGCの起動方法は2種類あって、ユーザーが直接Lisp手続きのgcを叩くのと、リージョンの使用メモリがトリガーバイト以上になった際に勝手に起動されるのの2種類である。(前者しか用意されてなかったらGCじゃないわね・・・)

では、GC起動の大まかな流れを見てみよう。流れとしては以下のようなフローになる。
  1. メモリ割付時に*gc-pending*フラグにtをセットする
  2. ついで擬似アトミックに割り込みフラグをセットする
  3. 割付終了後、擬似アトミックの割り込みをチェック
  4. 割り込みがあれば割り込みを処理させる
    • 割り込みはCPU割り込みで実現される(int3もしくはud3命令)
  5. 使ってないスタックをきれいにする
  6. 世界を止める
    • SBCLではincrementalマーキングとか、mostly concurrent GCとか軟弱なものはなく、漢らしくGCの間世界には止まってもらう
  7. ごみ集めする
    • 基本的には第一世代のみを行うが、必要(次の世代もメモリが足りない)ならば以降の世代も行う
    • 明示的にどの世代をGCするかの指定も可能
  8. *gc-pending*nilをセットする
  9. 世界を動かす
  10. ファイナライザを起動させる
ファイナライザはGC終了後に起動されるのは(多分)Boehm GCでも同じだと思う。(ファイナライザがメモリを要求したらとか考えるとそうあった方が便利な気がするし。)
SBCLのファイナライザはLisp側で実装されていて、起動時にはGCが起きないようになっている(src/code/final.lisp参照)。

世界を止めるのはマルチスレッドでは重要だけど、今回はシングルスレッドの流れを追っているので深くは言及しないが、pthread_killでUSR2(内部でGC用シグナルとして定義)を送りスレッドを止めている。開始はその逆。わざわざシグナルを使っているのは、標準POSIXのpthreadではサスペンドがサポートされていないことと、Linuxのpthreadには拡張としてのpthread_suspend_npに対応するものがないことだと思われる。(Windows、*BSDとかだとスレッドのサスペンドが可能)。

【ルートマーキング】
SBCLにおいてGCルートと考えられているのは2つ、スタックとレジスタである。 マーキングは非常にシンプルで、スタックの底から現在のスタックポインタまでにあるヒープ領域に取られたLispオブジェクトもしくはコード(マシンコード)っぽいものを保存する。レジスタ上でも一緒。スタックの底はpthread_attr_getstackで取得(Windows除く)。

実際に何をするかと言えば、ルート上にあるそれっぽいオブジェクトが所属するページ丸ごとピン止めするのである。ページは最低でも4096バイトあるので、ある意味漢らしい。まぁ、いろいろ考えるよりは楽だわね。(詳細はsrc/runtime/gencgc.cにあるpreserve_pointerを参照)

 タイムオーバーなので今日はこのくらいで。続きはまた明日。

2013-03-20

詳解SBCL - 世代別GC(1)

全てのSBCLソースリーディングをしている人の手助けになることを願って。

そろそろ詰め込んだものがページアウトしそうなのでちょっと外部記憶に書き出しておこう。タイトル的には仰々しいことを書くような煽りだが、実際はそうでもないのでかなり釣りです。また、誤りが含まれている可能性が多分にあるので見つけたら指摘していただけるとうれしいです。

(1)となっているのは次がある予定だから。というか、全てを一つの記事するのはきついので。

以下の記事は世代別GCとは何ぞやということが分かっている人が対象になります。また、話を可能な限り簡略にするため、環境はX86、POSIX、シングルスレッド環境とします。言及しているSBCLのソースはバージョン1.1.5のものです(2013年3月20日現在の最新)。

【概要】
SBCLではメモリの管理は、リージョン、エリア、世代、ページの4つのグループを使って行われる。簡単なイメージは以下のような感じ。
                 mutator
                    |
                 gc_alloc
                    |
+-------------------------------------------+
|                region                     |
+-------+------+----------------------------+     +---------------------------+
|  page | page | ...                        |  -- |         * area            |
+-------+------+--------------+-------------+     +---------------------------+
| generation 0 | generation 1 | ...         |
+--------------+--------------+-------------+

* エリアはGCの際にのみ使われます。
メモリは割付は必ずリージョンを通して行われ、リージョンはページの開始アドレス、現在のフリーなアドレスを保持します。
ページは使用されているバイト、リージョンからのオフセット、所属している世代、その他もろもろの情報を保持します。リージョンからのオフセットは結構重要で、ページのアドレスから実際のリージョンの開始アドレスを割り出せます。
世代は所属しているページの最初のアドレス、その他GC回数等の情報を保持します。

恐らくここまでは他の世代別GCとは大きく変わらないと思います。

実際のメモリ割付及びGCに入る前に登場人物の説明。

【ページテーブル】
SBCLでは全てのページはページテーブルで管理されます。ページテーブルはページの配列で、その個数はヒープサイズから割り出されます。実際のコードは以下の通り(src/runtime/gencgc.cgc_initより)
    /* Compute the number of pages needed for the dynamic space.
     * Dynamic space size should be aligned on page size. */
    page_table_pages = dynamic_space_size/GENCGC_CARD_BYTES;

                           :

    /* The page_table must be allocated using "calloc" to initialize
     * the page structures correctly. There used to be a separate
     * initialization loop (now commented out; see below) but that was
     * unnecessary and did hurt startup time. */
    page_table = calloc(page_table_pages, sizeof(struct page));
GENCGC_CARD_BYTESはビルド時にgenesis(多分2以降の記事で書く)で定義される値。ちなみにX86環境では4096。
dynamic_space_sizeは大域変数でSBCL起動時にヒープ指定用。デフォルトはsrc/runtime/gc-common.cで以下のように定義:
os_vm_size_t dynamic_space_size = DEFAULT_DYNAMIC_SPACE_SIZE;
ちなみに、DEFAULT_DYNAMIC_SPACE_SIZEの定義はsrc/runtime/validate.hにあり、以下の通り:
#ifdef LISP_FEATURE_GENCGC
#define DEFAULT_DYNAMIC_SPACE_SIZE (DYNAMIC_SPACE_END - DYNAMIC_SPACE_START)
#else
#define DEFAULT_DYNAMIC_SPACE_SIZE (DYNAMIC_0_SPACE_END - DYNAMIC_0_SPACE_START)
#endif
この記事では世代別GCを扱っているので、LISP_FEATURE_GENCGCは定義されている。DYNAMIC_SPACE_ENDDYNAMIC_SPACE_STARTはgenesisでビルド時に割り出される固定アドレスである。

話が逸れたので、ページテーブルに戻す。 ページテーブルはSBCLが管理するヒープ外で管理されており、具体的にはcallocで割り付けられたメモリ、当然だがGCの対象にならない。ページ、ページテーブルは実際のヒープを指すわけではなく、そのメタ情報を扱っている。実際にあるページが指すヒープは以下のように割り出される(src/runtime/gencgc.c
より):
/* Calculate the start address for the given page number. */
inline void *
page_address(page_index_t page_num)
{
    return (heap_base + (page_num * GENCGC_CARD_BYTES));
}
heap_baseDYNAMIC_SPACE_STARTと同値である(gc_initで設定されている)。1つのページはGENCGC_CARD_BYTESで区切られるのでこのように計算できる。

【リージョン】
シングルスレッド環境ではリージョンはたったの2つ、boxed_regionunboxed_regionである。基本的な違いは、前者は割り付けられたメモリ内にポインタを持ち、後者は持たないというだけのもの。たとえば、CLのconsは前者のリージョンから、basic_stringは後者のリージョンから割り付けられる。

リージョンは実際のヒープアドレスを持ち、メモリの割付を行う。

【世代】
SBCLでは6つの世代+スクラッチ用世代の7つの世代が用意されている。スクラッチ用世代はGCの際にコピー用のヒープを保持する世代で、GC対象の世代がプロモートしない場合に使用される。
他の世代別GCと同様にある一定回数のGCが行われかつ生き残ったオブジェクトは次の世代にプロモートされる。ちなみに、デフォルトでのプロモートGC回数は1回。つまり、2回生き残ると次の世代に昇格する。このパラメータはLISP側から世代毎に調整できる(src/code/gc.lisp参照)。

疲れたので今日のところはここまで。明日辺りにメモリの割付以降の話を書く。

2013-03-16

脱BoehmGCへの道 実装編(2)

昨晩BBCのコミックリリーフを見ながら(寝ながら)実装方針のようなものを考えていた。

とりあえず、SBCLがどのようにポインタ内のポインタを解決しているのかは考えないようにして(たぶんscavengeがその辺をうまいこと扱っているんだと思うけど)、まずは動くものを作ろうという感じである。

とりあえず現状での違いを列挙
【SBCL】
  • 保存するポインタは、スタック及びレジスタのみ
    • 静的領域は持ってない
    • 動的にコードを生成するのだからある意味当たり前ではある
  • 全てのポインタは中身にアクセスすることなくおよそLispオブジェクトかの判別が可能
    • これによって実際にscavenge及びtransportを行う手続きをテーブルで持つことが可能
  • 全てのポインタからおよその割付サイズを割り出すことが可能
【Sagittarius】
  • 保存するポインタは、スタック、レジスタ及び静的領域
    • 結構な勢いでstaticなオブジェクトを持っているので変更したくない
  • Schemeオブジェクトかどうかの判別にはポインタの中身を見る必要がある
    • 単なるコンテナのpairはどうしても一般的なメモリとしてしか判別できない
  •  動的領域から割り付けられたものならばメモリヘッダからサイズの割り出しが可能
    • あいまいなポインタがきた場合に多少困る
    • 一応チェックが走るけど、不安
 今更ながらにオブジェクトをタグにしておけばよかったと多少後悔しているが、まぁ泣くまい。

っで、実装戦略(というほどでもないが)だけど、現状で困っているのはポインタ内ポインタの保存である。とりあえず、スタック及びレジスタ上で参照されているポインタを動かすのは嬉しくないのでこいつは無視して(不可能ではないが)、静的領域である。
いったん保存されたアドレスはページ単位で移動を禁止される、なので保存先のアドレスから中身をたどっていき全てのオブジェクトを新たな世代(もしくは単にページ)に移動させる。この際に既に保存されているものであれば動かしてはいけないのでそのままにする必要がある。そうすると、たどれるポインタのうち、スタック、静的領域及びレジスタ上にないものは全て昇格することになり、世代別GC的に動く(ような気がする)。
ここで気になるのは、スタック上で保存されたポインタで、こいつからたどれるものはどうしようかなぁというところである。まぁ、静的領域と同様にやってしまってもいいような気はするのだが、そうするとまだ保存されていないポインタを動かすことになるような気がしている。あぁ、でも動いた先をいれてやれば問題ないのか?あんまりアグレッシブに動かすと1が10になる問題が起きるよなぁ。

とりあえずこの方針で行くことにする。

2013-03-15

脱BoehmGCへの道 準備編(4)

実装編書いたのに準備編に逆戻りw

コードリーディングに関するのは準備編にまとめようと思っているだけなので実装をしていないわけではないんだけど、妙な感じではある。

SBCLのコードを読んでてどうも納得がいかないというか、理解ができていない部分がある。オブジェクトのコピーである。他のGCと同様SBCLも世代別GCも最初にスタックエリア、静的エリア(SBCLが内部で持ってるもので、.dataとかではない)におかれているポインタの保存をした後にごみ集め(scavenge)するようになっている。

まぁ、これだけ見れば特に問題ないように見えるんだけど、世代別GCではコピーが発生する。コードを読んでいるとscavenge_newspace_generationがコピーを行うとコメントに書いてあるのだが、 最終的にそいつはscavengeにたどり着き普通に回収しているように見える。また、ポインタを保存する際にそのオブジェクトが保持している中身には一切の興味を示していない。つまり、ルートからたどれる最初のオブジェクトしか保存していないようにみえるのだ。(実際は、ページ丸ごと保存しているので4096バイト(32ビット?)ごそっと保存してるんだけど。)

これはLisp側のコードも解析しないといけないかなぁと思い、ちょっと眺めてみた。知っている人は知っていると思うけど、SBCLはVOPと呼ばれる仮想アセンブリ言語があってこいつが非常に読みづらい。頑張ってたどっていくと、X86環境ではメモリの割付はallocation手続きからalloc_overflow_*(ecxとかとか)が呼ばれ最終的にCで定義されたallocそして、世代別GCならgeneral_allocが呼ばれることが分かった。ということは、Lisp側で割り付けられようが、CのAPI使おうが(SBCLは外部にAPIを公開してないので不可能だけど)、最終的には同じメモリが同じように割り付けられているはずである。

となってくると、たとえばベクタなんかが中にLispオブジェクトを保持していた場合どうにかしてコピーしないとまずいことになると思うんだけど、どうなってるんだ?確かに、scav_other_pointerではオブジェクトの最初のアドレスからヘッダをとってコピーしてるんだけど、こうあるべきなのか?

そもそも、general_allocを勘違いしている可能性があるといえばあるんだけど・・・

Sagittarius 0.4.3 リリース

Sagittarius Scheme 0.4.3がリリースされました。今回のリリースはメンテナンスリリースです。
ダウンロード

【修正された不具合】
  • evalがunbound variable errorを投げる不具合が修正されました
  • 閉じられたソケットに対してsocket-sendを呼ぶとSIGPIPEで落ちる不具合が修正されました
  • キャッシュファイルをロードする際にライブラリのインポート順序が逆順になっている不具合が修正されました
  • bytevector->stringがSIGILLを起こす不具合が修正されました
  • R7RSのloadにenvironment引数を渡すとカスタムリーダが認識されない不具合が修正されました
【改善された点】
  • メモリの使用量が多少少なくなりました
【新たに追加されたライブラリ】
  • リモートREPLライブラリ(sagittarius remote-repl)が追加されました
【新たに追加された機能】
  • (rfc tls)がサーバソケットとTLS 1.2をサポートするようになりました
  • (rfc x509)ライブラリに基本的な証明書を作成するための手続きが追加されました
  • (rfc x509)に証明書をバイトベクタに変換する手続きが追加されました

2013-03-14

脱BoehmGCへの道 実装編(1)

SBCLの保守的世代別GCを参考(*1)に自前GCをちょぼちょぼ実装している。メモリの割付はいけるがGCがうまいこと動いていないのですぐにSEGVる。

とりあえず現状ぶつかっている妙な挙動と実装上のメモ

【実装上のメモ】
  • SBCLではヒープに割り付けられたメモリは*ほぼ*Lispオブジェクトとして扱える
    • 一部違うものもあるっぽいが、少なくとも2ワードはあると断定できるらしい
    • Lispオブジェクトならヘッダーが第一ワードにきて、そいつからサイズも特定できるっぽい
    • さすがにこれは真似できない
  • ↑をなんとかするためにメモリブロック+ヘッダという構造を導入
    • サイズとフォーワードチェック用の構造体
      • フォーワードチェック用に1ビット、残りはファイナライザを詰める
    • アライメントの関係上2ワード取るようにする
    • 32ビットなら8バイトの無駄
    • でも、ファイナライザもいれないといけないしということで妥協
  • スタックの底は頑張ってOSコールで取るようにした
  • データセグメントは_data_startとかで頑張る
    • Windowsはどうしようかね?
    • 前に書いたハックで頑張るか
  • Cygwin上のmmapについて
    • MAP_NORESERVEを指定しないようにした
    • 512MB必要としているので、Cygwinのメモリだとスワップ領域を確保しないときついはず、ということで
【妙な挙動】
主な開発環境はCygwinなので、とりあえずの妙な挙動はCygwinということになる。っで、妙な挙動。

静的領域を取るためにCygwinでは_data_start__系の値を使うのだが、GDB上で見ると正しく取れているように見えるんだけど、実際には意味不明な値が飛んできている。 たとえば、GDB上では開始アドレスは0x6a5a4000となっているんだけど、実際には0x3000とどう見てもアドレスに見えない値が取れている。

追記:
多分メモリ破壊的な何かが起きてる感じである。最初のGCではOKなのに2回目で死んでる。

追記の追記:
単にアホなミスであった。まず自分から疑うべきである・・・

*1 参考=コピペとも言う。コピペプログラマは適当にアジャストするのも得意なのであるw

2013-03-06

脱BoehmGCへの道 与太話

SBCLのコードを読んでいると、コンパイラとかデバッガを作るということがいかに環境べったりのコードを書く必要があるかということを実感させられる。もちろん、それを#ifdefで区切るのか、もっと抽象化してやるのかは実装者の好みだろう。

コード読んでて感動したのが以下のコメント。
    /* On entry %eip points just after the INT3 byte and aims at the
     * 'kind' value (eg trap_Cerror). For error-trap and Cerror-trap a
     * number of bytes will follow, the first is the length of the byte
     * arguments to follow. */
    trap = *(unsigned char *)(*os_context_pc_addr(context));
これは、Windowsなら、handle_breakpoint_trap、x86環境ならsigtrap_handlerにあるコードなんだけど、どうやってその'kind'を飛ばしているかというと以下のアセンブラから飛んでくる。
 .globl GNAME(do_pending_interrupt)
 TYPE(GNAME(do_pending_interrupt))
 .align align_16byte,0x90
GNAME(do_pending_interrupt):
 TRAP
 .byte  trap_PendingInterrupt
 ret
 SIZE(GNAME(do_pending_interrupt))
別にdo_pending_interruptである必要はないけど、ようするにこんな感じで飛ばすのである。んで、C側ではEIP(x86)の次のバイトを読む。SIGTRAP飛ばすのにint3もしくはud2使ってる。ud2だとSIGILLか。

最初なんでOSのPCなんて必要なんだろうと思ったけど、こういう理由でいるみたい。「完全解説SBCL」なんて本が出たら多分買うと思う。

2013-03-05

脱BoehmGCへの道 準備編(3)

実際のコードの準備に入る。

Twitterでも呟いたのだが、SBCLは*_SPACE_(START|END)という奇妙な固定アドレスがあって、これらは環境(OS、アーキテクチャ)によって値が違う。Genesisというビルド時に走るソース生成のLispがこいつらを作るのだけど、この値を使ったら負けな気がしてるのと、ポータビリティが下がるどころの話じゃないのでなんとかデータセグメントをランタイムで取れないかを探っている。(ここまで前置き)

Linuxとか*BSD環境だと、etextとかedataとか使えるのだけど(GCC?)、Windowsだとそうは問屋がおろしてくれない。Boehm GCはこの辺をMEMORY_BASIC_INFORMATIONと多少のハックで何とかしているのだが、.dataセグメントをとるのなら以下の方法でもいけることが分かった。
/* dll.c */
#include <windows.h>
#include <winnt.h>
#include <dbghelp.h>
#include <stdio.h>

__declspec(dllexport) void dump(HANDLE hModule)
{
  char *dllImageBase = (char*)hModule;
  IMAGE_NT_HEADERS *pNtHdr = ImageNtHeader(hModule);
  IMAGE_SECTION_HEADER *pSectionHdr = (IMAGE_SECTION_HEADER *) (pNtHdr + 1);
  int i;
  printf("base   : 0x%p\n", dllImageBase);
  for (i = 0 ; i < pNtHdr->FileHeader.NumberOfSections ; i++) {
    char *name = (char*) pSectionHdr->Name;
    printf("name   : %s\n", name);
    printf("section: 0x%p\n", dllImageBase + pSectionHdr->VirtualAddress);
    printf("size   : %d\n", pSectionHdr->Misc.VirtualSize);
    pSectionHdr++;
  }
}

__declspec(dllexport) int show()
{
  HANDLE hModule = GetModuleHandle("dll.dll");
  dump(hModule);
  return 0;
}

/* linked.c */
#include <windows.h>
#include <winnt.h>
#include <dbghelp.h>
#include <stdio.h>

__declspec(dllimport) int show();

int main()
{
  HANDLE hModule = GetModuleHandle(NULL);
  char *dllImageBase = (char*)hModule;
  IMAGE_NT_HEADERS *pNtHdr = ImageNtHeader(hModule);
  IMAGE_SECTION_HEADER *pSectionHdr = (IMAGE_SECTION_HEADER *) (pNtHdr + 1);
  int i;
  printf("base   : 0x%p\n", dllImageBase);
  for (i = 0 ; i < pNtHdr->FileHeader.NumberOfSections ; i++) {
    char *name = (char*) pSectionHdr->Name;
    printf("name   : %s\n", name);
    printf("section: 0x%p\n", dllImageBase + pSectionHdr->VirtualAddress);
    printf("size   : %d\n", pSectionHdr->Misc.VirtualSize);
    pSectionHdr++;
  }

  printf("should be in DLL\n\n");
  show();

  return 0;
}

/* load.c */
#include <windows.h>
#include <stdio.h>

typedef void (*Dump)(HANDLE);

int main()
{
  HMODULE handle = LoadLibrary("dll.dll");
  Dump dump;

  dump = (Dump)GetProcAddress(handle, TEXT("dump"));
  if (dump) {
    dump(handle);
  } else {
    printf("something wrong\n");
  }
  return 0;
}
問題なのはLoadLibraryではなくリンクされた方だったりする。GetModuleHandleは.exeのハンドルを取得するらしく、DLLの名前を渡さないと.exeと同じアドレスになった。おそらくDllMainでDLLがアタッチされた際に引数として渡されるハンドルを保存しておくのがいいだろう。LoadLibraryの方は逆にハンドルが返されるので、既存の拡張DLLのコードをいじることなくいけそうである。

唯一これが問題だなぁと思うのは、dbghelp.libをリンクする必要があることだろうか。おそらくXP以上の環境ならMSVCライブラリを入れなくてもあると思うんだけど、ちょっと不安。

ふとBoehm GCのこの辺のハックを読んだときに思ったのだが、Boehm GCってDLLを呼ぶたびにGC_INIT呼ばないとまずいのかな?それともLoadLibraryをフックしてる?じゃないとDLLごとの静的領域がルートに入らない気がするのだけど・・・

2013-03-04

脱BoehmGCへの道 準備編(2)

Scheme48の世代別GCを読むと言ったな、あれは嘘だ・・・orz

引き続きSBCLの世代別GC。さすがにこの規模のコードを2,3時間でっていうのは無理があって、読んでるうちにいろいろ発見がある。

GC自体はcode/gc.lispで定義してあって、こいつが世界を止めてごみ集めしてまた世界を動かしてる。これは誰が読んでるんだ?メモリ割付はGCが必要かどうかのフラグをセットしてるだけだし。
以下はメモ:
  • Windows以外の環境ではsignal (SIG_STOP_FOR_GC: SIGUSR2)を使って世界を止めてる
    • Windowsではそんなシグナルないので、safepointと呼ばれるものでごにょごにょしてる
    • 多分CreateEventで何とかなるか?
  • 世界を止めるために作られたスレッドを全て管理している
    • そんで、pthread_killでSIG_STOP_FOR_GCを送りスレッドを止める
    • なんで現在のスレッド以外を再び起こしてるんだろう?
      • そして起こせたらエラーで死んでる・・・
      • 単なる再チェック?
  • シグナルを送らないとGCが発生しないように見えるけど、シグナル送るのはstop the worldという矛盾
    • interrupt_handle_pendingのコメントに書いてあった
      • allocが*gc-pending*にtを入れる
      • set_pseudo_atomic_interruptedが呼ばれる
      • do_pending_interruptが呼ばれる(アセンブラなんだぜこれ・・・)
        • int3もしくはud2命令でSIGTRAPを送る
        • 後ろにtrap_PendingInterruptをつけて識別する
      • handle_trapが起動される
      • ようやくinterrupt_handle_pendingにたどり着く・・・
なんでここまでしてシグナルを使いたいのかは不明。いろんな兼ね合いがあるのだろう。(シグナルを送るとスレッドのことを考えなくてもいいとか?GCの起動をぎりぎりまで遅らせたいとか?)

なんとなくばらばらなピースが合わさってきた感じがする。

2013-03-03

脱BoehmGCへの道 準備編(1)

2があるかは知らない。(たぶんある、Scheme48で)

SBCLは2種類のGCをサポートしていて、(たぶん)デフォルトでは保守的世代別GCが使われている。しかも、ランタイムの部分はCで書かれているといるので、これは読まなければならないだろうと思って読んだ(理解は微妙・・・)。

世代別GCがなんぞやという人はここが詳しい:GCアルゴリズム詳細解説

GCを実装する上で(個人的に)重要な点は、割付とGC部分の2箇所。メモリに対してどんなメタ情報を付与するのかと、どのようにルートをたどるのかという部分。この辺はGCレベル(何それ?)が高い人は違うのかもしれないが、レベル1以下の僕にはそう見える。

SBCLはメモリの割付をリージョンと呼ばれるヒープから割り付ける(スモールオブジェクト)。っで、こいつはページテーブル内で管理されていて、必要に応じて拡張されたりしている。(まじめに追ってない・・・)。

GCは保守的になる必要がある場合のみに保守的に行われる。具体的にはX86、X86_64な環境。ただし、それらの環境でもgc_and_saveで呼び出された場合はPreciseで行われる。(たぶんコアイメージの保存用?)。
保守的なGCは外部C呼び出し(Foreign C call)の際にのみ起きる(とコメントにある)ので、スレッドコンテキストからその辺りのPCを持ってきてポインタらしきものをマークしている。マークが終わると回収なのだが、回収はX86、X86_64以外の環境ではスタックを問答無用で回収する。どういう仕組みでX86、X86_64以外の環境がPrecise GCになるのかは(今のところ)不明。(FFIが無いとか言うシンプルな理由かもしれない)。回収自体はポインタサイズ(種類?)で回収の仕組みが違う。それぞれに適した回収と移動が実装されている。(うへぇ・・・)

読んでて気になったというか、やっぱりなぁと思ったのは、保守的GCという性質上どうしてもOS、アーキテクチャ依存の部分が出ざるを得ないということ。SBCLはその辺がかなりうまく分離されているので対象のコードを読むこと自体はあまり苦ではないのだが、自前でGCを持つということはBoehmGCが行っているハックを大なり小なりやる必要があるということが分かってちょっとがっかり。
後、SBCLはビルド時にホストとターゲットをビルドするのだけど、ホストがランタイムの設定及びヘッダファイル郡(genesis)を生成する。もっとも気になるのはthread.hでこいつはGCのコードでもスレッドコンテキスト等を取得する際に多用されている。これがビルド時に生成されるということは、ターゲットの環境によって中身が大きく変わる可能性があるということ(構造体のオフセットまで全部生成されてるし)。

規模が規模だけに全部を把握するのは難しいが、参考になる部分はたぶんにありそう。

2013-03-02

脱BoehmGCへの道 計画編

別にBoehmGCに対してそこまで不満があるわけではないのだけど、Sagittariusは既にインストールされているライブラリ(Unix系環境)もしくは新規にダウンロードして特に手を入れることなく使う(Windows環境)という手法をとっているので、サポートしていない環境で動かすのに支障がでる。(たとえばFreeBSDの最新のportsでは不具合があってSEGVる)

それ以外だとGaucheやMoshみたいにGC_sizeから割り付けられたサイズを求めてごにょごにょするといいったことができないとか、多少の不満があったりはする。

そこでとりあえずなんとかならないだろうかと思い計画+どうしようこれ?的な問題点を思いつくままにずらずらと。

計画(妄想)的な何か
  • 世代別GCにしたい
    • 特に理由はないけど、大域定義とかはGCされる率は極めて低いので効果的な気がする
    • Scheme48の最新版は世代別GCを実装してるし
  • パラメータでGCの挙動をチューニングできるようにしたい
  • メモリ割付を安価にしたい
    • Ypsilonはメモリの割付がおそらくすごく高速(ctak見て思ったこと)
    • BoehmGCはベンチ取ったことないから知らないけど・・・
問題的な何か
  • Conservative GCかPrecise GCか
    • 世代別ならPreciseじゃないとまずいのか?
    • 現状のコードを書き直さないようにしたい
    • Conservativeな世代別GC?(可能なの?)
  • マルチスレッド環境をどうするか
    • ヒープの場所をどうするか
      • スレッド毎に持つ
        • 子スレッドが死んだ時にどうする?
      • ヒープはメインスレッドのみが持つ
        • 割付ごとにロックする
        • 遅くね?
    • スタックの底をどうするか
      • あんまりスレッドモデル依存にしたくない
      • かといってアーキテキチャ依存もなぁ(espとかrspとか?)
たとえばYpsilonは自前GC(コピーもしくはコンパクションはしなかったはずだからマーク&スイープかな)だが、ヒープはVM毎に持っていて子は親を参照できるけど書き換えられないとかあったはず。http://d.hatena.ne.jp/fujita-y/20081121/1227252054

RacketはPrecise GCなんだけど、↓なので参考にならない・・・

Scheme48の実装を理解しつつ分散GC的な何かを理解するという地道な方法しかないだろうか。できれば、サクッと作って「GCは自前じゃないとね」とか軽口を叩いてみたいのだが・・・

誰かこの本を献本してくだしぁ(ぉぃ