Zenn
🧩

『リンカー moldをいろんなターゲットに移植した話』を視聴してCPUやpsABIの世界を覗き見してみた #kernelvm

2023/01/24に公開
コンパイラ
CPU
kernelvm
リンカ
tech

Kernel/VM探検隊online part6 で Rui Ueyama 氏による『リンカー moldをいろんなターゲットに移植した話』のセッションを視聴し、普段は接点のないCPUやpsABIといった低レイヤーの世界を覗き見したので、メモを残しておきます。

https://twitter.com/rui314/status/1614588389038370822

Ruiさんは、LLVMのリンカlldの作者でもあり、過去には同勉強会のPart 2でもリンカについて発表されています。

今回も、前日に発表が決まったとはとても思えない、非常に濃い発表でした。

https://twitter.com/rui314/status/1614173210807013377

本テーマは筆者の普段の業務と大きく異なります。間違いなどがあればコメントで指摘していただけると助かります。

以下の様なキーワードが頻出します。

  • リンカ
  • psABI
  • ELF
  • QEMU
  • ISA
  • RISC/CISC
  • エンディアン
  • アラインメント
  • PC相対
  • PLT
  • GOT
  • 位置依存/独立コード

これらトピックに疎い人は、前提知識として第2回のリンカの発表や『リンカのお仕事』by kaityo256や『ふつうのコンパイラをつくろう』青木峰郎 さんの「第4部 リンクとロード」を一読するのがおすすめです。

発表概要

moldというリンカを作成している。

いろいろなターゲットをサポートすることにしており、現在13種類の異なるターゲットをサポートしている。

移植作業を行うことで、いろいろなCPUの違いやCPUだけによらない思想的なというか、ABIのインターフェースの違いがいろいろ浮き彫りになって面白いので、リンカの移植性という観点から、CPUやpsABI(ABIのCPU依存部)について説明してみたいと思います。

サポート済みターゲット一覧

ターゲット 製造元 難易度 デザイン ビット 命令 pc相対 エンディアン
x86-64 AMD 低 CISC 64 可変長 あり リトルエンディアン
i386 Intel 中 CISC 32 可変長 なし リトルエンディアン
Motorola 68000 Motorola 低 CISC 32 可変長 あり ビッグエンディアン
s390x IBM 低 CISC 64 可変長 あり ビッグエンディアン
ARM64 ARM 中 RISC 64 4バイト固定長 あり リトルエンディアン
ARM32 ARM 中 RISC 32 2/4バイト可変長 なし リトルエンディアン(厳密にはバイエンディアン)
SPARC64 Sun 中 RISC 64 4バイト固定長 なし ビッグエンディアン
RISC V RISC-V 高 RISC 32/64 2/4バイト可変長 あり リトルエンディアン
32-bit PowerPC IBM(AIM) 中 RISC 32 4バイト固定長 なし ビッグエンディアン
64-bit PowerPC ELFv1 IBM(AIM) 高 RISC 64 4バイト固定長命令 なし ビッグエンディアン
64-bit PowerPC ELFv2 IBM(AIM) 中 RISC 64 4バイト固定長命令 なし リトルエンディアン
SH-4 日立製作所/ルネサスエレクトロニクス 中 RISC 32 2バイト固定長 あり リトルエンディアン
Alpha DEC 高 RISC 64 4バイト固定長 なし リトルエンディアン

リンカとは?

前提知識を駆け足で紹介。

プログラムをビルドすると、たくさん .o というファイル(オブジェクトファイル)が作成される。
.o ファイルは基本的にソースファイル1個ごとに作られ、ソースファイル1個ごとにコンパイラが起動して、.cc みたいなファイルが .o になる。

このオブジェクトファイルはコンパイルされたプログラムの断片が入っているだけなので、誰かが1個にがっちゃんこして、実行ファイルとかにまとめないといけない。

1個のファイルにガッチャンコしてまとめるプログラムがリンカと呼ばれるプログラム。

出力は実行ファイルや共有ライブラリ。

オブジェクトファイルの中身

オブジェクトファイルには、コンパイルしたプログラムの断片が入っている。具体的には、マシンコードとデータが入っている。さらに、リンカが必要とする付随的な情報も入っている。

オブジェクトファイルの中身を覗くには、readelf と objdump という2つのコマンドがよく使われる。

$ readelf -a foo.o
$ objdump -dr foo.o （逆アセンブル）

逆アセンブルしてみる

次のfoo.cを試しにディスアセンブルします。

#include <stdio.h>

void hello() {
  printf("Hello world\n");
}

オブジェクトファイルを作成

$ gcc -c foo.c
$ file foo.o
foo.o: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

逆アセンブル

$ objdump -dr foo.o

