リンカースクリプト入門

RISC-Vのベアメタル環境向けに実行ファイルを作りたかったが、 どうやってコードの配置を行うかわからなかったので、 既存のリンカスクリプトを参考にしつつリンカスクリプトを調べてみた。

参照するのは riscv-test-env に入っている、 ベアメタル環境向けの以下のスクリプト

OUTPUT_ARCH( "riscv" )
ENTRY(_start)

SECTIONS
{
  . = 0x80000000;
  .text.init : { *(.text.init) }
  . = ALIGN(0x1000);
  .tohost : { *(.tohost) }
  . = ALIGN(0x1000);
  .text : { *(.text) }
  . = ALIGN(0x1000);
  .data : { *(.data) }
  .bss : { *(.bss) }
  _end = .;
}

GNU ldはこのドキュメントを参照した。

リンカーの役割は、複数の入力オブジェクトファイルに含まれるセクションを、出力オブジェクトファイル(あるいは実行ファイル)のセクションに配置すること。 セクションは実行時に読み込まれる loadable と、実行時に確保されるが読み込むデータがない allocatable がある。 またどちらでもないセクションも存在し、デバッグ情報などを格納している場合もある。 loadable または allocatable なセクションは2つのアドレス、VMA(virtual memory address)とLMA(load memory address)を持つ。 たいていの環境では、どちらも同一だが、場合によってはROMに読み込まれて、実行時にコピーされるような環境も存在する。 またオブジェクトファイルは symbol table も含んでいる。symbol は名前とアドレスとその他情報を持っている。 C などは関数やグローバル変数に symbol を利用する。

まずは、OUTPUT_ARCH だが、これは出力マシンアーキテクチャを指定する。引数に与えられる名前は BFD ライブラリで使われる名前。 この辺を見ると良い気がする。

ENTRY はプログラムのエントリーポイントを指定する。引数は symbol 名。 スタートアドレスがあればなくても問題ないと思うが、どうやら ELF ヘッダーは entry point の指定ができるらしく、 そのために使われるらしい。

SECTIONS が一番重要なセクションの配置に関するコマンドになる。 SECTIONS のあとにはブレースを使って、複数の sections-command を並べる。 sections-command はいくつか種類があるが、今回使っているのは、symbol assignment と output section description である。

symbol assignment は symbol に対して、アドレスを指定する。 . は特別な symbol で location counter と呼ばれる。 location counter は出力される section のアドレスを示し、代入されると出力先のアドレスが移動する。 またセクションを配置するごとに、自動的に値が変更される。

. = 0x80000000; はこれよりあとのセクションが 0x80000000 に配置されるように設定するという意味になる。 . = ALIGN(0x1000);ALIGN 関数を呼び出した結果を、location counter に設定している。 ALIGN 関数は現在の location counter の値を、引数で指定したバイト数でアラインメントした次のアドレスを返す。 結果として、ここでは次の配置アドレスが 0x1000 単位に整列された値に設定されることになる

output section description はコロンの左辺で指定した出力先セクションに対して、右辺で指定した入力セクションを配置する意味になる。 左辺に指定するセクション名には曖昧性を除くために、スペースが必須になっている。

コロンの右側にはブレースの中に、output-section-command を書く。 output-section-command は input section description などがかける。

input section description は入力オブジェクトファイル名とその後にカッコで入力セクションを指定する。 それぞれワイルドカードを指定できる。

.text.init : { *(.text.init) }.text.init 出力セクションに対して、任意の入力ファイルの .text.init セクションを配置するという意味になる。

Mellanox ConnectX-3 VPIのセットアップ

サーバ、クライアント間の帯域を上げたくて、Mellanox ConnectX-3 VPIをセットアップした。 入手したのはMCX354A-FCBTで、スペック上40Gの帯域がある。

購入は、ebayでbrand newのものが送料含めて7000ほどで買えた。 また、接続用のケーブルはfiberjpで汎用のパッシブDACを2000円ほどで購入した。

インストール先は、ちょっと古めのサーバと第三世代ryzenを搭載したデスクトップ。 サーバの方はカードを挿入したらそのまま認識までした。

一方デスクトップ機の方は、そのままだと認識しなかった。 切り分けを行った結果、UEFIでPCIeのバージョンを3に固定することで認識した。 第三世代ryzenとX570チップセットだとPCIe4が使えるので、 NICマザーボードネゴシエーションがうまく行かないのかもしれない。 また、そのままだとLinuxのドライバの初期化が失敗する。 おそらくPCIeデバイスがそれなりにあるので、メモリの確保に失敗しているらしい。 MSI X570 Gaming Plusでは、「Above 4G memory/ Crypto Currency mining」をEnableにすると解決した。

