SSHクライアントを実装したった

そろそろ(自分のために)要るなぁと思っていたので「えいや！」と作った。と書くとちょっと自分がすごいことしてる感じが出るが、要するにRFCに書かれていることを地道に実装しただけである。ちなみに全ての要求はまだ満たしていない。

以下のように使える。

(import (rfc ssh))

(define transport (make-client-ssh-transport "localhost" "22"))
(define user "guest1")
(define pass "pass1")

(ssh-authenticate transport +ssh-auth-method-password+ user pass)
(let-values (((status response) (ssh-execute-command transport "ls -l")))
  (print (utf8->string response)))

ssh-execute-commandはコマンドの戻り値と出力を受け取る。出力はバイナリなので適当に変換する必要がある。他にもShellを起動したりチャンネルを自前で開いたりするAPIがある。

まだまだおもちゃ程度の処理しかできない(ので、しばらくはドキュメントに載らないｗ)。そして、本当にほしいのはSFTPだったりするので次はsubsystemセッションの確立とSFTPの実装かね。

以下は適当な情報
ソースはsitelib/rfc/sshディレクトリ以下。あまりの汚さに精神汚染を起こしても当方は責任を取らない(多分未来の自分に対する警告・・・)。これを実装するために以下の機能及びライブラリが追加された。

• (binary data)ライブラリ(自分で言うのもなんだけど、すごく便利ｗ)
• DSA鍵署名及び検証

Binary data structure read/write library

Currently I'm implementing SSH (for now client only) on Sagittarius and have noticed it would be convenient to have a library which handles binary data structure read/write. So I've written (binary data) library. (not sure if the name should be '(binary structure)' or '(binary io)', or something else).

Here is the simple example;