foo.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <hello>:
   0:	f3 0f 1e fa          	endbr64
   4:	55                   	push   %rbp
   5:	48 89 e5             	mov    %rsp,%rbp
   8:	48 8d 05 00 00 00 00 	lea    0x0(%rip),%rax        # f <hello+0xf>
			b: R_X86_64_PC32	.rodata-0x4
   f:	48 89 c7             	mov    %rax,%rdi
  12:	e8 00 00 00 00       	call   17 <hello+0x17>
			13: R_X86_64_PLT32	puts-0x4
  17:	90                   	nop
  18:	5d                   	pop    %rbp
  19:	c3                   	ret

オブジェクトファイルをディスアセンブルすると、マシンコード(例はx86-64)を確認できる。

ただしこのファイルは不完全。

例えば printf を呼び出しているけど、printf のアドレスは埋まっていない。

というのも、printf はこのオブジェクトファイルそのものには含まれていないから、どこのアドレスに飛べばよいのかはコンパイル時にはわからないので、コンパイラはアドレスを埋めようがない。

代わりに リロケーション という情報を出力し、puts のアドレスを書き換えてね、みたいな情報を入れている。

同様に、"Hello world\n" というリテラルの文字列をどかに置くかはメモリレイアウトを決定するまでは決まらないので、下線のように0で埋めておき、その代わりにこの .rodata(read only data) の4バイト目を指すようにしてね、みたいなリロケーション情報を入れている。

printfがputsに変わっているのは、コンパイラの最適化の結果。

リンカがこれらファイルを全部ガッチャンコすると、名前を突き合わせることができるので、未確定だったアドレスを修正すると、実行ファイルができあがる。

PLTとGOT

共有ライブラリに入っている関数のアドレスは、実際に実行が始まるまでは分からないので、実行時にローダーに修正してもらう必要がある。

リンカは PLT(Procedure Linkage Table) というテーブルを作る。
飛び先が確定しない関数に関しては、このPLTのエントリに一度飛ばし、ローダーはPLTのアドレスを書き換え、そこから本来飛びたかった関数に飛ばす。

このPLTを作ることが、リンカの仕事の一部。

同様に、共有ライブラリに含まれているかもしれない グローバル変数 などもアドレスはリンク時に解決されない。 GOT(Global Offset Table) というテーブルを作り、実行時にこのテーブルからアドレスを改めて読み直すと、グローバル変数の値が読めるようになる。

位置独立・依存コード

重要な区別の一つとして位置依存コードと位置独立コードという概念があり、リンカを作る上で把握しておく必要がある。

  • 位置独立コード(Position Independent Code;PIC) : どのアドレスに配置しても破綻しないように作られているコード
  • 位置依存コード : 特定のアドレスにロードしないと動かないコード

実行ファイルは位置独立コードでも位置依存コードでもよい。

実行ファイルはフレッシュなメモリ空間にロードされるので、実行ファイルは位置依存でリンクしてもいい。関数やグローバル変数は、同じファイル内にある限りにおいては、アドレスはリンク時に確定することになる。

一方で、共有ライブラリはどのアドレスにロードされるかわからない。
どこかのアドレスに対してリンクしても、同じアドレスに対してリンクされている別の共有ライブラリがあるとかち合うので、ずらさないといけない。

そのため、共有ライブラリは位置独立コードとしてコンパイルしてリンクする。

位置独立にするために、絶対アドレスをファイルに含めない。

位置独立なコードといっても、メモリ上ではひとかたまりとしてシフトされるだけであり、自分自身の中でのオフセットは変わらない。このオフセットでメモリにアクセスする限りに置いては、位置独立コードになる。

このように、絶対アドレスの代わりに相対アドレスを使ってアクセスすると、位置独立コードになる。

最近は、セキュリティを強化するために、実行ファイル自身も位置独立コードとしてコンパイルし、ランダムなアドレスにロードすること(position-independent executable(PIE))が一般的になっている(アドレス・ランダマイゼーション)。

移植方法

今までが前提で、ここからが本題の移植方法。

いろいろなアーキテクチャに移植するにしても、実機を用意できないし、実機を用意しても不便なだけなので、基本的にQEMU(CPUや各種ハードウェアをエミュレート)で開発している。

クロスコンパイラはapt-getでインストールできる。

gcc-aarch64-linux-gnu みたいなパッケージをインストールすると、そのターゲットのGCCがAvailableになり、aarch64-linux-gnu-gcc を起動すると、Arm64向けのバイナリを吐く。

出力されたファイルはネイティブじゃないけど、QEMUを使うと、実行できる。

QEMUはgdbのサポートもあるので、ポート番号などを渡してリモートのホストであるかのようにgdbから接続すると、リンクしたバイナリのデバッグもできる。

アーキテクチャによってはリーバス実行みたいなことができるアーキテクチャもあって、ステップ iみたいに、1命令進むだけじゃなくて、1命令戻るみたいなこともできて、デバッグが容易にできたりする。

移植に必要なコード量(行数)

GNU gold はターゲット依存コードが1万行を超えることもあるけれど、mold は数百行。ものによっては、300行とか400行で移植が完成してしまう。moldでは移植が非常に容易になっている。


※発表スライドから

x86-64