あとは、OS側からNICファームウェアを更新する。 利用しているのはArch Linuxだが、ファームウェア更新用のソフトウェアの最新版がdebrpmでしか配布されていない。 これらのパッケージから取り出しても良かったが、OSS版が存在したのでそちらを使うようにした。

$ git clone https://github.com/Mellanox/mstflint.git
$ cd mstflint
$ ./autogen.sh
$ ./configure --disable-inband
$ make
$ make install

デフォルトだとInfiniBandのライブラリがないとビルドできないので、明示的に無効にする。

OSS版では、ツールセットの先頭にmstがつくので、手順のflintはmstflintと読み替える必要がある。 また、デバイスの指定はPCI ID(?)を利用する。

$ lspci|grep -i mellanox
2d:00.0 InfiniBand: Mellanox Technologies MT27500 Family [ConnectX-3]

$ mstflint -d 2d:00.0 q
Image type:            FS2
FW Version:            2.11.1280
Device ID:             4099
HW Access Key:         Disabled
<snip>
VSD:
PSID:                  ORC1090120019

セラーの説明ではHPのOEMとのことだったが、実際にはOracleのものらしい。 とはいえ、以降の手順では特に関係はない。

手順はこちらを参考にした。 この手順では、カスタムファームウェアを作ることなく、直接Mellanoxの最新ファームウェアを書き込む。

まずは、現在のファームウェアと設定をバックアップする。

$ mstflint -d 2d:00.0 ri orig_firmware.bin
$ mstflint -d 2d:00.0 dc orig_firmware.ini

次にファームウェアを書き込む。

$ mstflint -d 2d:00.0 -i fw-ConnectX3-rel-2_42_5000-MCX354A-FCB_A2-A5-FlexBoot-3.4.752.bin -allow_psid_change burn

    Current FW version on flash:  2.11.1280
    New FW version:               2.42.5000


    You are about to replace current PSID on flash - "ORC1090120019" with a different PSID - "MT_1090120019".
    Note: It is highly recommended not to change the PSID.

 Do you want to continue ? (y/n) [n] : y
Burning FS2 FW image without signatures - OK
Restoring signature                     - OK

成功したらリブートする。

リブート後にポートをEtherに設定する。

$ mstconfig -d 2d:00.0 set SRIOV_EN=1 LINK_TYPE_P1=2 LINK_TYPE_P2=2

Device #1:
----------

Device type:    ConnectX3
Device:         2d:00.0

Configurations:                              Next Boot       New
         SRIOV_EN                            False(0)        True(1)
         LINK_TYPE_P1                        VPI(3)          ETH(2)
         LINK_TYPE_P2                        VPI(3)          ETH(2)

 Apply new Configuration? (y/n) [n] : y
Applying... Done!
-I- Please reboot machine to load new configurations.

更に再起動することで、通常のNICと同様に利用できる。

iperfで速度計測した結果、MTU9000で13Gbpsほどの速度が出た。 CPUでサチっているようでカタログスペックは出ないものの、 10Gよりも速度は出ているので十分だろう。

FOSS でハードウェア開発を行う

ハードウェア開発につかうツールチェインはベンダー製ソフトウェアが多いが、 利用する FPGA によっては FOSS ツールチェインでも可能なようだ。

Fomu に載っている iCE40 はビットストリームの解析が完了しているため、 すべての工程を FOSS ツールで完結できる。

HDL の合成は yosys を使うことで行える。 yosys のマニュアルは長いのでちゃんと読んでいないが、 コマンドを入力していくことで様々な工程を実施できる。 この工程は TCL でスクリプト化することもできる。 また自分でスクリプトを組まなくても、ビルトインで良い感じの合成を行ってくれる synth_ice40のような便利コマンドも用意されている。

yosys にもシミュレーションを行う sim コマンドが用意されているが、 対応している機能が少ないようなのでテストベンチを書くには iverilog や verilator を使うのが良さそうだ。

iverilog は verilog シミュレータで verilog でテストベンチを記述するのに使える。 ただし即時 assert が master ブランチでしか使えないので注意が必要。 ハードウェア開発に詳しくないのだが、assert を使わずに波形を確認するほうが一般的なのかもしれない。 波形は gtkwave を使えば見ることができる。

verilator は合成可能な verilogC++コンパイルしてくれるシミュレータだ。 高速なのが売りらしく、公式サイトでは iverilog に比べて100倍高速とのことだ。 ハイレベルHDLのChicelはverilatorでのテストが可能になっていたりする。

