暗号ライブラリの不満

Sagittariusは自前で暗号ライブラリを持っているのだが、ちょっと不満が出てきた。何が不満かと言えば、DES3の鍵生成で必ず24バイト要求するというものだ。これだといわゆるDES2が使えなくて、でも16バイトの鍵がわたってきた場合に困ることになるというもの。

現状では秘密鍵の生成は以下のようにして鍵オブジェクトを作ってやる必要がある。

(import (crypto))
(generate-secret-key DES3 #vu8(...)) ;; must be 24 byte bytevector

generate-secret-keyは総称メソッドなので、DES3がわたってきた際に特異なものを作ってやればいいという話になる。

本来ならという注釈がつくのがポイント。ドキュメントにちょろっと書いてあるのだが、この鍵アルゴリズムの名前は専用のクラスを作って唯一のオブジェクトを登録するのが望ましい、と書いてあるだけだったりする。つまり、なんでもいいのである。 (今思ったのだが、なんでオブジェクトを作る必要があるんだ？クラスだけでもいいんじゃね？) っで、その裏ルールに則って組み込みの秘密鍵なアルゴリズムは文字列が登録されていたりする。(これはバックエンドで使っているLibTomCryptoが文字列でディスクリプタを登録しているため)

そんなときのためにeql-specializerがあるんじゃないかとも思ったのだが、こいつは組み込みではサポートしていないので総称メソッドの定義時にメタクラスとして指定してやる必要があってうまくいかない。

解決方法はとりあえず思いつく中でスマートなものは以下の2つ。

1. RSAと同様に秘密鍵のアルゴリズムも文字列じゃない何かにする
2. eql-specializerを組み込みでサポートする

1.はクラスの階層を考えたり、現在サポートしている全てのアルゴリズムに適用する必要があったりでひたすら面倒だけど王道な解決策。
2.はどこと無くadhocな感じはするが、eql-specializerが組み込みに出来るチャンスともいう。

さて、どっちにしようかな・・・

FFI周りの改善

SagittariusのFFIでCの構造体を定義する際にメタな情報を付与してユーザーにアライメントの計算を強いないようにしている。ここまでは単にユーザーフレンドリな仕様で済むんだけど、内部のアライメント計算処理があまりにも適当すぎて32ビットと64ビットでの違いが吸収できてないとか、オフセット計算が間違ってて特定のメンバにアクセスするとSEGVるとかのバグがちらほらあった。

個人的にあまり問題にしていなかったのだが(Cの構造体を弄る場面が少なかった) 、なんとなく隙間の時間があったので「えいやっ！」と直すことにした。

0.4.4以前で問題になるのは以下のようなコード。

(import (sagittarius ffi))
(define-c-struct foo
  (int   i0)
  (char  c)
  (short s)
  (int   i1))
(size-of-c-struct foo)

定義された構造体のサイズは12(sizeof(int) == 4)でなければならないが、0.4.4では11を返す。これは、構造体のパディングとサイズの(意図的ではないが)ルールを無視しているためだったりする。また、メンバのオフセット計算もおかしかったりで、複雑な構造体を扱うのは危険だったりもした。(メンバが全部intとかvoid *もしくは型が違ってもサイズが同じとかなら問題はない。)

とりあえず、以下のWikipediaのページを参考にしつつ、もうちょっとまともな計算をするように改善。
http://en.wikipedia.org/wiki/Data_structure_alignment
現在のHEADではかなりまともな計算をするようになっている。(個人的に怪しい部分はあったりするが・・・)

また、define-c-structの定義をちょっと変えて、アクセサを同時に定義するようにした。たとえば上記の構造体なら以下のアクセサが自動的に定義される。

foo-i0-ref
foo-i0-set!
 ...
foo-i1-ref
foo-i1-set!
;; 参考 foo-i0-refとfoo-i0-set!の定義イメージ
(define (foo-i0-ref p)
  (c-struct-ref p foo 'i0))
(define (foo-i0-set! p v)
  (c-struct-set! p foo 'i0 v))

実際には内部構造体のメンバを扱うためにオプショナル引数を受け付ける。このオプショナル引数は個人的には美しくないと思っているので(特に-set!側)、なんとかしたいのだがいい案が思いつかない。

さらに、構造体の定義内に配列を含めた際の参照と代入が(ほぼ全く)サポートされていなかったのでそれも直した。配列で定義されたメンバの参照をすると現在はベクタを返すようになっている。代入もベクタで行う必要がある(以前は代入は自前でオフセット計算してやる必要があった)。

個人的にこの辺の機能を使うことがほとんどないので、誰かハードに使ってくれる人を募集してますｗ

Yet Another Syntax-case Explanation

Unlikely my (own) rule, this article is in Japanese (if you want it in English, please comment so).

世の中syntax-caseの解説なんて(たぶん)山ほどあるだろうけど、もう一つGoogleの検索結果を汚してやろうという話。

この記事のsyntax-rulesは使えるけど、syntax-caseとwith-syntaxを絡めて使えないという方をターゲットとしてます。マサカリ大歓迎ですw

【syntax-caseって】
まずは、簡単にsyntax-rulesとsyntax-caseの違いを見てみよう。

(import (rnrs))
(define-syntax print-rule
  (syntax-rules ()
    ((_ o o* ...)
     (begin (display o) (print-rule o* ...)))
    ((_ o)
     (begin (display o) (print-rule)))
    ((_) (newline))))

(define-syntax print-stx
  (lambda (x)
    (syntax-case x ()
      ((_ o o* ...)
       #'(begin (display o) (print-stx o* ...)))
      ((_ o)
       #'(begin (display o) (print-stx)))
      ((_)
       #'(newline)))))

どちらのマクロも同じことをします。これだけ見れば、違いは以下ぐらい：

• syntax-rulesがsyntax-caseになった
• lambdaで囲まれて、syntax-caseの引数(と呼ぶのもおかしいが)にlambdaの引数が渡った
• テンプレート部分がsyntax (#')で囲まれた

はい、この程度のものを書くならsyntax-rulesだけで十分です。じゃあ、syntax-caseを使うと何が嬉しいのか見ていきましょう。

【低レベルな操作】
何を持って低レベルとするのかはさておき、ここでは与えられて式の内容を操作することを低レベルと呼びます。syntax-rulesでは式の変形はできても、中身を操作することはできません。たとえば以下のようなコードは、syntax-rulesでは実現不可能です。

(define-syntax define-foo-prefix
  (lambda (x)
    (define (add-prefix name)
      (string->symbol 
       (string-append "foo-" (symbol->string (syntax->datum name)))))
    (syntax-case x ()
      ((k name expr)
　　　　　　;; need datum->syntax to compliant R6RS
       (with-syntax ((prefiexed (datum->syntax #'k (add-prefix #'name))))
         #'(define prefiexed expr))))))

(define-foo-prefix boo 1)
foo-boo ;; -> 1

さて、ここでwith-syntaxが出てきました。こいつが何をしているのかの説明がこの記事のメインなのでここで解説です。

構文的なものはR6RSでも見てもらえばいいとして、何をしているのか。名前が示すとおり、with-syntaxは新たに構文オブジェクトの束縛を作ります。 ここでは、prefixedがそれにあたります。なぜこんなことが必要かといえば、syntax-caseのテンプレートは構文オブジェクトを返す必要があるからです。そして、syntax (#')構文内では構文オブジェクトの束縛のみが参照可能ということも大きな要因です。上記のような、低レベルな操作を健全なマクロで行うためにあるといっても問題ないでしょう。

また、with-syntaxで作られた構文オブジェクトが保持する情報も重要になってきます。R6RSではテンプレート部分にどこにも定義されていない名前が出てくると、それはユニークな名前に変更されます。define-valuesなどの定義で、dummyとか使われているあれです。しかし、with-syntaxで束縛された構文は束縛された名前がそのまま使えます。

いまいちイメージがつかめない方のために、R5RSとCommon Lispのマクロの議論でよく引き合いに出されるaifをwith-syntaxを使って書いて見ましょう。こんな感じの定義になると思います。

(define-syntax aif
  (lambda (x)
    (syntax-case x ()
      ((_ pred then)
       #'(aif pred then #f))
      ((k pred then else)
       ;; ditto
       (with-syntax ((it (datum->syntax #'k 'it)))
         #'(let ((it pred))
             (if it then else)))))))
(aif (memq 'a '(b c a e f)) it 'boo) ;; -> (a e f)

aifはpred部分の評価結果を変数itに暗黙的に束縛します。なので、マクロユーザからはその定義は見えず、いきなり現れたように見えます。Schemer的にはいまいち気持ち悪い気もしますが、あれば便利な機能です。
ここで使われているwith-syntaxが何をしているかといえば、シンボルitを構文オブジェクトに変換してテンプレート内で参照可能にしています。このitはリネームされないため、あたかも突如現れたかのように使うことができるのです。

【それ、quasisyntaxでもできるよ？】
はい、できます。with-syntaxとquasisyntaxはほぼ同等の力を持っていると思っていいです。なので、上記の例は以下のように書き換えることが可能です。

(define-syntax define-foo-prefix
  (lambda (x)
    (define (add-prefix name)
      ;; ditto
      (datum->syntax name
       (string->symbol 
 (string-append "foo-" (symbol->string (syntax->datum name))))))
    (syntax-case x ()
      ((_ name expr)
       #`(define #,(add-prefix #'name) expr)))))

(define-syntax aif-quasi
  (lambda (x)
    (syntax-case x ()
      ((_ pred then)
       #'(aif pred then #f))
      ((k pred then else)
       ;; ditto
       (let ((it (datum->syntax #'k 'it)))
       #`(let ((#,it pred))
           (if #,it then else)))))))

どちらの方がいいかはユーザの感性に寄るとは思いますが、個人的にはwith-syntaxを使った方が綺麗かなぁと思います。quasisyntaxはCommon Lispのマクロを連想させるという理由だけなのですが・・・。ただ、あまりに多くの構文を導入する必要があると無駄に長くなるという弊害もあるので、ケースバイケースで使い分けるのがいいでしょう。

追記：
Twitterで早速突っ込みが入ったのでdatum->syntaxで明示的に構文オブジェクトに変換するようにコードを修正。SagittariusとYpsilonはこの辺多少チェックがゆるい。
それに伴って多少文言の修正。with-syntaxは構文オブジェクトを束縛する等々。

SRFI-111

今一なんの意味があるのかよく分からないSRFIなんだけど、実装するのが非常に簡単だから実装してみた。こんな感じ。

(library (srfi :111 boxes)
    (export :export-reader-macro
     box box? unbox set-box!)
    (import (rnrs)
     (clos user)
     (sagittarius)
     (sagittarius reader))

  (define-class <box> ()
    ((value :init-keyword :value :reader unbox :writer set-box!)))
  (define-method write-object ((b ) port)
    (format port "#&~s" (unbox b)))
  (define (box? o) (is-a? o ))
  (define (box o) (make  :value o))

  (define ctr #'box)
  (define-dispatch-macro #\# #\& (box-reader port c param)
    (let ((datum (read port)))
      `(,ctr ',datum)))
)

(library (srfi :111)
    (export :all :export-reader-macro)
    (import (srfi :111 boxes)))

要求されているリーダーマクロまで入っているという優れものw
こんな感じで書ける。

#&abc              ;; -> #&abc
(unbox #&abc)      ;; -> abc 
(set-box! #&abc 1) ;; -> #<unspecified>

リーダが読み込んだBoxはimmutableが好ましいとは言われているけど、 そこは気にしない。とりあえず手元にある処理系でこのリーダーマクロをサポートしてるのはRacketのみだったという事実もあったりする。

参照実装がR7RSのライブラリ形式を使っているのも面白い。まだ決まってないけど・・・(まぁ、ここからこけるということもないんじゃないかなぁとは思っているが)

脱BoehmGCへの道 実装編(4)

あきらめてはいないという意思表示ｗ

いや、実際あきらめてなくて、未だに戦ってるんだけど、これ書くということはどうしようかなぁという問題が発生したということでもある。

問題は、あるオブジェクトAの中にあるオブジェクトBがAより後に回収された際に起きるアドレス更新の問題。(ひょっとして#3でも同じ問題を扱ったかもしれない。)
具体的にはユーザー定義のクラスAが同じくユーザー定義のクラスBを基底クラスとして持っていた際に、Aが先に回収されるとAのクラスタグであるBが古いアドレスを指したままとなりさまざまな場面でSEGVを発生するという問題になる。具体的にこれを発生させるコードは以下のようなの：

(import (clos user) (sagittarius control)
        (sagittarius mop validator))
(define-class <person> (<validator-mixin>)
  ((name   :init-keyword :name)
   (gender :init-keyword :gender
           :validator (lambda (o v) (or (memq v '(male female))
                                        (error 'boo))))))
(define-class <business-man> (<person>)
  ((job    :init-keyword :job)))
(let ((man (make <business-man> :name 'john :gender 'male :job 'neet)))
  (dotimes (i 10000) (make-vector 1000))
  (print (slot-ref man 'name))
  (print <person>)) ;; Boom!!

<person>が持ってる<validator-mixin<が回収されても更新されないので出力しようとした際に不正なアドレスを指して死亡する。 こういうのが発生するとクラスタグみたいなのは単なるタグにしておけばよかったと後悔するのだが、これはこれべ便利なので泣かない・・・

うまい解決方法が思いつかないのだが、タグに使われているクラスがGC対象のスペースにあった場合は先に回収してしまうという荒業でいけるだろうか？ただ、scavengeが後で呼ばれることになるのでその際に既に移動してるって怒られる気がするんだよなぁ。 まぁ、とりあえず試してみるか・・・

R7RS ratification vote

The reason why this is English article is simply I don't know the proper translation of  'ratification vote' and felt it's awkward to write it in hiragana or katakana. Sorry, my bad :)

The ratification vote has been started. I'm not quite sure if I will vote or no and if I would, I would vote to 'yes' that's because Sagittarius has whole functionalities, not because I totally agreed with it.

Nobody expects 100% agreement, I believe, probably 70 to 80%. However mine is much lower than it. The reason is it's not stepping forwards but backwards. These are the stuff I think R7RS went backwards from R6RS.

[Low level macro]
A lot of *pure* Schemer think syntax-case is too huge to be in the specification. Actually I totally agree with it (well, that's because it was really hard to implement but as user's perspective it's really convenient). However, R6RS at least put low level hygiene macro in it. I think that's a big step forward. On the other hand, R7RS simply removed it without alternatives. I know it is hard to decide which low level hygiene macro should be in. And now we don't have any way to make R7RS macros compatible with R6RS macros except syntax-rules.

I'm following the discussion since 2011 (I guess) and probably missed why they dropped it without any alternatives. But I can guess the reason, low level hygiene macro is too big to put in RnRS so they probably thought let WG2 handle this. It might be a clever decision but since we already have it, then it is definitely not the best decision, that's because implementations don't have to implement all of libraries defined in WG2.

[Library syntax]
I agree R7RS library syntax much more flexible and convenient than R6RS one. However that simply made existing R6RS libraries not to be able to run in R7RS implementations. As far as I know, currently only 2 implementations are fully implemented with R7RS, Chibi Scheme and my Sagittarius (if you know other, please let me know. I want to try). And Chibi only supports R7RS library syntax means it can't use useful R6RS libraries (like industria or so, before you say 'is there such a library?' :P).

They were probably aiming to use R5RS codes on R7RS implementation easily, like SSAX or so. However, I'm doubting if it was a better way. I don't know why they needed to introduce the brand new  syntax instead of using the existing one. For me, it seems they simply didn't like R6RS or maybe try not to make any confusion.

[Reader macro]
As you already know, reading R6RS source code might not be possible on R7RS implementation because of the difference of bytevector lexical syntax. I totally have no idea why they changed this. I know it's different from SRFI-4 but SRFI is not a specification. Not all Scheme implementation has extensible reader macro like Common Lisp so this simply breaks capability even just reading S-expression file written by R6RS implementation. Honestly, this totally sucks!

I've been feeling that R7RS was for people who didn't agree with R6RS or even hate. I know that's not true. I believe the Scheme spirit is not dropping off the necessary functionalities nor reminiscing good old days. But why R7RS looks like this? Or maybe that's because I'm not a pure Schemer?

At least there are loads of good stuff, one of them is implementing R7RS Scheme would be much easier than implementing R6RS one. So there would be loads of Scheme implementations again :P

Sagittarius 0.4.4リリース

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

修正された不具合

•  sqrtに巨大数を与えると非正確数が返される不具合が修正されました
• (atan 0.0)がエラーになる不具合が修正されました
• string-scanが不正な値を返す不具合が修正されました
• get-output-string及びget-output-bytevectorから一度しか値が取り出せない不具合が修正されました
• UTCタイムオフセットがマイナスの地域でcurrent-dateがエラーを投げる不具合が修正されました
• aproposが動作しない不具合が修正されました

 改善点

• 巨大数のexptのパフォーマンスが改善されました

新たに追加された機能

• shared-object-suffix及びset-pointer-value!手続きが(sagittarius ffi)に追加されました
• dbi-fetch-all!に既定処理が実装されました
• key-check-value手続きが(crypto)に追加されました
• ->tlv及びread-tlv手続きが(tlv)に追加されました
• 64bitと32bitの識別子がcond-expandで使えるようになりました

TLVの構築

職業柄TLVとかスマートカードとかよく使うのだが、使う割りにパースするだけで構築するのが無かったので作ることにした。とりあえず現状で必要だったのはAPDUのデータの部分に必要なTLVの構築。

というか、作った。以下のように使える。

(import (tlv))

(->tlv '((#xC9 (#x4F . #xA000000310) ;; AID的な何か
               (#xA0 1 2 3 4))       ;; この行は適当
         (#xEF)))                    ;; タグEF 長さ0の値
;; -> (#<tlv :tag C9> #<tlv :tag EF>)
;;    => C9 0D 4F 05 A0 00 00 03 10 A0 04 01 02 03 04 EF 00

;; バイトベクタに変換するのはちと面倒だけどこんな感じ
;; tlv-list->bytevector作った方がいいかな？
(bytevector-concatenate (map tlv->bytevector (->tlv '(...))))

一応以下のようなS式を受け取ることができる。

tlv-list      ::= (tlv-structure*)
tlv-structure ::= (tag . value)
tag           ::= <integer>
value         ::= ((tlv-structure)*) | <bytevector>
               |  <integer>    | octet*

値部分のオクテットと整数はそれぞれu8-list->bytevector、integer->bytevectorでバイトベクタに変換される。正直これの必要性を今のところ感じていない。半分くらい勢いで入れてしまった。

実装してて思ったのは、TLV形式とS式の親和性は抜群にいいということ。まぁ、バイナリ版XMLみたいなもの(というと大分違うが、柔軟性という意味)なので、なんとなく分かっていたことではある。

自分以外にこのライブラリを使う人がいる気がしないのがポイントだろう。みんなもっとSchemeでスマートカードの操作をするべきである(暴言)

健全なマクロ

探せば山ほど解説があるので、今更というかGoogle検索の妨害するだけな気がするけど。

Twitterで健全マクロの実装をされている方がいて、そういえばコンパイラの環境を重点に置いた解説記事ってあったかなぁと思ったのがきっかけ。たぶんどこかにあるだろうけど・・・

まずは以下のコードを考える。

(import (rnrs))
;; from Ypsilon
(define-syntax define-macro
  (lambda (x)
    (syntax-case x ()
      ((_ (name . args) . body)
       #'(define-macro name (lambda args . body)))
      ((_ name body)
       #'(define-syntax name
           (let ((define-macro-transformer body))
             (lambda (x)
               (syntax-case x ()
                 ((e0 . e1)
                  (datum->syntax
                   #'e0
                   (apply define-macro-transformer
                          (syntax->datum #'e1))))))))))))

;; hygiene
(let ((x 1))
  (let-syntax ((boo (syntax-rules ()
                      ((_ expr ...)
                       (let ((x x))
                         (set! x (+ x 1))
                         expr ...)))))
    (boo (display x) (newline))))

;; non hygiene
(let ((x 1))
  (define-macro (boo . args)
    `(let ((x x))
       (set! x (+ x 1))
       ,@args))
  (boo (display x) (newline)))

;; expanded
(let ((x 1))   ;; frame 1
  (let ((x x)) ;; frame 2
    (set! x (+ x 1))
    (display x) (newline)))

;; frame 1
'(((x . 1)))

;; frame 2
'(((x . x))  ;; *1
  ((x . 1)))

話を簡単にするために、環境フレームは変数と値のペアをつないだもの(alist)とする。まぁ、多くの処理系がこの形式を使ってると思うけど。健全なマクロと非健全なマクロそれぞれの展開形はどちらも同じに(というと嘘が入るが)なる。コメントのframe 1及び2はその下にあるコンパイル時の環境フレームのイメージを示している。

ここで問題にするのは*1がそれぞれの場合で何になるかということ。

健全なマクロではマクロ内で定義された変数をマクロ外から参照することはできない。なので展開後の式とframe 2の環境イメージは実際には以下のようになる。

(let ((x 1))
  (let ((~x x))
    (set! ~x (+ ~x 1))
    (display x) (newline)))
;; frame
(((~x . x))
 ((x . 1)))

実際にどうなるかは処理系によって違うので、上記はあくまでイメージ。ここで問題になるのはletで束縛される変数のみがリネームされるということ。値の方は一つ上の環境フレームから参照されなくてはならない。(正直、これが実装者泣かせな部分の一つだと思っている。)
これの解決方法は僕が知っているだけで2つあって、1つは多くのR6RS処理系が取っている(Sagittarius以外はそうじゃないかな？)マクロ展開フェーズを持たせること。もう一つはSagittariusが取っているマクロ展開器が実行時環境とマクロ捕捉時環境の両方を参照する方法(正直お勧めではない)。

最初の方法だと、マクロ展開器は何が変数を束縛するかということを知っていなければいけない。 そうしないと上記の例のように変更してはいけないシンボルまでリネームしてしまうことになるからだ。値側のシンボルも実はリネームされるんだけど、マクロ束縛時の環境フレーム(frame 1)を参照して外側のletで束縛されたシンボルを見つけて同じ名前にするということが行われる。

2番の方法だと、マクロ展開器は両方の環境を適切に参照しつつ、コンパイラも変数の参照時に多少トリックが必要になる。正直書いててバグの温床にしかならないなぁと思ったのでお勧めではないが、この方法ならマクロ展開器は何が変数を束縛するかということを知らなくてもいいので、重複コードが多少減る。

ただ、どちらの場合もsyntax-rulesを実装するだけならたぶん必要なくて、Chibi Schemeのようにsyntactic closureを使ってer-macro-transformerを実現するとかでなんとかなる。(syntactic closure自体の実装で環境の束縛とか参照が必要にはなるけど、上記ほど複雑にはならない・・・はず。)

非健全なマクロではシンボルはリネームされないので、例で上げた展開後フォームそのままとなる。CLだと上記のようなマクロをSchemeのように動かしたいなら(gensym)とかwith-unique-namesとかを多用する必要がある。Lisp-2だったらたぶんそれでもいいだろうけど、Lisp-1だと泣けるだろうなぁと思う。

思ったとおり普通のマクロ解説記事の劣化版になってしまった。

OCI binding

If you are a professional programmer, then you can't avoid Oracle (or you need to be really lucky). I'm also one of them.

I was using either GUI (mostly Quantam DB) or Sagittarius ODBC binding. Both have some problems but by now it worked pretty fine for me. The reason I've decided to write it was it's getting annoying to use some thing not supporting to dump BLOB data thoroughly or requiring to configure connection setting somewhere difficult to find.

As you already knew, there is the API to use Oracle directly called OCI (Oracle Calling Interface). Well, since I have FFI then why not write a binding for it? It would make my life much easier than now. I was really hoping like that. If everything would have gone well, I wouldn't have written this article. Yes, I've met THE problem.

If you have an experience using ODBC, then you might have thought like this: 'this API requires cast no matter what'. OCI also has this and I call it problem. When this become a problem is actually certain situations such as binding parameters. Sagittarius converts input Scheme object to relevant C object. However it doesn't support casting. So at this point, my motivation had disappeared.

Then it revived like phoenix. My FFI doesn't support cast however most of the values can be converted to bytevector (it can be done by R6RS). Now I have got some lights to go through this crappy API jungle (it's well designed actually).

脱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で同じものが共有されてるから、クロージャ側だけ更新してやればいいはずなんだけどなぁ、何を見落としてるんだろう・・・

詳解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-setupはsrc/compiler/generic/parms.lispに定義がある。第一引数はスモールスペースのアドレス(どこで使われてるかは確認してない)、第二引数が動的領域の開始アドレスである。これはX86の固有設定だが、他のアーキテキチャにも同様の定義があり、固定値を使っている。

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

詳解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.cのgc_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;
}

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

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

ここまで読んでいれば勘のいい人は既に分かっているだろうが、scavengeである。実際にscavengeは以下の3つの段階で呼ばれる。

1. 割り込みハンドラ、バインディングスタック及びSBCLの静的領域の回収
2. GC対象外の世代の回収
3. 新しい世代の回収

の3つである。ものすごく簡単に言えば、GC対象のヒープ領域以外のヒープをすべて回収し、GC対象の領域でピン止めされたページ以外はごみとするという感じである。

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

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

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を参照)

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

詳解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.cのgc_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_ENDとDYNAMIC_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_baseはDYNAMIC_SPACE_STARTと同値である(gc_initで設定されている)。1つのページはGENCGC_CARD_BYTESで区切られるのでこのように計算できる。

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

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

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

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

脱BoehmGCへの道 実装編(2)

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

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

とりあえず現状での違いを列挙
【SBCL】

• 保存するポインタは、スタック及びレジスタのみ
• 静的領域は持ってない
• 動的にコードを生成するのだからある意味当たり前ではある
• 全てのポインタは中身にアクセスすることなくおよそLispオブジェクトかの判別が可能
• これによって実際にscavenge及びtransportを行う手続きをテーブルで持つことが可能
• 全てのポインタからおよその割付サイズを割り出すことが可能

【Sagittarius】

• 保存するポインタは、スタック、レジスタ及び静的領域
• 結構な勢いでstaticなオブジェクトを持っているので変更したくない
• Schemeオブジェクトかどうかの判別にはポインタの中身を見る必要がある
• 単なるコンテナのpairはどうしても一般的なメモリとしてしか判別できない
•  動的領域から割り付けられたものならばメモリヘッダからサイズの割り出しが可能
• あいまいなポインタがきた場合に多少困る
• 一応チェックが走るけど、不安

 今更ながらにオブジェクトをタグにしておけばよかったと多少後悔しているが、まぁ泣くまい。

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

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

脱BoehmGCへの道 準備編(4)

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

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

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)に証明書をバイトベクタに変換する手続きが追加されました

脱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