ここからが移植の具体的な話。

※発表スライドから

x86-64は64ビットの普通のPCで使われているプロセッサで、1バイトから15バイトまで命令がある。

PC相対load/store命令があり、ロード命令の位置から何バイト先のデータを読むみたいなことができる。

ドキュメントも充実していて実装も充実していて、移植の難易度は非常に低い。

一番最初に実装したのもx86-64。

一般論として、下のレイヤーの機能がしっかりしていれば、上のレイヤーは手抜きできるので、CPUが高機能なほうがリンカは簡単に実装できる。
逆に下のレイヤーが低機能だと、上のレイヤーで頑張らないといけない。

そのため、CISC("C"はComplexの略)のほうがRISC("R"はReducedの略)よりもリンカを作るのは簡単な傾向がある。

特記することはない。

Motorola 68000(m68k)

※発表スライドから

Motorola 68000シリーズは大昔のオリジナルのMacにも使われていたレトロなCPUでビッグエンディアンが特徴。

参考:MacのCPUの変遷

  1. m68k
  2. PPC
  3. Intel
  4. ARM

なんでこれに移植することになったかと言うと、レトロPC愛好家からサポートの依頼メールをもらい、お金くれたらやってもいいよ、みたいな話をした。

m68kには活発なホビーストコミュニティがあり、LLVMバックエンドも$3,000のクラウドファンディングして対応した。

金額の桁が1つ、2つ違うと思ったけど、最低300万円からとはとても言えなくて、最終的に$800もらって移植した。1日で移植できたから、この金額でもまぁいいかなという感じ。非常に素直に移植できた。

依頼メールをもらったときに、ググっても資料が見つからないといったら、紙をスキャンしたPDFが送られてきてくれて、これがスペックだと言われた。

※発表スライドから

謝罪文が検索避けに画像になっているのと同じで、画像のPDFなので、ぐぐっても見つからない。

この資料があれば、めちゃ古いですけど、一応書ける。

s390x

※発表スライドから

s390xはIBMのメインフレーム向けISA。
サイズが冷蔵庫くらい有って、3重化された電源、CPU/メモリがホットスワップできて、メモリが48TB積める「ビッグ・アイアン」マシン。

このCPUはPowerPCとかですらなくて、s390xというIBM Zという謎のアーキテクチャ。
64bitのCISCで2000年位に開発された。

何かおかしいところがあるかというと、あんまりない。
命令は2/4/6バイトの可変長で、常に2バイトにアラインされ、ビッグエンディアン。

移植するのは、比較的簡単。

s390のクロスコンパイラも、apt-getで簡単にインストールできる。

ディスアセンブルすると、見たこともないニーモニックのアセンブリが出力され、どれが mov 命令で、どれが call 命令なのかもわからない。

$ sudo apt-get install gcc-11-s390x-linux-gnu
$ ls /usr/bin/ | grep s390
s390x-linux-gnu-addr2line
s390x-linux-gnu-ar
s390x-linux-gnu-as
s390x-linux-gnu-c++filt
s390x-linux-gnu-cpp-11
s390x-linux-gnu-dwp
s390x-linux-gnu-elfedit
s390x-linux-gnu-gcc-11
s390x-linux-gnu-gcc-ar-11
s390x-linux-gnu-gcc-nm-11
s390x-linux-gnu-gcc-ranlib-11
s390x-linux-gnu-gcov-11
s390x-linux-gnu-gcov-dump-11
s390x-linux-gnu-gcov-tool-11
s390x-linux-gnu-gprof
s390x-linux-gnu-ld
s390x-linux-gnu-ld.bfd
s390x-linux-gnu-ld.gold
s390x-linux-gnu-lto-dump-11
s390x-linux-gnu-nm
s390x-linux-gnu-objcopy
s390x-linux-gnu-objdump
s390x-linux-gnu-ranlib
s390x-linux-gnu-readelf
s390x-linux-gnu-size
s390x-linux-gnu-strings
s390x-linux-gnu-strip

オブジェクトファイルを作成

$ s390x-linux-gnu-gcc-11 -c foo.c
$ file foo.o
foo.o: ELF 64-bit MSB relocatable, IBM S/390, version 1 (SYSV), not stripped

ディスアセンブル

$ s390x-linux-gnu-objdump -dr foo.o

foo.o:     file format elf64-s390


Disassembly of section .text:

0000000000000000 <hello>:
   0:	eb bf f0 58 00 24 	stmg	%r11,%r15,88(%r15)
   6:	e3 f0 ff 60 ff 71 	lay	%r15,-160(%r15)
   c:	b9 04 00 bf       	lgr	%r11,%r15
  10:	c0 20 00 00 00 00 	larl	%r2,10 <hello+0x10>
			12: R_390_PC32DBL	.rodata+0x2
  16:	c0 e5 00 00 00 00 	brasl	%r14,16 <hello+0x16>
			18: R_390_PLT32DBL	puts+0x2
  1c:	07 00             	nopr
  1e:	eb bf b0 f8 00 04 	lmg	%r11,%r15,248(%r11)
  24:	07 fe             	br	%r14
  26:	07 07             	nopr	%r7