ディジタル回路とコンピュータアーキテクチャで例に出されている sillyfunction を例に各ツールを試してみた。 https://github.com/toshipp/learn-verilog/tree/master/sillyfunction

make simで verilator を使ったシミュレーションを行うことができる。 verilator では verilog で記述されたモジュールが C++ のクラスにコンパイルされるので、 そのクラスを生成して、インプットを設定し eval を読んでやることでモジュールの挙動をシミュレーションすることができる。 この段階になると単にソフトウェア的なテスト手法が適用できるので verilog でテストベンチを書くよりも良いかもしれない。

make showでは yosys を使ってモジュールをネットリストに変換し、grapviz によって表示する。 挙動確認のためにスクリプトで低レベルコマンドを使ってネットリストに変換している。 procコマンドは verilog の always などをフリップフロップに変換してくれる。 opt は基本的な最適化を行う。 techmapはハイレベルな回路をローレベルな素子に変換する。 abcは組み合わせ回路をターゲットに応じて最適化する。

make testbenchX.vvp は iverilog によってテストベンチをシミュレーション可能ファイルに変換する。 変換されたファイル実行可能で、内部的には vvp コマンドによって処理される。

Fomu 事始め

USBスロットに収まるサイズののFPGAバイスで6000円ぐらいでCrowd supplyで購入できる。

自分の場合はストックがあったので、発注してからUPSで3日ぐらいで届いた。

搭載しているFPGAはLatticeのiCE40UP5kというものを積んでいるらしい。 全然わかっていないのでどの程度の回路が組めるかわからないが、LUTが5000個あって、RISC-Vを組み込んでいる。 その上で DFU のソフトウェア実装が動いている。

ソフトコアとブートローダfobootというリポジトリで管理されている。 ソフトコアは hw ディレクトリに収められていて、Migen という python による HDL ツールでビルドされるらしい。 とはいえ、メインの RISC-V の実装は、VexRISC-Vによるものを使うらしく、hw/rtlverilog ファイルが収まっている。 VexRISC-Vは SpinalHDLという高レベルHDLで実装されている。 SpinalHDL は Scala で実装されており、Chiselといい、この分野は Scala が流行っているのかもしれない。

Getting Started として workshopがあるのでこれに沿って初めてみる。

手元の環境は arch linux を使っている。

workshop は Foboot として v2.0.3 以上を要求している。

$ sudo pacman -S dfu-util
$ sudo dfu-util -l
...
Found DFU: [1209:5bf0] ver=0101, devnum=5, cfg=1, intf=0, path="1-9", alt=0, name="Fomu PVT running DFU Bootloader v1.9.1", serial="UNKNOWN"

確認すると残念ながらバージョンが古いのでまずはアップデートが必要になる。

Bootloaderのページを参考にアップデートを行う。

ファームウェアの種類としては PVT (Production Validation and Testing)を選べば良い。

$ curl -OL https://github.com/im-tomu/foboot/releases/download/v2.0.3/pvt-updater-v2.0.3.dfu
$ sudo dfu-util -D pvt-updater-v2.0.3.dfu
$ sudo dfu-util -l
...
Found DFU: [1209:5bf0] ver=0101, devnum=6, cfg=1, intf=0, path="1-9", alt=0, name="Fomu PVT running DFU Bootloader v2.0.3", serial="UNKNOWN"

workshop リポジトリを clone する。 400MB 程度をダウンロードするので少し時間がかかる。

$ git clone --recurs https://github.com/im-tomu/fomu-workshop.git

次にツールチェインをインストールする。 手順ではビルド済みバイナリを利用するが、OS 標準リポジトリと AUR を使ってみる。

nextpnr の依存で必要な trellis ビルドがコケるので trellis-git を選択する。

$ yay -S nextpnr-git
$ sudo pacman -S yosys
$ sudo pacman -S wishbone-utils
$ yay -S riscv64-unknown-elf-gcc riscv64-unknown-elf-newlib

udev を設定して dfu-util を sudo なしで動かすのが公式手順だが、今回はスキップ。

workshop リポジトリに micropython のバイナリがあるのでロードして動かしてみる。

$ sudo dfu-util -D micropython-fomu.dfu

これで fomu がシリアルデバイスに化けるので、screen などでつなぐ。

$ sudo screen /dev/ttyACM1
MicroPython v1.10-308-g421dcd2 on 2020-01-03; fomu with vexriscv

>>>

サンプルはエルチカさせるものだが micropython が拡張されているので簡単。

