SBCLの実装を追う ~car, cdr, cons~

なんとなく興味があったのでdisassembleを使ってSBCLのcar、cdr、consの中を追ってみました。 CPUのアーキテクチャはx64です。

carとcdrをdisassembleしてみます。

CL-USER> (disassemble #'car)
; disassembly for CAR
; Size: 12 bytes. Origin: #x52A3B48B                          ; CAR
; 8B:       488B56F9         MOV RDX, [RSI-7]
; 8F:       488BE5           MOV RSP, RBP
; 92:       F8               CLC
; 93:       5D               POP RBP
; 94:       C3               RET
; 95:       CC10             INT3 16                          ; Invalid argument count trap
NIL
CL-USER> (disassemble #'cdr)
; disassembly for CDR
; Size: 12 bytes. Origin: #x52A6E77B                          ; CDR
; 7B:       488B5601         MOV RDX, [RSI+1]
; 7F:       488BE5           MOV RSP, RBP
; 82:       F8               CLC
; 83:       5D               POP RBP
; 84:       C3               RET
; 85:       CC10             INT3 16                          ; Invalid argument count trap
NIL

C言語によるcarやcdrの実装を呼び出しているのかと思ったのですが、そういうわけではなさそうです。 もしそうならCALLやJMPがdisassembleの結果に現れるはずです。

まだ分からないのでcadrもdisassembleしてみます。 cadrはcdrを取った後でcarを取る関数で上で見た関数の組み合わせです。何か分かるかもしれません。

CL-USER> (disassemble #'cadr)
; disassembly for CADR
; Size: 26 bytes. Origin: #x52D0F4AB                          ; CADR
; AB:       488B7701         MOV RSI, [RDI+1]
; AF:       8D46F9           LEA EAX, [RSI-7]
; B2:       A80F             TEST AL, 15
; B4:       750A             JNE L0
; B6:       488B56F9         MOV RDX, [RSI-7]
; BA:       488BE5           MOV RSP, RBP
; BD:       F8               CLC
; BE:       5D               POP RBP
; BF:       C3               RET
; C0: L0:   CC4C             INT3 76                          ; OBJECT-NOT-LIST-ERROR
; C2:       18               BYTE #X18                        ; RSI(d)
; C3:       CC10             INT3 16                          ; Invalid argument count trap
NIL

3つの結果を眺めると、RSI-7, RSI+1, RDI+1, RSI-7など似たようなパーツが浮かび上がってきます。 これで何か分かるかもしれないので、cadrの結果を、car、cdrの結果を見ながら追っていきます。

cadrでは最初にcdrを実行します。 cadrをcdrを比べると、cadrではMOV RSI, [RDI+1]を実行しており、 cdrではMOV RDX, [RSI+1]を実行しています。 双方とも、レジスタの値に1足した先にあるメモリの値を取得しています。これがcdrなのでしょうか。

cadrはcdrの結果からさらにcarを取ります。 disassembleの結果によると、次はLEATESTを実行しています。 しかし、これはJNEのためのものという感じがして、carを実行しているとは思えません。

その後のMOV RDX, [RSI-7]がcarでしょうか。 carのdisassemble結果にあるMOV RDX, [RSI-7]と同じです。 cadrのRSIには[RDI+1]が入っていて、これはcdrと思われる前段処理の結果です。 これらでcarとcdrを実行していると考えるとつじつまが合いそうです。

まとめると、以下のような仮設を立てられます。

  • carではRSIにコンスセルのアドレスが入っている
  • cdrではRSIにコンスセルのアドレスが入っている
  • cadrではRDIにコンスセルへのアドレスが入っている
  • コンスセルのアドレス+1から8バイトがcar部分のアドレス
  • コンスセルのアドレス-7から8バイトがcdr部分のアドレス

この仮説をもとに、以下のような設定でcadrの動きを追ってみます。

メモリ:

  200   207  208      215
   |      |  |         |
   |      |  |         |
   v      v  v         v

   +---------+---------+
   |   xxx   |   407   |
   +---------+---------+


  400   407  408      415
   |      |  |         |
   |      |  |         |
   v      v  v         v
   
   +---------+---------+
   |   yyy   |   zzz   |
   +---------+---------+

レジスタ: RDI = 207
  • RDIにcadrの引数のアドレス(= 207)が入っている
  • MOV RSI, [RDI+1]が実行される
    • 207 + 1 = 208から8バイトの値は407
    • 407がRSIに読み込まれる
  • MOV RDX, [RSI-7]が実行される
    • 407 - 7 = 400から8バイトの値はyyy
    • yyyがRDXに読み込まれる

と、このような動きになるようです。

読み飛ばしていたLEATESTを見てみます。 上気の例だとRSI-7 = 400がEAXに読み込まれ、15 = 0x0Fと論理積が取られます。 結果は0なので無事car部分が実行されます。

論理積がもし非ゼロならJNE LOが実行され、LOラベル部分の命令が実行されます。 ここにはOBJECT-NOT-LIST-ERRORというコメントがあるので、引数がリストでなかったときのエラー処理ということでしょうか。

アドレスは通常8の倍数になるようにアライメントされていると思われます。 8の倍数はアドレス、8の倍数でない値は数値を意味し、下位4ビットはタグになっているとかでしょうか。

とりあえず、cadrを通して、car、cdrの動きを分かったように思います。 +1と-7でちょうど64ビット違うのもつじつまがあいそうですし。

consもdisassembleしてみます。

CL-USER> (disassemble #'cons)
; disassembly for CONS
; Size: 58 bytes. Origin: #x52BF09AF                          ; CONS
; AF:       4D896D28         MOV [R13+40], R13                ; thread.pseudo-atomic-bits
; B3:       498B5558         MOV RDX, [R13+88]                ; thread.cons-tlab
; B7:       488D4210         LEA RAX, [RDX+16]
; BB:       493B4560         CMP RAX, [R13+96]
; BF:       771E             JNBE L2
; C1:       49894558         MOV [R13+88], RAX                ; thread.cons-tlab
; C5: L0:   488932           MOV [RDX], RSI
; C8:       48897A08         MOV [RDX+8], RDI
; CC:       80CA07           OR DL, 7
; CF:       4D316D28         XOR [R13+40], R13                ; thread.pseudo-atomic-bits
; D3:       7402             JEQ L1
; D5:       CC09             INT3 9                           ; pending interrupt trap
; D7: L1:   488BE5           MOV RSP, RBP
; DA:       F8               CLC
; DB:       5D               POP RBP
; DC:       C3               RET
; DD:       CC10             INT3 16                          ; Invalid argument count trap
; DF: L2:   6A10             PUSH 16
; E1:       E86AFAE0FF       CALL #x52A00450                  ; SB-VM::LIST-ALLOC-TRAMP
; E6:       5A               POP RDX
; E7:       EBDC             JMP L0
NIL

L2ラベル部分にCALLがあり、SB-VM::LIST-ALLOC-TRAMPとコメントされています。 つまりこれがconsにおけるメモリ確保の部分だと思われます。 CALLの後はPOP RDXで、確保した領域のアドレスをRDXに納めていそうです。 最後にJMP LOLOに飛びます。

LOではMOV [RDX], RSIMOV [RDX+8], RDIを実行しています。 確保した領域の0~7バイト目にRSIを、8~15バイト目にRDIを入れています。 OR DL, 7RDXの下位3ビットに1を立ててます。つまり200は207になります。 このような割り当ての仕方は、cadrで見たcar、cdrのアクセスと整合しています。 おそらくRSIがcarでRDIがcdrなのでしょう。

というわけで、SBCLのcar、cdr、consを中を追ってみた、でした。 処理系の中を覗いてみるのは楽しいですね。