ナンジャコリャって思うけど、頑張ってマニュアルとかと突き合わせると、だんだん読めるようになってきて、普通にx86_64みたいなもんだなって言うことがわかってくる。
別の並行宇宙で進化したx86 みたいなもんだなっていう理解に達する事ができる。

ただ、あまりユーザーが存在しないと思うので、GCCとかが変なコーナーケースとかで微妙にバグっている。GCCのバグを発見してIBMに報告したりした。

https://sourceware.org/bugzilla/show_bug.cgi?id=29655

99.999%な稼働率を誇るコンピュータのコンパイラのバグが1日2日いじるだけで簡単にみつかるのはいかがなものかと思う。

ドキュメントもあまり読む人がいないので、間違いがある。
そういうのも報告して、IBMの人に直してもらったりした。

https://github.com/IBM/s390x-abi/issues/3

IBMのエコシステム全体にはからずも貢献する形になり、IBMのためにタダ働きしている感じ。

ARM64(AArch64)

※発表スライドから

このあたりから、だんだんトリッキーになってくる。

ARM64は

  • MacOS M1/2 チップ
  • iPhone
  • Android

など、広く使われている。

いままでに紹介したのはCISCなので可変長命令だけど、ARMはRISCなので、命令がすべて4バイト(固定長)。

微妙に難易度が高まっている。

RISC向けのCPUは一般にリロケーションのタイプが多くなることが多い。

変数一つを読み込むだけでも2つのリロケーションが必要。
なぜかというと、変数1個のオフセットを読むだけでも2命令必要なことがあるから。

例えば、32ビットのオフセットを利用して、どっかのアドレスからなにかを読むという時に、32ビットのオフセットというのを直接命令に埋め込めない。
なぜかというと、命令が4バイト(32ビット)なので、 命令と同じサイズの値を命令に埋め込むことはできないので、2命令に分けざるを得ない。

最初の命令(ADRP)で上位20ビットをレジスターにセットし、次の命令(LDR)で、下位12ビットを指定する。同じことをやるにも、リロケーションのタイプが2倍になる。

0:   90000000        adrp    x0, 0 <foo>
                     0: R_AARCH64_ADR_PREL_PG_HI21   bar
4:   b9400000        ldr     w0, [x0]
                     4: R_AARCH64_LDST32_ABS_LO12_NC bar

64ビットの値をロードするには、4命令とか使って4倍になったりし、一般にリロケーションはたくさんある。

ARM64は関数呼び出しにBL(Branch and Link)という命令を使う。
命令が32ビットなので、埋め込めるオフセットが大きくなく、BLの場合、PC(program counter)から±128MiBの位置しか飛べない。

Is the program label to be unconditionally branched to. It is an offset from the address of this instruction, in the range ±128MB.
https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/BL

実行ファイルが大きくなって、テキストセグメントが128MiB以上になってくると、直接飛べない領域が出てくる。直接飛べないものはリンカが検出し、そこに飛ぶための小さい命令列を、飛べない命令列の近くに配置し、そこを経由して遠くに飛ばす必要がある。

そういう命令片を

  • Range Extension Thunk
  • (単に)Thunk(サンク)
  • veneer(ベニヤ板の「ベニヤ」)

などという。

サンクをどう挿入するかは興味深い問題。

ちゃんと動く(correctness)だけのサンクを用意しないといけないけど、たくさんサンクを作りたいわけではない。なるべく少ない数を作って、なるべくスパースに散らしておいて、動いてほしい。

ナイーブなアルゴリズムを使いギリギリ届く範囲にサンクを作ると、サンクにコードを足していくと、届かなくなることが発生するので、洗練されたアルゴリズムが必要。

※発表スライドから

mold ではかなりいいアルゴリズムを使っていて、1GiBの実行ファイルでも、数十ミリ秒の実行時間でレイアウトが確定できるようなサンクを作成するアルゴリズムを使っている。

https://twitter.com/rui314/status/1497846501740998662

i386

※発表スライドから

i386はx86の32ビット版でx86-64と同じようなものだけど、PC相対load/store命令がない。
どういうことかと言うと、命令からのオフセットを使ってデータを読むことができない。

代わりに、命令に絶対アドレスそのものを埋め込むことはできて、そのアドレスからデータを読んだり、レジスタを指定して、そのレジスタからの相対位置で読むこともできる。

ただし、実行中の位置から何バイトといった指定はできないので、i386では位置独立コードをサポートするのが難しくなっている。

絶対アドレスから読むのは、位置独立コードではできないし、レジスタに入っている値をアドレスとみなして、そこから読むにしても、そのレジスタの値をどうやって組み立てるかという問題がある。

GOTのアドレス計算

