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 がありうる

EFI system partition を拡張する

EFI system partition(ESP) の容量が足りなくて、ファームウェアアップデートが失敗したので拡張した。

今回は、ESP の後ろに別のパーティションが存在し、そのままではパーティションのサイズ変更ができなかった。 そのため、ESP を空き領域に作り直して内容をコピーする作戦を取った。

UEFI は GUID の特定のフラグを持つパーティションを ESP として使うらしい。 ファームウェアがまともなら今回の作戦でもうまく行くはず。 幸いなことに手元の XPS 13 9380 はまともなファームウェアだったらしくうまく行った。

方法としては、linux 上から ESP に保存されているファイルを保存しておく。 次に parted で既存の ESP を削除し、別の場所に esp と boot フラグを立てたパーティションを作る。 あとは、fat32 でフォーマットして保存しておいたファイルを書き戻す。

linux の fstab を書き換えるのを忘れていたので systemd がレスキューモードに落ちたが、 fstab を書き換えて復旧できた。

もとから入っている windows も BitLocker を有効にしていたので若干不安だったが正しくブートした。

CMU 15-445 Two-Phase Locking Concurrency Control

  • dependency graph はスケジュールを与えられたときにserializeかどうかを判定する方法
  • クエリをserializeに実行するにはどうするか?
    • lock を使う
  • 2 Phase Locking
    • grow phaseとshrink phaseがある
    • 前者ではロックを取ること、後者は開放することしかできない
  • 2PL ではコミットあるいはロールバックの前にロックを開放できる
  • Strict 2 PL
  • 2PLはデッドロックを起こす
    • 解決には2種類ある
    • deadlock detection
    • deadlock prevention
  • deadlock detection
    • dependency graphを作成してループがあればアボートさせる
    • バックグラウンドでDGを作れば即応性はなくなるが、計算コストが下げられる
    • これはトレードオフなのでDBMSはチューニングパラメータを持っている
  • deadlock prevention
    • ロックまちが取れないときに、どちらかを殺す
    • DGを作る必要がない
    • 先に開始したほうを高プライオリティにする
    • ロック順序を一方後にするためのプロトコル
    • wait-die
      • 高プライオリティ側はロックを待てる
      • 低プライオリティは死ぬ
    • wound-wait
      • 高プライオリティはロックを持っている方を殺す
      • 低プライオリティはロックを待つ
  • ロック粒度
    • タプルだけでロックを扱うとたくさんのタプルを扱うとたくさんのロックを取らないといけない
    • ロックを階層化して低階層でのロックの数を減らす
    • Intention-Shared(IS), Intention-Exclusive(IX), Shared+Intention-Exclusive(SIX)を導入する
      • ISは下層で読むときに使う
      • IXは下層で書くときに使う
      • SIXは下層で良い書きするときに使う

CMU 15-445 Concurrency Control Theory

  • トランザクションの性質としてACIDがある
  • 一番簡単な方法はシングルスレッドで実行して、データベースファイルをコピーして、書き換えてスワップすること
  • Aを守る方法としては shadow paging と logging がある
  • schedule について
  • serial schedule とはトランザクションを一つずつ実行するスケジュール
  • equivalent schedules とは実行結果が同じになるスケジュール達のこと
  • serializable schedule とは serial schedule と同じ結果になるスケジュールのこと
  • conflict とは R-W, R-W, W-W を起こすようなオペレーションの組
    • これが起こると anomaly が置きてうれしくない
    • R-W だと2回読むと異なるデータが読めちゃう
  • conflict serializable とは conflict の順を保ったまま serial schedule に並び治せるスケジュール
    • dependency graph を作って循環がないかみれば効率的に判定できる
  • view serializable とは conflict serializable に加えて blind write を許すスケジュール
    • dependency graph が循環しても許される場合がある
    • 効率よく判定することができないので使われていないらしい