>>> import fomu
>>> rgb = fomu.rgb()
>>> rgb.mode("idle")
>>> rgb.mode("done")
>>> rgb.mode("writing")
>>> rgb.mode("error")

LED 点滅は Lattice のハードウェアブロックで実装されていて、レジスタをメモリーにマップしているらしい。 この辺でやっているっぽいが、migen を勉強しないと読めないですね。

コンポーネントは、wishbone bus というバスでつながっている。 fomu の場合は bridge が wishbone bus につながっていて、USB 経由でバスをいじることができる。 そのため USB 経由で直接メモリをいじったりできる。 これを利用して gdb でリモートデバッグすることもできる。

あとは、verilog で Lチカしたり、Migen で wishbone bus につながる USB デバイスを作ったりという感じ。

CMU 15-445 Logging Protocols + Schemes

  • バッファプールの書き出しは2つのポリシーに分解できる
    • Steal はコミット前のデータを書き出すか
    • Force はコミット時にダーティなデータを書き出すか
  • Shadow paging
    • master copy と shadow copy を作って、書き込みを shadow に行い、commit 時にスワップする
    • no-steal + force なアルゴリズム
    • リカバリ時には shadow を破棄する
    • ランダムライトになるし GC が必要なので使っている DB はほとんどいない
    • また no-steal なのでメモリより大きなデータが扱えない
  • Write-Ahead Log
    • 書き込みをログする
    • steal + no-force なアルゴリズム
    • トランザクション開始時に begin ログを、終了時に commit ログを書き込む
    • トランザクションコミット時にログを fsync する
    • 複数のトランザクションを fsync を一発にする group commit を行えばコストを下げられる
    • ログの方法は3種類
      • physical logging は更新行の情報を書き込む
      • logical logging はクエリーを書き込む
      • physiological logging はページ内の論理更新を書き込む
      • physical は更新量が多いとログが多くなり、logical は undo がむずい。
    • checkpoint
      • ログの適用をどこからするべきかわからない
      • ダーティページを書き出した直後に checkpoint ログを書き込むことで、以後のログだけ undo/redo すれば良い

CMU 15-445 Multi-Version Concurrency Control

  • MVCC は複数バージョンを持つことで、writer は reader をブロックせず、reader は writer をブロックしない

    • writer がロックを取っていても reader は前のバージョンを読めば良いのでブロックされない
    • 逆に read していても writer は新しいバージョンを作れば良いのでブロックされない
    • W-W は 2PL なり OCC なりで調停しないといけない
    • (疑問)MVCC と S2PL を組み合わせると read only じゃない限り、ロック取っちゃうから嬉しくない?
  • version storage

    • append only
      • バージョン番号をつけた新しい行を追加する
      • 簡単だけど copy が必要
    • time travel storage
      • time travel table に古い行を突っ込んで、メインテーブルには新しい行を入れる
      • gc が楽
    • delta storage
      • 変更したカラムのデータだけ入れる
      • 差分が少ない
  • garbage collection

    • tuple level
      • background vacuuming
        • シーケンシャルスキャンして不要なデータを消す
        • シーケンシャルスキャンでバッファプールが死ぬ
        • dirty page bitmap を持てば回避できる
      • cooperative cleaning
        • 各スレッドがバージョンチェインを舐めるときに不要なデータを消す
    • trx level (advanced)
  • index management

    • バージョンを扱うと更新ごとに index の更新が必要になる
    • secondary index が参照する先を pk にすると、更新が減る
    • あるいは間接層をはさんで index の参照先と物理IDのマッピングを作る。

CMU 15-445 Timestamp Ordering Concurrency Control

  • Timestamp Ordering Concurrency Control
    • optimistic な方法
    • 2PL がロックを使ってserializableになるのに対して、serializableでないならアボートしてリトライする
    • トランザクションの実行時にタイムスタンプをふって、自分が触ったオブジェクトが、より新しいタイムスタンプを持つトランザクションが操作していないか確認する
      • もしもしそうなら未来に実行されるべきトランザクションの内容を見ていることになるのでserializableではない
  • Optimistic Concurrency Control
    • read 時にローカルコピーを作ってwriteするときにやってよいか確認する
  • Partition based T/O
  • Phantom problem
    • ロックをrowごとに取ると隙間にインサートされることを防げない
    • 同じSELECTが異なる結果を返すことがある
  • Predicate locking
    • 論理演算からロックを生成する
    • 次元が増えると破綻する
  • Index locking
    • 扱う値の範囲のindexをロックする
    • インデックスがないなら全ページやテーブルをロックする
  • Phantom を防ぐと重いので Isolation level を導入する
    • serializable より低い分離レベルなら phantom がありうる