リンカはそれぞれのELFファイルの中に変数のアドレスが入っているテーブル(GOTもその一つ)を作る。GOTのアドレスを関数の一番先頭で計算しておいて、あとはGOTからのオフセットで変数にアクセスすれば良い。

アドレスを計算するには、一旦ダミーの関数にジャンプする。
call 命令はコールの次の命令のアドレスをリターンアドレスとしてスタックにプッシュするので、
そのアドレスを読むと、そのcallの次の命令のアドレスを得られる。
そのコールの次の命令のアドレスと同じファイル内のGOTの位置はリンク時に決まるので、その差分を足すと、GOTのアドレスを得られることになり、あとはGOTを使ってアクセスすれば良い。

call __x86.get_pc_thunk.bx

__x86.get_pc_thunk.bx:
  mov (%esp), %ebx  # リターンアドレスを%ebxにコピー
  ret

このコードを実行するのは、それなりにコストがかかるので、この計算を毎回やりたいわけじゃない。位置依存なコードには不要なので、位置独立なコードに対してのみこの計算をする。

さらにi386はレジスタが8個しか無い。
GOTのアドレスを計算するには、%ebxに入れておくことになっており、このために%ebxを1個常に使うのはもったいない。

位置独立なコードにしか%ebxは使わないことになっていて、これにより、普通の関数からPLTにあるリンカが生成したコード列に飛んできた時に、%ebxに意味のある値が入っているかどうかは、位置独立か位置依存かによって変わってくるので、コード列を使い分けないといけない。

このために、リンカは若干めんどくさくなる。

それ以外は普通。

ARM32

※発表スライドから

ARM32は普通のARMプロセッサーで、組み込みで至るところで使われている。
Raspberry Piもその一つ。

32ビットのRISC CPU。とはいえ、変な機能が沢山ある。

プロセッサはビッグ・リトルの両方にサポートするバイエンディアンだけど、実質的に、リトルエンディアンしか使われていない。

ARM32に特徴的なのは

  • 4バイト命令モード(狭義の意味での"ARM命令")
  • 2バイト・4バイトの混在命令モード(Thumbモード) ※ メモリが勿体ないから

の2つのモードがあること。一般的にはThumbモードが使われている。

Thumbは後で追加され、命令のバイト列を見ただけではARMとThumbの区別がつかない。CPUはどっちのモードを実行中か知っていて、ARMとThumbの切り替えは、明示的にプログラムがジャンプ命令のついでに行う。

そのための命令

  • BX:無条件ジャンプ
  • BLX:リターンアドレスをプッシュしてジャンプ

ARMとThumbが混在しているので、リンカとか実行環境も区別しないといけない。

関数ポインタを呼び出す時にも、関数の先がARMなのかThumbなのかわからないと、ジャンプできない。関数のアドレスの最下位ビットはARMとThumbを区別するフラグになっている。

int main() {
  printf("Hello world\n");
}

と有ったときに、自分がコンパイルする main 関数がどっちなのかは知っているけど、共有ライブラリのprintfがどっちのモードでコンパイルされたのかは分からない。
コンパイラはBL命令またはBLX命令(X:モードを変える)で出力し、リンカが最後につなぎ合わせる時には、どっちのモードなのかわかるので、命令を書き換える。

PC相対のload/store命令がないので、絶対アドレスかレジスタの値をアドレスとみなしてアクセスすることしかできない。ARM32の場合、今実行中のアドレスが普通の汎用レジスタのように見えるので、その値と別のレジスタの値を足すみたいなことをやると、オフセット+現在の位置で絶対アドレスを生成できるので、PCの値を足すことができる。

add lr, pc, lr # %lrにPCの値を足す

Sun SPARC64

※発表スライドから

Sunという会社が昔あり、昔のSUNはMotorola 68k シリーズを使ってたけれども、Sun-4から自社開発のCPUに切り替えて、それがSPARCです。

SPARCは32ビットと64ビットがあり、moldがサポートしているのは64ビット。

PC相対のload/storeg無いので、i386と同じく GOT からグローバル変数にアクセスしている。
これは多分偶然ではなくて、SUNの人たちが i386 の ABI を作ったからと思う。

sethi  %hi(. - _GLOBAL_OFFSET_TABLE_), %l7
add    %l7, %lo(. - _GLOBAL_OFFSET_TABLE_), %l7
call   __sparc_get_pc_thunk.l7
nop

__sparc_get_pc_thunk.l7:
retl
add  %o7, %l7, %l7

面白い特徴としては、SPARC64は命令長が32ビット固定のRISCアーキテクチャーにもかかわらず
range extension thunkがいらない。

なぜかと言うと、call 命令に含まれている即値が30ビットもあるから。

先頭の2ビットが01で、残りの部分は全部アドレスで、30ビット指定できる。すべての命令は4バイト境界にアラインされているので、x4を安全にすることができて、どの命令もアドレスの最後は00なので、32ビットフルに指定できる。
なので、±2 GiB に飛べるので、Range Extension Thunkは実質いらない。

※発表スライドから