;; The definition is from RFC 4250-4254
;; atom datum
(define-simple-datum-define define-ssh-type read-message write-message)
(define-ssh-type <name-list> (<ssh-type>)
  names '()
  (lambda (in)
    (let* ((len (get-unpack in "!L"))
           (names (get-bytevector-n in len)))
      (string-split (utf8->string names) #/,/)))
  (lambda (out names)
    (let ((names (string->utf8 (string-join names ","))))
      (put-bytevector out (pack "!L" (bytevector-length names)))
      (put-bytevector out names)))
  :parent-metaclass <ssh-type-meta>)

;; composite data
(define-composite-data-define define-ssh-message read-message write-message)
(define-ssh-message <ssh-msg-keyinit> (<ssh-message>)
  ((type   :byte +ssh-msg-kexinit+)
   (cookie (:byte 16)) ;; array of byte
   (kex-algorithms <name-list>)
   (server-host-key-algorithms <name-list>)
   (encryption-algorithms-client-to-server <name-list>)
   (encryption-algorithms-server-to-client <name-list>)
   (mac-algorithms-client-to-server <name-list>)
   (mac-algorithms-server-to-client <name-list>)
   (compression-algorithms-client-to-server <name-list> (name-list "none"))
   (compression-algorithms-server-to-client <name-list> (name-list "none"))
   (language-client-to-server <name-list> (name-list))
   (language-server-to-client <name-list> (name-list))
   (first-kex-packat-follows :boolean #f)
   (reserved :uint32 0)))

So the idea of the library is that structured data are either simple datum or composite of simple datum. Thus if we define how to read/write the simple datum, then composite data's read/write are already decided. This might not be always true but as far as I know most of the case.

BTW, I think the naming of the macro is ugly so if you have a better suggestion it's very welcome :)

マクロバグリターンズ

えらく久しぶりに発見した気分ではある。二つあって、一つは(とりあえずやっつけで)片付けたのだが、もう一つに苦戦している。

問題となるのは以下のようなコード。

(import (rnrs))
(define-syntax renaming-test
  (syntax-rules ()
    ((_ var val)
     (begin
       (define dummy val)
       (define (var) dummy)))))
(define dummy #f)
(renaming-test a 'a)
(print (a))
(print dummy)

まぁ、見れば分かるとおり、最後のdummyは#fを返してほしいのだがaを返してくるというバグである。要するにリネームが上手いこといっていないのである。

現状ではリネームは展開時にのみ行われているのだが、パターンのコンパイル時にどこにも束縛されていない識別子はリネームしてしまっていいのではないか？という気がしている。上記の例なら、パターン変数であるvarとval、束縛されている_、begin及びdefineはリネームするとまずいのだが、残り(dummy)はリネームしてもマクロ外にもれることはないわけなのだから(むしろ漏れるとまずい)。ちょっとそんな感じでやってみるかね。 あぁ、だめだ。それだと以下のようなパターンで困る。

(let ((dummy #f)
      (hoge #t))
  (define (print . args) (for-each display args) (newline))
  (let-syntax
      ((renaming-test (lambda (x)
                        (syntax-case x ()
                          ((_ var val)
                           #'(begin
                               (define dummy val)
                               (define (var) dummy)
                               (display hoge) (newline)))))))
    (renaming-test a 'a))
  (print (a))
  (print dummy))

これだと、dummyはリネームされてほしいけど、hogeは変更されたくない。ただ、このパターンってマクロが構文を知ってないとどうしようもないような。違うかな？dummyとhogeが意味的に違うってのを構文の情報なしにどう知ればいいんだ？

セルフホスティング

現状でもSagittariusはほぼセルフホスティングしているのだが、もう少し発展させたものにしたいなぁと思ってきたのと、微妙な問題点に気づいたのでメモ。

0.4.11までは(実は0.4.11は試験的に違うが)Schemeで書かれたVM上でコンパイラをコンパイルしてCのコードを生成していたのだが、これだとVMのコードを変更するたびにC側とScheme側の両方を変更しなければならなくて正直面倒だった。そこで、とりあえずの下地として、コンパイルされたコードをCに変換するライブラリを0.4.11では導入した。

とまぁ、Sagittariusが変なことをしていない処理系だったらこれで話は終わるんだけど、実は変なことをしている処理系なのでここで話が終わらないことに気づいたのだ。SagittariusのコンパイラはVMが使用するフレームのワード数を知っていて(VMから取るんだけど)、コンパイル時に余計な環境の束縛を行わないようにしている(多分以前そうしたっていう記事書いた)。これが問題になる。ちょっといい例が思いつかなかったので微妙な例だが、こんなの。

(disasm (lambda (x)
          (let ((y (get x z))) 
            (print (let ((w (get y z)))
                     (get w (let ((e (get x)))
                              (get e x))))))))
;; size: 40
;;    0: FRAME 6
;;    2: LREF_PUSH(0)
;;    3: GREF_PUSH #<identifier z#user (0x80501990)>; z
;;    5: GREF_CALL(2) #<identifier get#user (x805019d8)>; (get x z)
;;    7: PUSH
;;    8: FRAME 6
;;   10: LREF_PUSH(1)
;;   11: GREF_PUSH #<identifier z#user (0x805018b8)>; z
;;   13: GREF_CALL(2) #<identifier get#user (0x80501900)>; (get y z)
;;   15: PUSH
;;   16: FRAME 18
;;   18: LREF_PUSH(2)
;;   19: FRAME 4
;;   21: LREF_PUSH(0)
;;   22: GREF_CALL(1) #<identifier get#user (0x80501810)>; (get x)
;;   24: PUSH
;;   25: FRAME 5
;;   27: LREF_PUSH(10) <-- !!! this !!!
;;   28: LREF_PUSH(0)
;;   29: GREF_CALL(2) #<identifier get#user (0x805017b0)>; (get e x)
;;   31: LEAVE(1)
;;   32: PUSH
;;   33: GREF_CALL(2) #<identifier get#user (0x80501870)>; (get w (let ((e (get x))) (get ...
;;   35: LEAVE(1)
;;   36: PUSH
;;   37: GREF_TAIL_CALL(1) #<identifier print#user (0x80501948)>; (print (let ((w (get y z))) (g ...
;;   39: RET

普通ならLREF_PUSH(10)というのはスタックに詰まれた変数の10番目をスタックに積むという意味なのだが、この場合は途中にあるフレームを考慮したら10番目になった変数の参照を意味している。なんでこんな風になっているかと言えば、まぁ歴史的理由が大きいのだが、Sagittariusには一つ外側の環境という概念が存在しないからである(その方がパフォーマンス的に有利だったから)。VMのスタックはプッシュとポップ以外では基本変更されないので、そこを(個人的には)上手く使った(と思っている)トリックである。

では、普通のセルフホスティングでは何が嬉しくないかといえば、コンパイラやビルトインライブラリにこういったケースが無いとは言い切れないため、先に計算されたオフセットがずれる可能性があるからである。となれば、解決策は一つで、ホストはまずターゲットコンパイラAをコンパイルしてそのコンパイラでもう一回コンパイルするというものだろう。Aは一つ前のVMインストラクションで構成されるが、吐き出すインストラクションはターゲットが必要とするものになるといった寸法である。多少回りくどいなぁとは思うが、仕組み上回避不可っぽいので諦めるしかないだろう。

とりあえず、メモとして記録。

コンパイラマクロ

実は材料は最初からあったんだけど、気が向かなかったのと必要に迫られるほどタイトな性能を要求してなかったので放置してたものの一つ。っが、気が向いたのでえいや！っと作ることにした。まぁ、気が向いた理由は2chでRacketとChickenはあるという話を見たからなのだが・・・

とりあえず、以下の様に使える。

(import (rnrs) (core inline))
;; map is defined in (core base)
(define-inliner map (core base)
  ((_ p arg)
   (let ((proc p))
     (let loop ((l arg) (r '()))
       (if (null? l)
           (reverse! r)
           (loop (cdr l) (cons (proc (car l)) r)))))))

手続き名とそれが定義されているライブラリを指定し、実際の展開部分はsyntax-rulesのようなパターンマッチで記述する。っで、比較のためにある版とない版のコンパイル結果がこれ。

;; あり
(disasm (lambda (x) (map values '(1 2 3 4 5))))
;; size: 26
;;    0: GREF_PUSH #<identifier user#values x80414678>; values
;;    2: CONST_PUSH (1 2 3 4 5)
;;    4: CONST_PUSH ()
;;    6: LREF(2)
;;    7: BNNULL 5                  ; (if (null? l) (reverse! r) (lo ...
;;    9: LREF_PUSH(3)
;;   10: GREF_TAIL_CALL(1) #<identifier reverse!#user x804146d8>; (reverse! r)
;;   12: RET
;;   13: LREF_CDR_PUSH(2)
;;   14: FRAME 4
;;   16: LREF_CAR_PUSH(2)
;;   17: LREF(1)
;;   18: CALL(1)
;;   19: PUSH
;;   20: LREF(3)
;;   21: CONS_PUSH
;;   22: SHIFTJ(2 2)
;;   23: JUMP -18
;;   25: RET

;; なし
;; size: 7
;;    0: GREF_PUSH #<identifier values#user x802ba300>; values
;;    2: CONST_PUSH (1 2 3 4 5)
;;    4: GREF_TAIL_CALL(2) #<identifier map#user x802ba330>; (map values '(1 2 3 4 5))
;;    6: RET

インライン展開されていることが分かる。実際に効果があるか、といわれるとなくは無いがベンチマークレベルで多用しないと目に見えないレベル、の効果だったりする。

これだと高階関数を使用する手続きのインライン展開にしか使えず、定数畳込みはできない。実はもう一段低レベルのマクロがあってdefine-inlinerはそれのラッパーなのだけど、外に見えるようにはしていない。理由は今一APIが気に入らないからだったりする。低レベルのAPIの方が設計が難しい気がしないでもない・・・