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の結果によると、次はLEA
、TEST
を実行しています。
しかし、これは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に読み込まれる
と、このような動きになるようです。
読み飛ばしていたLEA
、TEST
を見てみます。
上気の例だと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 LO
でLO
に飛びます。
LO
ではMOV [RDX], RSI
とMOV [RDX+8], RDI
を実行しています。
確保した領域の0~7バイト目にRSIを、8~15バイト目にRDIを入れています。
OR DL, 7
でRDXの下位3ビットに1を立ててます。つまり200は207になります。
このような割り当ての仕方は、cadrで見たcar、cdrのアクセスと整合しています。
おそらくRSIがcarでRDIがcdrなのでしょう。
というわけで、SBCLのcar、cdr、consを中を追ってみた、でした。 処理系の中を覗いてみるのは楽しいですね。