一方で、エンコーディング可能な空間の1/4がコール命令1個だけで占めめられているので、これがいいトレードオフだったのかはわからないけれども、SPARC64はこういうデザインになっている。

時代を感じるのは、PLTが自己書き換えコードなこと。

メモリ上にロードされている他の共有ライブラリに飛ぶかもしれない関数はPLTに1回飛び、そこから改めて、目的の関数に飛ぶ。PLTはたくさんあるので、一発で目的の全部のアドレスをロード時に解決するわけではない。

一番最初に呼ばれた時に、シンボル名を見に行って解決し、解決されたアドレスをどこかに書き込んでおいて、それ以降はシンボル名解決をスキップしてジャンプする。

SPARCは解決されたアドレスをどっかのデータ領域に書き込むのではなく、PLTの命令自体を自己書き換えして、直接飛ぶようにしている。

解決されたシンボルのアドレスを保存する領域が要らなくなるけど、セキュリティがガバガバになるので、時代を感じるデザイン。

RISC-V

※発表スライドから

RISC-Vは新しいCPU/ISAで、極めてきれいな感じの作りになっているけど、psABIという意味では、非常に特徴的なABIになっている。どういうことかと言うと、range extension thunkとは違う方法により、長いジャンプを実現している。

RISC-Vでは、関数呼び出しは1命令じゃなくて、常に2命令使うことになっている。

※発表スライドから

一番最初のAUIPC命令が上位20ビットとPC+オフセットを設定し、次のJR命令が下位12ビットを指定してジャンプ。

1命令で飛べるのに、2命令使うのは非効率。

そのため、RISC-Vではセクションを縮めて良いルールになっていて、ジャンプ先が1命令で到達可能だったら、リンクは2命令を1命令に書き換えるルールになっており、Range Extension Thunkとはある意味逆。

マシンコードが可変長というのは、他のpsABIでは見られない特徴なので、特別に実装する必要がある。

ドキュメントも新しいので、ドキュメントがバグっていたり、おかしい場所があって、報告していたら、いつの間にかRISC-VのpsABIのレビュアー側に足され、標準化をする側になった。

32-bit PowerPC

※発表スライドから

32ビットのPowerPCは普通のRISCプロセッサ でSPARCみたいなもの。

PC相対のload/storeが無いのでどうするかと言うと、また例によって call 命令みたいなやつを使い、複雑なルールとともに %r30 にGOTのアドレス的なものを入れると、再計算しなくて済む。

※発表スライドから

ただし、このルールが複雑なので、moldでは毎回再計算している。

64-bit PowerPC

※発表スライドから

64ビットのPowerPCはv1とv2の2つの異なるABIがある。

ELFv1 はもともとのやつで、ビッグエンディアン。関数ポインタの扱いとかが特殊。
ビッグエンディアンだと、移植などが辛いというフィードバックがあり、IBMもクラウドをプッシュしていくにあたり、ビッグエンディアンはIntelからのポータビリティとかの問題で、つらいので、リトルエンディアンのほうが良かろうということで、ELFv2 が作られた。

その際に、エンディアンをスイッチするだけでなくて、ELFv1の良くなかったところを直そうというので、ちょっと少し違うABIになっている。

64-bit PowerPC ELFv1

※発表スライドから

CPU自体はv1もv2も同じ64ビットのPowerPC。

PowerPCはPC相対load/store命令がなくて、関数ポインタが関数を指してない。

関数ポインタが関数を指してないとはどういうことか?

PC相対がないので、GOTのアドレスを毎回計算している。
別の共有ライブラリのコードがGOTを計算すると、違うアドレスになるけど、同じELFファイルに存在する限りにおいては、GOTのアドレスは同じなので、%r2 にセットすることで、なるべく使せるような仕様がある。

同じファイルに飛ぶということがわかっていれば、このアドレスは同じで、PLT経由で飛ぶ場合はPLTが外の関数か内の関数かというのは知っているので、PLTがよしなにやってくれる。
ただし、関数ポインタ経由で直接飛ぶ時にはよくわからない。

どういうことかというと、関数ポイントはPLTを指しているわけではなくて、関数を直接指しており、その関数が同じ共有ライブラリー内にあるかわからない。

関数ポインタは関数のアドレスを直接指しているのではなくて、関数ディスクリプタ(関数のアドレス、関数を呼ぶ前に%r2にセットするべき値)という2つの値のタプルを指していており、関数ポインタが少し変。

関数のアドレスを取るようなリロケーションがある時には、このタプルが入っているテーブルをmoldが作る必要がある。

64-bit PowerPC ELFv2

※発表スライドから

ELFv2は関数ポインタ周りが変わっており、関数はエントリーポイントが「グローバル」と「ローカル」の2つがある。グローバルとローカルの間には2つの命令が入っている。

同じファイルでのジャンプと知っている場合には、ローカルに直接飛び、同じファイル内かどうか確信を持てない場合にはその関数にジャンプする前に、その関数自体のアドレスを%r12にセットして、そのレジスタの値で飛ぶ。

関数はGOTとの相対位置を知っているので、%r12から正しい%r2を計算できる。

ELFv1にあった関数ディスクリプタは無くなり、関数が2つのエントリーポイントを持つ仕組みになっている。

そもそもPowerPCにPC相対のload/storeがあれば、こういう苦労をしなくて済んだ。

SH-4

※発表スライドから

※ https://en.wikipedia.org/wiki/File:SH7091_01.jpg

SH-4(SuperH-4;スーパーエイチ)は日立製作所/ルネサスエレクトロニクスが開発している32ビットのRISC CPU。セガのドリームキャストで使われていた。

命令長が2バイト(16ビット)なので、大きい即値を入れられない。

例えば、32ビットの値を2命令を使って組み立てるといったこともできない。16ビットの値と16ビットの値を分割すると、命令の入る位置(スペース)が0になってしまう。
どうするかというと、オフセットとかアドレスは命令の近くに置いて、PC相対でロードする。そこの部分の実行にかかりそうになったらジャンプして、そのデータをスキップする。

命令そのものをリロケートすることはなくて、その32ビットのオフセットとかをリロケートすることになるので、リロケーションのタイプが少なくて、実装も簡単になっている。

※発表スライドから

問題はドキュメントがめちゃくちゃ貧弱であること。
メモみたいなテキストファイルがスペック扱いで、普通に間違っているし、不完全。

カンと経験でguesstimateにより再構築する必要があり、GNUリンカを使ってもクラッシュするバイナリができたりするので、ビットロットが進んでいる。

補足

セガサターンに使用されていた2世代前の SH-2 はパテントが切れているため、オープンソースにした設計図を元にチップを製造する eFabless社のプロジェクトの参加中です。

https://platform.efabless.com/projects/1542

DEC Alpha

※発表スライドから

※ https://en.wikipedia.org/wiki/DEC_Alpha

最後がDEC Alpha。

DEC Alphaは1990年代に一瞬煌めいたプロセッサで、その後、消滅してしまった。25年持つISAとして設計されたけど、5年ぐらいしか持たなかった、悲しいCPU。

4バイト固定長命令で、RISC/SparcみたいなCPU。

問題は公式のpsABIドキュメントが存在しないこと。社内的には存在するかもしれないけど、インターネット上にはみつからない。詳しい人の話によると、GNU ldのソースコードが最も権威のある ドキュメント で、地獄のような状態。

GNU ldのソースコードを読むのはめんどくさいので、リロケーションの名前から動作を類推したり、逆アセンブリを眺めて推測する必要があり、動けば良いかという感じで動いているのが現状。

最後に

いろんなプロセッサに移植したけど、移植は意外と簡単です。

昔は移植はよくわからないから、移植するCPUに詳しい人に任せたほうが良いかなと思っていたけど、全然そんなことはなくて、リンカに詳しい人がCPUのマニュアルをちょろっと読んで実装したほうが全然早い。

psABIは大きくて複雑だったりするけど、完全に理解する必要もないし、完全にドキュメント通りにやる必要もない。

テストセットが全部通ったら、かなり普通に動くはずなので、それでよしとする。
主要な実装もドキュメント通りに実装されているわけではないので、ドキュメントを信用しすぎるのも良くない。

移植の簡単さは、そのpsABIが他のpsABIから大きく逸脱していないかどうかに関わっている。

MIPSやHP/PA(PA-RISC)は、大きく逸脱しているので、めんどくさくてサポートしていないけど、逸脱していなければ、1日とか、せいぜい1週間で移植できる。

80年代とか90年代に戻れるとしたら、PC相対load/storeを実装するよう、真っ先に伝えたい。

以上。

Q＆A

psABIのpsってなんですか？

psABIはProcessor Specific Application Binary Interfaceの略。
ABIのCPU依存部のこと。

https://twitter.com/gachacomplete/status/1614555041465270273

処理の切り分け

これだけABIがあるなかで、移植コードはどんな感じで処理が切り出されているのか?

https://github.com/rui314/mold/tree/main/elf というディレクトリが切られている。

moldの移植で一番特徴的なのは、コードが全部テンプレートになっていること。

すべての関数やデータ構造は基本的にテンプレートになっていて、そのテンプレートの型パラメーターがターゲットを取ることになっています。

メイン関数のx86_64版とか、メイン関数のSH4版のテンプレートがインスタンシエートされることになっている。

テンプレートプログラミングを使って動的にディスパッチしているのではなくて、全体がクローンされて、ターゲットごとにコードが生成されているイメージです。

これによりデータ構造が微妙に違っていたりする時に、データ構造のレイアウトの違いを動的にディスパッチするのは難しいけど、スタティックにテンプレート・プログラミングにディスパッチするだけだと、名前さえ一致すれば、そのままテンプレートが展開されてコンパイルされるだけ。

テンプレートプログラミングによりかなりうまく行っている。具体的にはソースコードを見てほしいけど、C++20の機能をいろいろうまく使って、自分なりにはかなりエレガントに移植性がハンドルされていると思うので、ぜひ、ソースコードを読んでみて下さい。

moldはELF 専用？

mold はELF専用。

以前はMac OSのMach-Oもサポートしていたけど、商用の方のリンカ sold にコードを移した。

moldだから移植が楽なのか?

なんで他のリンカがあんなり難しくなっちゃっているのか、よくわからない。

移植が難しいのは、他のリンカは移植した人たちが全員別々だから。
ターゲットの関係者が実装している。
そうすると、移植性を上げて、いい感じにやるみたいなインセンティブはあんまりない。

例えばPowerPCのポートがすでに存在する時にMIPSに移植するときは、powerpc.cc みたいなやつをmips.cc にコピーして、中身を書き換える。
そうすると、猛烈に似たようなコードが合って、しかも一部違うみたいな事になりがちで、ある意味、無責任体制みたいなことに、仕組み的になりがち。

コンウェイの法則。

LinuxのSH-4サポート

LinuxのアップストリームではSH4を削除する提案が出されている。

LKML: Christoph Hellwig: remove arch/sh

SH-4はビットロットが激しく、C++の例外を投げるコードをGCCでビルドしてもクラッシュする。

Thunkの正式用語

みんな、ベニア、Thunk、range extension thunkと適当に言っていて、オフィシャルな用語はない。

レトロコンピュータにリンカを移植するモチベは?

https://twitter.com/Linda_pp/status/1614547977246494720

レトロコンピュータだとmoldの長所の速度を活かせないのでは?

愛好家は趣味だからやっている。

LLVM用のバックエンドを作っていたり、VMを使えば、メモリが3GBあるm68kの環境を用意できるので、LLVMもセルフビルドできるといえばできる。
実際にそんなパワフルなチップが存在したことはないが。

アクティブなコミュニティがあるらしくて、特にAmigaで68mを趣味人がやっているっぽくて、特にドイツ方面で盛んな雰囲気。
お金を払ってでもサポートしてほしいモチベがあるということは、結構それなりに本気といえば本気。

Crowdfunding for m68k support in the Mold linker

Motolora以外のアーキテクチャーを移植する理由。

UbuntuやSUSEがサポートしているアーキテクチャーはサポートしたい。
例えば、ビルダーとか使って、自動テスト環境とかでいろんなアーキテクチャーでビルドしているプログラムがある。

例えばBlenderはs390をテストしている。

同じツールが使えると、採用してもらえるけど、アーキテクチャーごとにツールが別れていると使ってもらえない。だから、活きているプラットフォームについてはサポートしたい。
そうすると、ARM32/64,x86, PPC 64v2, s390などはサポートしないといけくなる。

UbuntuもIBMマネーが流れていて、S390をサポートしている。
銀行とかメインフレームのユーザーからのマネーが流れ込んでいる。

残りのマイナーな

  • Alpha
  • SH4
  • Sparc
  • PPC32

などは試しにやってみただけ。
どれも移植は1日とか2日、最大でも、1週間もかからずに移植できているので、大した手間ではない。

あとは、レトロコンピュータに対する愛があり、ここらへんのアーキテクチャーはドキュメントが存在しなかったり貧弱だったりするので、わかりやすくまとまっている資料としてのソースコードは重要性が大きい。

moldのこの800行の移植分だけで基本的に全部動きますよってあったら、非常に資料的価値が大きい。

12,000行の goldリンカのalpha.ccを読まないとなると大変だけど、400行だったら、動く説明文みたいな感じで読めるので、これ以上わけが解らなくなる前に、資料的価値としてまとめておきたいなっていうのはある。

ライブな実装があるのは価値がある。

RISC-Vのレビュアーに追加された

RISC-VのpsABIのレビューをしてLGTMしているけど、なんの権限があってやっているのかとか、意味はよくわからない。ぼくがApproveして良いのかも、よくわからない。

レビュアーに足されて、RISC-Vの中の人から言われてレビューしたりしている。

ただ、考えてみれば、ある意味当然といえば当然。

実際にリンカを作っているので、実装的にありえないとか、間違っているとか、僕とあとごく少数の人しかわからない。

正直に言って、僕が世界で一番詳しいレベルなので、レビューを依頼されるのは、わかるといえば、わかる気がする。

s390

s390のハードを売るためにはソフトウェアが重要なので、IBMはLinuxに全とっかえすると決めていて、カーネルのメンテナンスは終わっているし、ソフトウェアアセットを腐らせないように、Ubuntu と提携して頑張っている。

IBMマネーが僕(Ruiさん)にも流れ込んで来ないかなぁと期待

moldのサポート

有償版 moldのsoldというリンカも作っており、Mac OSもターゲット。

soldでライセンス商売をやっていきたい。

GitHub Sponsorsを募集している。

お金がもっとあれば、人も雇える。

新機能開発を有償で受けたりもしているので、そういうサポートも歓迎。

Discussion