2019-02-20

BLS署名における双線形性（ペアリング）について

ブロックチェーン系プロジェクトで着目される暗号技術のP.21-22を理解するために双線形性（ペアリング）について調べた。自分が理解するに至った軌跡をメモベースで残す。

余談だが、調べる過程で双線形写像（Bilinear maps）とペアリングの違いが気になった。個人的な印象としては、ペアリングは暗号分野寄りに使われる用語だと思ったが、Intro to Bilinear Mapsにも以下のように書いてあるので、本記事では大体同じものとして扱う。

Bilinear maps are called pairings because they associate pairs of elements from G1 and G2 with elements in Gt.

(拙訳) 双線形写像はペアリングとも呼ばれる。 G1とG2からの要素をGtでペアとして関連付けるからだ。

以下、調べた内容。¹

双線形とは何なのか

本節は、ブロックチェーン系プロジェクトで着目される暗号技術がベースとなっている。

双線形を定義するにあたり、まず2種類の楕円曲線の生成元を $P, Q$ とする。このとき、素数位数 $p$ の加法巡回群 $G_1, G_2$ は、以下のように表現できる。

$G_1 = \lbrace 0, P, 2P, ..., (p-1) P \rbrace$
$G_2 = \lbrace 0, Q, 2Q, ..., (p-1) Q \rbrace$

また、有限体 $\mathbb{F}_p$ と、位数 $p$ の乗法巡回群（ $1$ の $p$ 乗根の集合）として $G_T$ を定める。

このとき、 $a, b \in \mathbb{F}_p$ なる $a ,b$ に対して、写像 $e: G_1 \times G_2 \to G_T$ が以下を満たすことを双線形という。

$e(aP, bQ) = e(P, Q)^{ab}$

個人的に本記事を書く要因となったのが、ブロックチェーン系プロジェクトで着目される暗号技術P.22「正当性」における以下の数式。上記定義と表記が違ったので疑問に思って調べ始めた。なので本記事では下記数式が成立するところまでを追う。

$e(sH(m), Q) = e(H(m), sQ)$

ベクトル空間における線形性（その1）

本節は、双線形関数物理のかぎしっぽがベースになっている。

まず、復習として一変数関数に対する線形性を考える。これはベクトル空間 $V$ の $x, y \in V$ なる元に対して、写像 $\phi: V \to \mathbb{R}$ が以下を満たすことだった。

$\phi(x + y) = \phi(x) + \phi(y)$
$\phi(\alpha x) = \alpha \phi(x) , \alpha \in \mathbb{R}$

では、二変数ではどうなるか。ベクトル空間 $V$ の直積集合 $V \times V$ の元 $(x, y)$ に対して、写像 $\psi(x,y): V \times V \to \mathbb{R}$ が以下を満たすことを双線形という。

$\psi(\alpha x + \beta x, y) = \alpha \psi(x, y) + \beta \psi(x,y)$
$\psi(x, \alpha y + \beta y) = \alpha \psi(x, y) + \beta \psi(x,y)$

双線形関数物理のかぎしっぽ本文には、以下のように記載されているが、理解が及ばず腹落ちしなかった。

双線形関数は個々の変数に対して別々に線形性を持っていると言えそうです．これが双線形という名前の由来でもありますなるほど。確かにそう見える。

ベクトル空間における線形性（その2）

本節は、岸本研究室 - 双線形写像についてがベースとなっている。

上記議論では、理解が及ばなかったので、もう少しシンプルに考える。「ベクトル空間における線形性（その1）」の定義に比べて、式の数は多いが、以下で双線形を定義したほうがシンプルで、学習にあたっては、理解しやすかった。

双線形を定義する。ベクトル空間 $V$ を考え、 $x, x_1, x_2, y, y_1, y_2 \in V$ なる元を考える。このベクトル空間 $V$ に対して、 $f: V \times V \to \mathbb{R}$ なる写像 $f$ を定義する。また、 $c \in \mathbb{R}$ とする。このとき双線形は以下の性質を満たすことをいう。

$f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y)$
$f(cx, y) = c f(x, y)$
$f(x, y_1 + y_2) = f(x, y_1) + f(x, y_2)$
$f(x, cy) = c f(x, y)$

こちらのほうが「ベクトル空間における線形性（その1）」で引用した個々の変数に対して別々に線形性を持っているというのが理解しやすいと思う。

双線形の例

「例示は理解の試金石」ということで双線形を満たす写像 $f$ の具体例を考えてみる。

双線形な例

$f(x, y) = xy$

「ベクトル空間における線形性（その2）」で定義した4式を一つずつ確かめていく。

$f(x_1 + x_2, y) = (x_1 + x_2) y = x_1 y + x_2 y = f(x_1, y) + f(x_2, y)$
$f(cx, y) = (cx)y = c xy = c f(x, y)$
$f(x, y_1 + y_2) = x(y_1 + y_2) = x y_1 + x y_2 = f(x, y_1) + f(x, y_2)$
$f(x, cy) = x(cy) = c xy = c f(x, y)$

となり、すべて満たすので双線形。

双線形じゃない例²

$f(x, y) = x + y$

実は最初にこれを念頭に考えていた。パッと見、線形性持ってそうだし。でも双線形じゃない。 4式中の一番上の式で双線形を満たさないことを確認する。

となり、左辺と右辺が一致しない。

BLS署名における双線形

話をベクトル空間から乗法巡回群で考えているBLS署名の話に戻す。それにあたり「ベクトル空間における線形性（その2）」で登場した双線形性の定義を再掲する。

$f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y)$
$f(cx, y) = c f(x, y)$
$f(x, y_1 + y_2) = f(x, y_1) + f(x, y_2)$
$f(x, cy) = c f(x, y)$

これらはベクトル空間 $V$ と実数 $\mathbb{R}$ で考えていたので、乗法巡回群 $G_T$ と有限体 $\mathbb{F}_p$ で考え直す。Intro to Bilinear Mapsより双線形性の定義を引用すると、双線形性とは $e: G_1 \times G_2 \to G_T$ なる写像について、 $u \in G_1, v \in G_2, a, b \in \mathbb{Z}$ に対して、

$e(u^{a}, v^{b}) = e(u, v)^{ab}$

が成り立つことである。ただし、このとき $e$ は非退化である。また本式の表現方法にはIntro to Bilinear Mapsの7ページ目に書いてある以下の表記もある。

$\forall P \in G_1, \forall Q \in G_2, \forall a, b \in \mathbb{Z}$ に対して、

$e(aP, bQ) = e(P, Q)^{ab}$

いきなり上式が出てくると、ベクトル空間から乗法巡回群への議論で少し飛んでしまっているように感じられるので補足する。

4式のうち、上2式について対応を示す。³

$f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y) \tag{1}$
$f(cx, y) = c f(x, y) \tag{2}$

式(2)から示す。 $e(aP, bQ) = e(P, Q)^{ab}$ において、 $a = c, b = 1$ とすると

$e(cP, Q) = e(P, Q)^{c}$

と表現できる。ここで $e(P, Q) \in G_T$ で $G_T$ が乗法巡回群であることを考えると自然な表記であろう。

次に式(1)を示す。 $P \in G_1$ で $G_1$ が加法巡回群であることを考えると

$e(P_1 + P_2, Q) = e(P_1, Q)e(P_2, Q)$

となることを示せればよい。ここで $P_1, P_2$ は $G_1$ の元であることから生成元 $P$ を用いて、

$P_1 = a_1 P$
$P_2 = a_2 P$

と表現できる。ここで $a_1, a_2 \in \mathbb{Z}$ である。これらを用いると

が得られる。

ここまでの議論は整数 $\mathbb{Z}$ 上のものだったが、有限体 $\mathbb{F}_p$ 上でも成り立つとして、

$\forall P \in G_1, \forall Q \in G_2, \forall a, b \in \mathbb{F}_p$ に対して、

$e(aP, bQ) = e(P, Q)^{ab}$

である。ここから $a, b$ が可換であることがわかるが、もう少し詳細に書いておく。

$c \in \mathbb{F}_p$ に対して、 $a = c, b = 1$ とすると

$e(cP, Q) = e(P, Q)^{c}$

である。同様に $a = 1, b = c$ とすると

$e(P, cQ) = e(P, Q)^{c}$

である。これらを合わせると

$e(cP, Q) = e(P, cQ)$

が得られる。これを使うとブロックチェーン系プロジェクトで着目される暗号技術のP.22では、以下の変形が成り立つことがわかる。

$e(sH(m), Q) = e(H(m), sQ)$

References

自分が理解しやすいように記号を変えているので出典元と異なる箇所がある↩
改行を含む数式にpreタグを使った。markdownでも&がエスケープされないようにならないかなー↩
$y$ については同様なので省略↩

2019-02-18

Raspberry Pi 3 Model b+でビットコインフルノードを構築する

背景

フルノードの重要性とLightning NetworkやProof of Stakeがノード運営インセンティブに与える影響 - YouTube やフルノードの重要性とフルノードが広がった世界について改めて考える - ビットコインダンジョン2.0 を読んで（見て）、ビットコインフルノードを立てたくなりました。
とはいえ以前、下記記事を書いたときに一度ノードを立てたことはあったので、二度目の構築です。

cipepser.hatenablog.com

前回はMacBook Pro上で構築したためストレージ容量を節約したかったので、当時の構築メモの通り、pruneモードで構築しました。
今回はフルノードです。 My first impressions of the Casa Bitcoin Node – The Startup – Medium のようにCasaもありかなぁと思ったいたのですが、Casaのホームページを見たら2019年2月7日時点で出荷に1ヶ月掛かるとありました。

1ヶ月は待てなかったので、Casaは諦め¹、以下のRaspberry Pi 3 Model b+²を購入しました。

ABOX Raspberry Pi 3 Model b+ ラズベリーパイ 3 b＋【2018新型】 MicroSDHCカード32G/NOOBSシステムプリインストール/カードリーダ /5V/3A スイッチ付電源/高品質HDMIケーブルライン/ヒートシンク /簡単に取り付けケース /日本語取扱説明書

出版社/メーカー: ABOX
メディア: Personal Computers
この商品を含むブログを見る

なお、HDD、モニタ、キーボード、マウスは家にあったものを流用したので、今回発生した費用は本セットの約1万円でした。

開封の儀

届いたやつです。開封し、基盤を取り出します。 f:id:cipepser:20190212175033j:plain f:id:cipepser:20190212175045j:plain

付属のmicroSDカードを挿します。

f:id:cipepser:20190212175057j:plain

BluetoothマウスのUSBを取り付けます。

f:id:cipepser:20190212175110j:plain

HDMIケーブルを挿します。

f:id:cipepser:20190212175124j:plain

外付けHDD（USBケーブル）を挿します。

f:id:cipepser:20190212175138j:plain

電源ケーブルを挿し、スイッチを入れます。

f:id:cipepser:20190212175150j:plain

今回のキットにはSDカードにOSが入っているので、Raspbianをインストールしました。

f:id:cipepser:20190212175205j:plain

キーボードはBluetoothキーボードしか持っていなかったので、ここでやっとペアリングです。

f:id:cipepser:20190212175227j:plain

Wi-Fiの設定も上図の赤い☓のところからいけます。

Bitcoin Coreのインストール

構築には、ラズパイでビットコインフルノードを動かしてみる(2017年） – Crypto Developer Blogを参考にさせていただきました。 2019年になりBitcoin Coreのバージョンも上がっており、コマンドが異なる部分もあるので、自分でやった手順を残します。³

まず、SWAP領域を拡張します。

# /etc/dphys-swapfile
CONF_SWAPSIZE=1000

# termitanl
$ sudo dphys-swapfile setup
$ sudo dphys-swapfile swapon

apt-getを最新の状態にします。

# termitanl
$ sudo apt-get update
$ sudo apt-get upgrade -y

ツール群をインストールします。

# termitanl
$ sudo apt-get install autoconf libevent-dev libtool libssl-dev libboost-all-dev libminiupnpc-dev -y
$ sudo apt-get install git -y
$ sudo apt-get install qt4-dev-tools libprotobuf-dev protobuf-compiler libqrencode-dev -y

Bitcoin Coreをインストールします。本記事時点で最新の0.17をインストールします。

# termitanl
$ mkdir ~/bin
$ cd ~/bin
$ git clone -b 0.17 https://github.com/bitcoin/bitcoin.git
$ cd bitcoin/
$ ./autogen.sh
$ ./configure --enable-upnp-default --disable-wallet
$ make -j2 # ここがとても長い
$ sudo make install

HDDのマウント

HDDの容量はどれくらいがいいのか見積もっておきましょう。ブロックチェーンサイズは、Blockchain Size - Blockchainで確認できます。グラフを引用すると以下のようになります。

f:id:cipepser:20190212174022p:plain

2019年2月10日現在で200GBを超えたくらいですね。ここ4年ほどは概ね線形にサイズが増加しており、約50GB/年くらいのスピードです。フルノードで運用することを考えると500GBくらいあれば5年くらいは大丈夫そうですね。

かなりバッファを見て（手元にあったHDDなだけ）1TBのHDDでマウントします。手順やハマった記録は以下記事参照。

cipepser.hatenablog.com

Bitcoin Coreの設定

マウント先に/volumes/BTC/blocksを作り、ここにデータを格納することにします。⁴

bitcoin.confに設定を書き込みます。どこにbitcoin.confを配置すべきかというと、Running Bitcoin - Bitcoin Wiki に以下のように書いてあるので、/volumes/BTC/blocksに配置します。

By default, Bitcoin (or bitcoind) will look for a file named 'bitcoin.conf' in the bitcoin data directory

デフォルトでは、bitcoinデータを格納するフォルダにあるbitcoin.confを見に行く

設定した内容は以下の通りです。

# bitcoin.conf
rpcuser=bitcoinrpc
rpcpassword=<PASSWORD>

# ~/.bashrc (追記分のみ)
PATH="$PATH:/home/pi/bin/bitcoin/src"
alias bitcoin-cli='bitcoin-cli -datadir=/volumes/BTC/blocks'

ラズパイでビットコインフルノードを動かしてみる(2017年） – Crypto Developer Blog のように設定すると、bashが~/.profileを読みにいってくれないので、~/.bashrcに集約しています。本当はaliasとか.bash_aliasesに書くべきかもしれないですが、どうせフルノード専用機にするので管理箇所を集約することにしました。

Bitcoin Coreの起動

以下で起動します。

# termitanl
$ bitcoind -datadir=/volumes/BTC/blocks -daemon

バックグラウンドで実行されているので同期がされていることをCLIで確認します。 v0.16.0でgetinfoは削除されてしまったので、getblockchaininfoを確認しましょう。

# termitanl
pi@raspberrypi:~ $ bitcoin-cli getblockchaininfo
{
  "chain": "main",
  "blocks": 181901,
  "headers": 563103,
  "bestblockhash": "000000000000075b5e5ee7573921a3b48e45ace6d9020af7777f32fd99737f14",
  "difficulty": 1591074.961847305,
  "mediantime": 1338165561,
  "verificationprogress": 0.009423622364504645,
  "initialblockdownload": true,
  "chainwork": "000000000000000000000000000000000000000000000012406bed1889e1f934",
  "size_on_disk": 1702373506,
  "pruned": false,
  "softforks": [
    {
      "id": "bip34",
      "version": 2,
      "reject": {
        "status": false
      }
    },
    {
      "id": "bip66",
      "version": 3,
      "reject": {
        "status": false
      }
    },
    {
      "id": "bip65",
      "version": 4,
      "reject": {
        "status": false
      }
    }
  ],
  "bip9_softforks": {
    "csv": {
      "status": "defined",
      "startTime": 1462060800,
      "timeout": 1493596800,
      "since": 0
    },
    "segwit": {
      "status": "defined",
      "startTime": 1479168000,
      "timeout": 1510704000,
      "since": 0
    }
  },
  "warnings": ""
}

blocksとheadersが一致したら同期完了です。

最新ブロックが「いつマイニングされたものなのか」を確認するなら、debug.logを見たほうがわかりやすいです。

$ tail -f /volumes/BTC/blocks/debug.log
2019-02-15T21:31:40Z UpdateTip: new best=000000000000000009bfca5a27f95c6212923139b0f43888d8581f49b3542fd4 height=338070 version=0x00000002 log2_work=81.95771 tx=56124782 date='2015-01-08T16:27:25Z' progress=0.150469 cache=497.6MiB(4300081txo)
2019-02-15T21:31:43Z UpdateTip: new best=00000000000000001177c70e7b05f9790c645202b6714b8dce38a10c1ddd9b0e height=338071 version=0x00000002 log2_work=81.957763 tx=56126029 date='2015-01-08T16:32:46Z' progress=0.150472 cache=497.6MiB(4300049txo)

同期開始（bitcoindの起動）は2019/02/15 12:20頃です。ルータで通信量を確認したところ、1日経過時点で40GB程度（その他の通信も込み）だったので、一週間くらい掛かりそうですね。。。気長に待ちます。

（2019/4/10追記） wimaxの3日10GB制限あり、かつ、途中で同期を停止していたタイミングもあったので参考になるかわかりませんが、4/10早朝にprogressが1となりました。制限ありの状況で2ヶ月くらい生活するとネットすら見れずかなりつらい日々でした。固定回線で同期しましょう。。。

References

自前で構築する分、こちらのほうが安い。需給もあると思いますが。↩
SDカードだけ違う安いショップもあったのですが、レビューでACアダプタの電圧が足りないようなレビューが多かったので割高でもこちらにしました。バッテリーが少ないようなエラーも出ないのでよかったです。↩
大きな流れは変わりません。2019年でも手順変わってないよくらいの感じで見てもらえるとうれしいです。↩
blocksの中にblocksディレクトリができてしまったので、別の名前のほうがよかった。反省。↩

2019-02-13

【Raspberry Pi】マウントするファイルシステムを間違えて起動できなくなった

ラズパイを買ったので RaspberryPi 3 にUSBの外付けHDD（NTFSフォーマット）を接続する - min117の日記を参考に、外付けHDDをマウントしたところ、ntfs-3gをインストール後rebootしたらラズパイの起動ができなくなりました。ファイルシステムに明るくないため、手こずりましたが、無事復旧したのでログを残します。

環境情報

Raspberry Pi 3 Model b+

pi@raspberrypi:~ $ lsb_release -a
No LSB modules are available.
Distributor ID:   Raspbian
Description:  Raspbian GNU/Linux 9.6 (stretch)
Release:  9.6
Codename: stretch

発生事象

etc/fstabに以下を追記後、再起動したら起動できなくなりました。

# etc/fstab
UUID="<MY UUID>"  /volumes/  ntfs-3g defaults,iocharset=utf8,umask=000 0 0

より具体的な事象は、raspi 3 が起動しなくなった。 - Raspberry Pi Forums と同じで、起動後、以下メッセージが出るもののctrl + DやEnterを押しても同メッセージが出続け、先に進めなくなりました。

You are in emergency mode, After loging in, type "jounalctl -xb"to view system logs,
"systemctl reboot" to rebott, "systemctl default" or ^D to try again to boot into defalult mode.

Cannot open access to console, the root account is locked. See sulongin(8) man page
for more details.

Press Enter to continue.

完全に/etc/fstabでファイルシステムの指定を間違えてしまい、起動できなくなってしまったパターンです。やらかしです。 /etc/fstabを戻そうにも起動すらできないので、Macで復旧します。

復旧

方針

幸い所有しているMacBook ProにSDカードスロットがあったので、VirtualBox上のUbuntuにSDカードを認識させる · Yoshi's Notesを参考にVirtualBoxでUbuntuを立ち上げて、/etc/fstabを編集できるようにします。

環境情報

# VirtualBox
バージョン 5.2.26 r128414 (Qt5.6.3)

SDカードを認識させるのにExtension Packが必要なので、Download VirtualBox (Old Builds)から自身のVirtualBoxのバージョンに合ったExtension Packをインストールします。なお、バージョンが異なるとインストールに失敗します。

UbuntuのOS情報は以下の通りです。

vagrant@vagrant-ubuntu-trusty-64:~$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=14.04
DISTRIB_CODENAME=trusty
DISTRIB_DESCRIPTION="Ubuntu 14.04.5 LTS"

復旧手順

Mac側

SDカードをMacに挿入します（MicroSDなので変換アダプタ使いました）。

Macからdiskutilを確認します。以下のように当環境では、SDカードは/dev/disk2で認識されていることが確認できます。

# Mac
❯ diskutil list
(中略)
/dev/disk2 (internal, physical):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:     FDisk_partition_scheme                        *31.9 GB    disk2
   1:             Windows_FAT_16 RECOVERY                1.7 GB     disk2s1
   2:                      Linux                         33.6 MB    disk2s5
   3:             Windows_FAT_32 boot                    72.4 MB    disk2s6
   4:                      Linux                         30.1 GB    disk2s7

mountコマンドでも確認したところ、/dev/disk2に関連するパーティションは以下の2つ(RECOVERYとboot)でした。

# Mac
❯ mount
(中略)
/dev/disk2s1 on /Volumes/RECOVERY (msdos, local, nodev, nosuid, noowners)
/dev/disk2s6 on /Volumes/boot (msdos, local, nodev, nosuid, noowners)

ディスクユーティリティからも以下のように確認できます。

f:id:cipepser:20190212161634p:plain f:id:cipepser:20190212161628p:plain

次にディスクユーティリティからRECOVERY/bootをマウント解除します。
（スクショを残し忘れましたが、上記2画面RECOVERY/bootの画面上部にマウント解除のボタンがあります）

続いて、VirtualBox vmdkファイルを作成し、権限を変更します。
（本当は777にしたくないですが、元記事と変えてハマるのも嫌なので、777で。。。）

# Mac
❯ sudo VBoxManage internalcommands createrawvmdk -filename ./sd-card.vmdk -rawdisk /dev/disk2
❯ sudo chmod 777 sd-card.vmdk
❯ sudo chmod 777 /dev/disk2

作成したvmdkファイルについて、VirtualBox上でハードディスクの追加を行います。

f:id:cipepser:20190212164933p:plain

既存のディスクを選択します。

f:id:cipepser:20190212164940p:plain

先ほど作成したsd-card.vmdkを開きます。

f:id:cipepser:20190212164945p:plain

ちなみにマウント解除したはずなんですが、少し時間を開けたら再度マウントされてしまっていて、以下のように失敗しました。

f:id:cipepser:20190212164811p:plain

慌てず、ディスクユーティリティから再度マウント解除すればOKです。

成功すると以下のようにsd-card.vmdkが認識されます。

f:id:cipepser:20190212165542p:plain

Ubuntu側

無事追加できたので、vagrant upしましょう。

参考までですが、一度以下のように起動に失敗しました。

❯ vagrant up
(中略)
==> default: Booting VM...
There was an error while executing `VBoxManage`, a CLI used by Vagrant
for controlling VirtualBox. The command and stderr is shown below.

Command: ["startvm", "84b91ede-c9fc-45bb-a45a-1f2dfbddee39", "--type", "headless"]

Stderr: VBoxManage: error: VD: error VERR_RESOURCE_BUSY opening image file '/Users/xxx/sd-card.vmdk' (VERR_RESOURCE_BUSY).
VBoxManage: error: Failed to open image '/Users/xxx/sd-card.vmdk' in read-write mode (VERR_RESOURCE_BUSY).
VBoxManage: error: AHCI: Failed to attach drive to Port1 (VERR_RESOURCE_BUSY)
VBoxManage: error: Details: code NS_ERROR_FAILURE (0x80004005), component ConsoleWrap, interface IConsole

こちらもRECOVERY/bootがMacにマウントされてしまっていることが原因なので、ディスクユーティリティから再度マウント解除すればOKです。

さて、vagrant sshしてからlsblkを実行し、Ubuntu上でSDカードが認識できたことを確認します。

vagrant@vagrant-ubuntu-trusty-64:~$ lsblk
NAME   MAJ:MIN RM   SIZE RO TYPE MOUNTPOINT
sda      8:0    0    40G  0 disk
└─sda1   8:1    0    40G  0 part /
sdb      8:16   0  29.7G  0 disk
├─sdb1   8:17   0   1.6G  0 part
├─sdb2   8:18   0     1K  0 part
├─sdb5   8:21   0    32M  0 part
├─sdb6   8:22   0    69M  0 part
└─sdb7   8:23   0  28.1G  0 part

sdbとして認識できていますね。これをマウントしていきます。ラズパイ上では何も考えずにntfs-3gにマウントしようとして失敗したので、今回はちゃんとファイルシステムのTYPEを確認します。

vagrant@vagrant-ubuntu-trusty-64:/volumes$ sudo blkid
/dev/sda1: LABEL="cloudimg-rootfs" UUID="xxx" TYPE="ext4"
/dev/sdb1: LABEL="RECOVERY" UUID="xxx" TYPE="vfat"
/dev/sdb5: LABEL="SETTINGS" UUID="xxx" TYPE="ext4"
/dev/sdb6: LABEL="boot" UUID="xxx" TYPE="vfat"
/dev/sdb7: LABEL="root" UUID="xxx" TYPE="ext4"

今回のゴールは「/etc/fstabを編集すること」なので、LABELがrootになっている/dev/sdb7を見ます。 TYPEはext4なので、ext4として/volumes/sdcard7にマウントします。
（/volumes/sdcard7が存在しないと思うので、事前にmkdirしておいてください）

vagrant@vagrant-ubuntu-trusty-64:/volumes$ sudo mount -t ext4 /dev/sdb7 /volumes/sdcard7

無事マウントできました。
今回のゴールであるetc/fstabが編集できます。以下記述を削除しましょう。

UUID="<MY UUID>"  /volumes/  ntfs-3g defaults,iocharset=utf8,umask=000 0 0

この状態でSDカードをラズパイに挿し、起動したら復旧しました。

`etc/fstab`を正しく設定する

復旧できたので正しい設定をしましょう。
先ほど同じようにラズパイ上でsudo blkidしてファイルシステムのTYPEを確認します。

$ sudo blkid
/dev/sda1: UUID="<MY UUID>" TYPE="vfat" PARTUUID="xxx"

vfatなので、ntfs-3gではなくvfatでマウントします。

# etc/fstab
UUID="<MY UUID>"  /volumes/  vfat defaults,iocharset=utf8,umask=000 0 0

これで再起動すれば、途中で止まることなく起動でき、/volumes/BTC/に外付けHDDがマウントされているはずです。

References

2019-02-04

haskell-ide-engineで ld: symbol(s) not found for architecture x86_64 のエラーが出る

vscode と haskell-ide-engine で Haskell 開発環境を構築する - Qiita をもとに環境構築を進めていたところ以下のエラーが出て、haskell-ide-engineをmakeすることができませんでした。

❯ make hie-8.6.3

(中略)

cabal-install-2.4.1.0: configure
Completed 19 action(s).

--  While building package cabal-install-2.4.1.0 using:
      /Users/cipepser/.stack/programs/x86_64-osx/ghc-8.6.3/bin/ghc --make -odir /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup -hidir /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup -i -i. -clear-package-db -global-package-db -package-db=/Users/cipepser/.stack/snapshots/x86_64-osx/nightly-2018-12-31/8.6.3/pkgdb -package-db=/Users/cipepser/hie/haskell-ide-engine/.stack-work/install/x86_64-osx/nightly-2018-12-31/8.6.3/pkgdb -hide-all-packages -package-id=Cabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D -package-id=base-4.12.0.0 -package-id=filepath-1.4.2.1 -package-id=process-1.6.3.0 -optP-include -optP/private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/setup_macros.h /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/Setup.hs /Users/cipepser/.stack/setup-exe-src/setup-shim-mPHDZzAJ.hs -main-is StackSetupShim.mainOverride -o /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/setup -threaded
    Process exited with code: ExitFailure 1
    Logs have been written to: /Users/cipepser/hie/haskell-ide-engine/.stack-work/logs/cabal-install-2.4.1.0.log

    [1 of 2] Compiling Main             ( /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/Setup.hs, /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/Main.o )
    [2 of 2] Compiling StackSetupShim   ( /Users/cipepser/.stack/setup-exe-src/setup-shim-mPHDZzAJ.hs, /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/StackSetupShim.o )
    Linking /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/setup ...
    clang-7: warning: argument unused during compilation: '-nopie' [-Wunused-command-line-argument]
    clang-7: warning: argument unused during compilation: '-nopie' [-Wunused-command-line-argument]
    ld: warning: ignoring file /Users/cipepser/.stack/snapshots/x86_64-osx/nightly-2018-12-31/8.6.3/lib/x86_64-osx-ghc-8.6.3/Cabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D/libHSCabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D.a, file was built for archive which is not the architecture being linked (x86_64): /Users/cipepser/.stack/snapshots/x86_64-osx/nightly-2018-12-31/8.6.3/lib/x86_64-osx-ghc-8.6.3/Cabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D/libHSCabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D.a
    Undefined symbols for architecture x86_64:
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_replDistPref_closure", referenced from:
          _s8sM_info in StackSetupShim.o
          _u8AR_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_replVerbosity_closure", referenced from:
          _s8sZ_info in StackSetupShim.o
          _u8AT_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziBuild_initialBuildSteps_closure", referenced from:
          _c8y6_info in StackSetupShim.o
          _u8AV_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimple_defaultMainWithHooks_closure", referenced from:
          _s7o5_info in Main.o
          _s7o5_closure in Main.o
          _c8DE_info in StackSetupShim.o
          _u8EF_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziUserHooks_replHook_closure", referenced from:
          _c8xN_info in StackSetupShim.o
          _c8y1_info in StackSetupShim.o
          _u8AW_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimple_simpleUserHooks_closure", referenced from:
          _s7qo_info in Main.o
          _u7FE_srt in Main.o
          _c8xN_info in StackSetupShim.o
          _c8y1_info in StackSetupShim.o
          _s8u9_info in StackSetupShim.o
          _u8AW_srt in StackSetupShim.o
          _u8EE_srt in StackSetupShim.o
          ...
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_buildVerbosity_closure", referenced from:
          _s7p9_info in Main.o
          _u7Fs_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziUtils_installOrdinaryFiles_closure", referenced from:
          _r3TL_info in Main.o
          _r3TL_closure in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_copyVerbosity_closure", referenced from:
          _s7pN_info in Main.o
          _u7Fv_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_copyDest_closure", referenced from:
          _s7q1_info in Main.o
          _u7Fx_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziLocalBuildInfo_absoluteInstallDirs_closure", referenced from:
          _s7nU_info in Main.o
          _u7wv_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziUtils_notice_closure", referenced from:
          _s7pm_info in Main.o
          _u7Fj_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziInstallDirs_NoCopyDest_closure", referenced from:
          _s7qn_info in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziTypesziHookedBuildInfo_emptyHookedBuildInfo_closure", referenced from:
          _s8tV_info in StackSetupShim.o
          _u8EB_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziUserHooks_UserHooks_con_info", referenced from:
          _c7xB_info in Main.o
          _c8DN_info in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_installVerbosity_closure", referenced from:
          _s7ql_info in Main.o
          _u7FA_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziInstallDirs_mandir_closure", referenced from:
          _s7nV_info in Main.o
          _u7ww_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziFlag_fromFlag_closure", referenced from:
          _s7qk_info in Main.o
          _s7q0_info in Main.o
          _s7pM_info in Main.o
          _s7p8_info in Main.o
          _u7Fr_srt in Main.o
          _s8t0_info in StackSetupShim.o
          _s8sN_info in StackSetupShim.o
          ...
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziTypesziLocalBuildInfo_buildDir_closure", referenced from:
          _s7nY_info in Main.o
          _s7pb_info in Main.o
          _s7pe_info in Main.o
          _u7wz_srt in Main.o
          _u7Fo_srt in Main.o
    ld: symbol(s) not found for architecture x86_64
    clang-7: error: linker command failed with exit code 1 (use -v to see invocation)
    `clang' failed in phase `Linker'. (Exit code: 1)
make: *** [cabal] Error 1

2019年1月末時点で、同じようなエラーでissueがいくつも立てられて（特にOSXで......）います。ワークアラウンドも様々なようなので、今回は自分が解消した方法を残します。

環境、ビルド対象

OS

システムのバージョン:  macOS Mojave 10.14.3 (18D42)
カーネルのバージョン: Darwin 18.2.0

haskell-ide-engine

ビルド対象のcommit: d9bcbf28408da4c42e54cfd5014cfc1cce3ca993

なお、Makefile中で指定されているようにcabalのバージョンは2.4.1.0です。

brew

念のため。

❯ brew --version
Homebrew 2.0.0
Homebrew/homebrew-core (git revision 175af; last commit 2019-02-02)
Homebrew/homebrew-cask (git revision 05a81; last commit 2019-02-02)

解決策

Build failed on MacOS with clang link error(ghc 8.4.4) · Issue #1058 · haskell/haskell-ide-engineに書いてあるとおり、別プロジェクトでインストールしていたbinutilsが悪さをしていたようです。unlinkしたところ、うまくいきました。

※ issueではghc 8.4.4ですが、8.6.3でも同じ方法で解決しました。

❯ brew unlink binutils
Unlinking /usr/local/Cellar/binutils/2.31.1_2... 120 symlinks removed
❯ rm -rf ~/.stack
❯ stack clean --full

stack cleanはrmの先にやってもいいかもしれないです。この状態で、make hie-8.6.3したらエラーが解消され、以下のようにhieがインストールできました。

❯ hie --version
Version 0.5.0.0, Git revision d9bcbf28408da4c42e54cfd5014cfc1cce3ca993 (2394 commits) x86_64 ghc-8.6.3

なお、後続のmake build-doc-8.6.3も問題なくビルドできました。

その他

Makefileのどのコマンドで失敗していたか

cabal:
    stack install cabal-install
    cabal update
    cabal install Cabal-2.4.1.0 --with-compiler=$(GHC)
.PHONY: cabal

ここのstack install cabal-installで冒頭のエラーとなっていました。

他にも試してもうまくいかなかった方法たち

hie-install-memo.md

References

2019-01-24

Writing A Compiler In Goを読んだ

Writing A Compiler In Goを読みました。

本書は、Writing An Interpreter In Go（邦訳：Go言語でつくるインタプリタ）の続編で、前作で開発したプログラミング言語MonkeyのコンパイラとVirtual Machine(以下、VM)を実装する内容となっています。

本書を読む前に、2018年後半にGo言語でつくるインタプリタを読み始めました。 Lexer、Parserを実装し、抽象構文木ASTを構築して、evalする流れを、自分の手でなぞり、ちゃんと動いたときには「Monkeyちゃん」と呼び出すほどに愛着が湧いていました。

これまで「すごそうだけどよくわからない」「いつか挑戦してみたい」と思っていた言語実装を一から自分の手でできたことに感動を覚え、「Lexerは他にも使えそうだな」と、12月にはGo2 Advent Calendar 2018 - Qiitaにて以下のようにProtocol Buffersのデコーダを書いていました。

cipepser.hatenablog.com

そんな折、続編である本書Writing A Compiler In Goの存在を知りました。 Turing Complete FMがとても好きなpodcastなのですが、2018年のセキュリティ・キャンプのCコンパイラを自作してみよう！でも多数の方がコンパイラを実装していて、本当にみんなすごいなぁと憧れを抱いていました。本書は、C言語ではないですが、コンパイラを実装できたことはとても嬉しかったです。

また、本書は現時点で邦訳が出ていません。個人的に初めて洋書を一冊完走することができた本にもなりました。初めての洋書でしたが、思いの外すらすらと読み進めることができました。理由としては以下がよかったです。

一文一文が短いので、どこを読んでいるのか迷子にならない
シンプルな言い回しなので、文意がわかる
わからなくてもコードを見れば何を言っているのかわかる
やたら文章のテンションが高く、勢いがある
「このテストは失敗して当然なんだ」のような応援が心強い

ちなみに、読むのにどれくらい時間が掛かるのか計測したところ26時間11分でした。実装中にtypoでハマったりしたので参考ですが。

f:id:cipepser:20190120123326p:plain

また、インタプリタと合わせて書いたコードの量は9289行でした。本書そのものがコメント（ドキュメント？）みたいなもので、コード中にはコメントがないので、処理そのものの行数だと考えると、気づけば結構書いたんだなぁと感慨深くもあります。

各章の所感

概要とメモベースで各章の所感を書きます。

第1章 Compilers & Virtual Machines

コンパイラ、VMとは何なのか、本書で実装するものが何なのかの説明。コードがなく（例示のみあり）、ひたすら説明。

初めての洋書だったこともあり、本章が一番つらかったかもしれない。

第2章 Hello Bytecode!

バイトコードとは何か。どうやって表現し、実装するかの概要説明。

スタックを実装して、OpCodeをVMに解釈させて実行させるまでを行う。 JVMなど聞いたことはあったVMやバイトコード、OpCodeがどういうものなのか、自分の手で実装することで掴めたのは大きかった。

第3章 Compiling Expressions

式をコンパイルする章。

まず中置式として四則演算のOpCodeから始まり、Booleanや比較演算子、前置式などを実装する。同じことを繰り返しやっていくので、よくわからなくても進めていくうちに前のほうもわかるようになる。繰り返し大事。

True/False/Nullをグローバルオブジェクトとして実装すると比較が楽（こうしないとrefrect.DeeqEqualを使うことになる）のも、勉強になった。

第4章 Conditionals

条件式をバイトコードで表現する。

条件が真のときとそうでないときで、スタックの飛ぶ先をJUMP命令として実装する。これがあのJUMP命令か！と謎の感動があった。

第5章 Keeping Track of Names

Identifier、もとい名前がついた変数や関数をバイトコードでどうやって表現するか

変数名を数字で置き換えることは知っていたが、実際に実装したことあるかないかは違うと思う。この章時点ではグローバル変数のみ実装。7章でScopeが実装される。

第6章 String, Array and Hash

章題の通り、String、Array、Hashを実装する。

同じような内容の繰り返しなので、復習を兼ねてサクサク進む。IndexをArrayとHashで同一の実装にできるのが気持ちいい。

第7章 Functions

おそらく本書の山場。関数や関数呼び出しを実装する。

個人的にはこの章が一番おもしろかったけど、同時に一番頭を使った。テストを一行一行追いかけて、スタック上がどうなっているか考えると理解できると思う。一番エッジケースを考慮しないといけないものこの章だったと思う。

関数内でローカル変数を実装するため、Scopeを定義する。関数の引数もローカル変数と同じように実装できるのがよい。 VMのほうではScopeと同様の概念をFrameと呼んでいた。

第8章 Built-in Functions

前作で登場した組み込み関数を実装する。

7章のScopeを組み込み関数用に特別に用意する。特に詰まることもなく進んだ。

第9章 Closures

クロージャを実装する。

7章でScopeの実装をしていたので、その延長ではあるものの自由変数の実装は興味深かかった。グローバル変数ではなく自由変数を扱うために、前章までで関数をOpConstantでスタックに積んでいたが、 OpClosureを使って、関数と一緒に自由変数もスタックに積む。これでうまく動くのかと懐疑的な気持ちだったが、テストが通る。すごい。

第10章 Taking Time

9章まででは関数を再帰で書けないので軽く修正を加える。

最後に、前作のevaluator v.s. vm (with compile)でベンチマーク。フィボナッチ数列の計算ベースで3倍程度速くなった。

Goコンパイラ本読了。
Goインタプリタ本で作ったevaluatorからコンパイルすることでフィボナッチ数列の計算ベースで3倍速くなった。 pic.twitter.com/J4PzdMg0Ju
— さいぺ (@cipepser) 2019年1月19日

最後に

思いは、本記事の序盤で語ってしまったので、多くは語りませんが、同じよう気持ちを持っている人には強く勧めます。もちろん最適化や実装方法にも別の方式があるなど、本書の範囲外となっていることも多数あります。（本書でも最適化よりわかりやすさ、学習を優先すると述べられている）しかし、入門書としてとても素晴らしい本だと思います。

なお、LexerやParserは、前作から引き続き利用するので、Go言語でつくるインタプリタから読むべきです。前作から合わせるとクロージャや第一級オブジェクト、リテラルなどイマイチ掴めていなかった概念を、実装することで理解を深めることができました。

あとTDD（Table Driven Tests）を実践できるのも、Goのプラクティスを知る上で役立つと思います。ただ、テストパターンはTypoで詰まると結構ハマる（1つのTypoで2時間くらい溶かしたりした）ので、コピペがおすすめです。（たぶんめんどくさくなるのもある）

本書は、Writing A Compiler In Go | Thorsten Ballで買えますが、eBookで買うとePub (iBook), Mobi (Kindle), PDF and HTMLで読めるのもよかったです。

References

Go言語でつくるインタプリタ

作者:Thorsten Ball
発売日: 2018/06/16
メディア: 単行本（ソフトカバー）

2018-12-11

165行で実装するProtocol Buffersデコーダ（ミニマム版）

この記事は Go2 Advent Calendar 2018の11日目の記事です。

今年の後半くらいに Protocol Buffers の仕様を読み始めたら、とてもシンプルかつコンパクトな仕様なのにcompatibilityへの考慮が凄まじくて、2018年後半に書いた記事の大半がProtocol Buffersに関するものでした。仕様とバイナリを睨めっこしていたら、自分でもバイナリをデコードしたくなったので、実装してみました。

本内容は、あくまでProtocol Buffersの勉強を目的としたもので、仕様には完璧に添っていません。というか、わかりやすさ（と実装のしやすさ）を優先して、コンパクトな仕様のさらにミニマム版な内容となっています。当然ですが、実運用する際にはofficialの実装を利用してください。

どこまで実装するか

上述の通り、ミニマム版として、以下を実装範囲とします。

バイナリからGoの構造体へUnmarshalする
Unmarshalする構造体は既知とする
wire typeは、値によって長さが変化する wire type 0(Varint)とwire type 2(Length-delimited)を対象とする

Length-delimitedやVarintは後ほど説明するので、今は一旦飛ばしてOKです。

3.について、後述のLexerは、他のwire typeにも適用できるように設計してるので、長さが固定なことに注意すれば実装可能です。Future Workです。

ミニマム版ですが、Protocol Buffersでも最初にハマるVarintも含めているので、Protocol Buffersよくわからないという方にも、お伝えできることがあるんじゃないかと思います。 Varintの仕様がわかっていると値は127以下にするのが望ましい（バイナリが短くなる）とかも理解できるのうれしいです。

バイナリの生成

まずはofficalのエンコーダでバイナリを生成していきましょう。正しく生成されたバイナリをデコードすることで、もとの構造体が復元できることを目標にします。

まず、すべての大元になる.protoファイルを以下のように定義します。
Person型にNameとAgeのフィールドをもたせています。 wire type 2(Length-delimited)を表現したかったので、stringとint32のままでよさそうなNameとAgeをwrapしています。（NameをFirstNameとLastNameとかにしたくなるかもしれないし......）

syntax = "proto3";

package person;

message Person {
  Name name = 1;
  Age age = 2;
}

message Name {
  string value = 1;
}

message Age {
  int32 value = 1;
}

protocして、上記.protoファイルに対応したライブラリ.pb.goをgenerateします。

❯ protoc -I=./ --go_out=./ person.proto

以下表の値を設定したバイナリを生成します。

フィールド	値
Name	Alice
Age	20

package main

import (
    "io/ioutil"
    "log"

    pb "github.com/cipepser/protobufDecoder/Person"
    "github.com/golang/protobuf/proto"
)

func main() {
    p := &pb.Person{
        Name: &pb.Name{
            Value: "Alice",
        },
        Age: &pb.Age{
            Value: 20,
        },
    }

    if err := write("./person/alice.bin", p); err != nil {
        log.Fatal(err)
    }
}

func write(file string, p *pb.Person) error {
    out, err := proto.Marshal(p)
    if err != nil {
        return err
    }

    if err := ioutil.WriteFile(file, out, 0644); err != nil {
        return err
    }

    return nil
}

生成したperson/alice.binを適当なバイナリエディタで見てみると以下のようになります。なお、vimなら:%!xxdで見れます。 hexdump person/alice.binをターミナル上で実行するのでもよいと思います。

0a07 0a05 416c 6963 6512 0208 14         ....Alice....

この時点で、バイナリではあるものの暗号化されているわけではない（Aliceが見えている）ので、ちょっと安心感を覚えます。

Protocol Buffersのバイナリの読み方

さて、実装を始める前にProtocol Buffersのバイナリがどのようなフォーマットなのか説明します。
Protocol Buffers のエンコーディング仕様の解説でも述べられているように以下が基本です。

key = タグナンバー * 8 + タイプ値

タグナンバーは.protoで定義した値です。例えば、今回のAge age = 2;であれば、2がタグナンバーです。

タイプ値は、メッセージタイプを表す値で、公式ドキュメントにwire typesとして、以下のように定義されています。冒頭からLength-delimitedやVarintと言っていたやつです。

Type	Meaning	Used For
0	Varint	int32, int64, uint32, uint64, sint32, sint64, bool, enum
1	64-bit	fixed64, sfixed64, double
2	Length-delimited	string, bytes, embedded messages, packed repeated fields
3	Start group	groups (deprecated)
4	End group	groups (deprecated)
5	32-bit	fixed32, sfixed32, float

これだけだとよくわからないと思うので、例として、上で生成したバイナリをデコードしていきましょう。
改めて生成したバイナリを記載します。

0a 07 0a 05 41 6c 69 63 65 12 02 08 14

わかりやすいように色分けしました。

f:id:cipepser:20181208001319p:plain

一つずつ読んでいきます。

まず初めの0x0aは、
0d10 = タグname(1) * 8 + Length-delimited(type 2)
であることからタグナンバーとタイプ値がわかります。
※Nameは自身で定義したmessageなので、表中のembedded messageが該当し、Length-delimitedとなります。
Length-delimited(type 2)だったので、lengthを得るために続く0x07を読みます。これがタグname(1)のlengthとなるので、後続の7バイト0a 05 41 6c 69 63 65をNameとしてデコードします。

Name(赤色の7バイト)の初め0x0aは、
0d10 = タグvalue(1) * 8 + Length-delimited(type 2)
です。
Length-delimited(type 2)だったので、lengthを得るために続く0x05を読みます。これがタグvalue(1)のlengthとなるので、後続の5バイト41 6c 69 63 65をstringとして読んでいきます。この5バイトをASCIIとして読むと41 6c 69 63 65はAliceとなります。

いい感じです。この調子で残りの12 02 08 14も読んでいきましょう。

0x12は、
0d18 = タグage(2) * 8 + Length-delimited(type 2)
です。
またまた、Length-delimited(type 2)だったので、lengthを得るために続く0x02を読みます。これがタグage(2)のlengthとなるので、後続の2バイト08 14をAgeとしてデコードします。

0x08は、
0d08 = タグvalue(1) * 8 + Varint(type 0)
です。
やっとVarint(type 0)が登場しましたね。 Varint(type 0)はちょっとトリッキーなので、このあとすぐ説明します。値が128未満であれば、そのままデコードしてあげることができるので、今回の例では0x14をint32として読んで0x14 = 0d20が得られます。

以上から、もともと定義したAliceと20をデコードできました。

フィールド	値
Name	Alice
Age	20

Varintの仕様について

Varint(type 0)について、もう少し詳しく見ていきます。値が128未満であれば、そのままデコードできると述べたので、128以上の値として131としてみましょう。(128だと1が立つbitが一つしかないのでもう少しわかりやすく131にしました)

上記例で最後にVarintとして読み込んだ08 14（緑色の箇所）を思い出しましょう。

0x08 = 0d08 = タグvalue(1) * 8 + Varint(type 0)
からVarint(type 0)であることがわかり、 0x14をint32としてデコードし、0d20を得ました。

.protoのAge: 20,をAge: 131,に変更してバイナリを生成し直してみます。コードは上述と同じなので省略しますが、実行して得られるバイナリは、08 83 01となります。

先頭1バイトは変わらず0x08なので、value(tag 1),Varint(type 0)となるので83をVarintとして読み込みます。

ここで0x83を2進数で表記すると0b1000 0011です。
Varintでは、先頭1bitが1のとき、次の1バイトに数値が続いていることを表します。
次の1バイトを読み込むと0x01 = 0b0000 0001となり、先頭1bitが0となったため、読み込みはここで終了です。

あとは0x83と0x01を組み合わせてint32にデコードしてあげればいいのですが、仕様に以下のように書かれているので、リトルエンディアンで読んでいく必要があります。

varints store numbers with the least significant group first

また、先頭1bitは無視することにも注意です。

Varintの値
= 0x01(0b0000 0001)から先頭1bit落としたもの ++ 0x83(0b1000 0011)から先頭1bit落としたもの // リトルエンディアンなので0x01が先
= 000 0001 ++ 000 0011
= 0b1000 0011 // 先頭の6bitは0なので省略
= 0d131

以上より、131にデコードできます。

※++演算子はバイナリを結合する操作を表します。

実装

バイナリの読み方がわかったところで実装に入っていきます。

Lexer

バイナリを読む部分を実装します。ちょうど最近、Go言語でつくるインタプリタを読んでいるので、こちらの実装を大きく参考にさせて頂いています。

まず、Lexerを以下のように定義します。バイナリのバイト列bを1バイトずつ読んでいくため、現在の位置positionと次のバイトの位置readPositionを保持します。

type Lexer struct {
    b            []byte
    position     int
    readPosition int
}

コンストラクタはバイト列inputを受け取って*Lexerを返します。

func New(input []byte) *Lexer {
    l := &Lexer{b: input}
    l.readPosition = l.position + 1
    return l
}

以下は補助的な役割を果たすメソッドですが、実装しておくと便利です。バイト列がまだ読み込めるかをhasNext()で判断します。また、next()で1バイト先に進められるようにします。

func (l *Lexer) hasNext() bool {
    return l.readPosition < len(l.b)
}

func (l *Lexer) next() {
    l.position++
    l.readPosition = l.position + 1
}

readCurByte()は現在の位置の1バイトを読み込み、位置を1つ進めます。 Varintを読み込む際はこちらを使います。

func (l *Lexer) readCurByte() byte {
    b := l.b[l.position]
    l.next()
    return b
}

readBytes(n int)はreadCurByte()のn文字版です。 Length-delimitedを読み込む際に利用します。
今回は省略しましたが、hasNext()でEOFの判定を入れたほうがいいですね。

func (l *Lexer) readBytes(n int) []byte {
    bs := l.b[l.position : l.position+n]
    for i := 0; i < n; i++ {
        l.next()
    }
    return bs
}

Varintのデコード

Varintのデコーダを実装します。
readCurByte()で1バイト読んできて、先頭1bitが1である限り(0になるまで)、1バイトずつ読み込みます。先頭1bitは数値としてデコードする際には不要なので、0x7fとANDで論理積を取ります。また、リトルエンディアンとしてデコードする必要があるので、スタックに積んでおきます。スタックといいつつ、Goのcontainer/listはあんまり使われている印象がない（おそらくsliceのほうが速い？）ので、 bsの[]byteにappendすることにしました。
あとは先頭1bitを取り除いて、++で結合してあげればよいので、7bitほど左シフトさせて足しこんでいきます。

func (l *Lexer) decodeVarint() (uint64, error) {
    if len(l.b) == l.position {
        return 0, errors.New("unexpected EOF")
    }

    var bs []byte
    b := l.readCurByte()
    for bits.LeadingZeros8(b) == 0 { // 最上位bitが1のとき
        bs = append(bs, b&0x7f)
        b = l.readCurByte()
    }

    // 最上位bitが0のとき = 最後の1byte
    x := uint64(b)
    for i := 0; i < len(bs); i++ {
        x = x<<7 + uint64(bs[len(bs)-1-i])
    }

    return x, nil
}

Unmarshalの実装

Person、Name、Ageそれぞれについて、Unmarshalの実装します。どの型も流れは共通で、以下の流れになります。

1バイト読み込み、タグナンバーtagとタイプ値wireを計算する
wireごとに後続の何バイト読み込むかがわかるので、その数だけ読み込む
読み込んだ値をtagに応じて評価する

1.のtagとwireの計算は、

key = タグナンバー * 8 + タイプ値

であることを思い出すと、以下のように実装できます。

tag := key >> 3       // 下位4bit目以上を抜き出す
wire := int(key) & 7  // 下位3bitのみ抜き出す

`tag`を`0`にしたとき

コラム的な話になりますが、tagを0になるようなバイナリを与えると以下のようにpanicします。

panic: proto: person.Person: illegal tag 0 (wire type 2)

逆に0でないtagではpanic（どころかエラーにもならない）になりません。今回の例でいうとPerson型はtagが1、2しか定義していませんが、tagが3になるようなバイナリを読み込ませてもエラーにはなりません。これはcompatibilityを考慮してのことで、tagが3となるフィールドが増えた際に、 tagが2までしかない古い.protoしか知らないクライアントでもエラーが起きないようにするためだと思われます。
今回の例（tagが1と2しかない状態）で、tagが3になるようにバイナリを作り、デコードすると、そのフィールドはnilになります。

panicさせる動作については、table_unmarshal.goに以下のように書かれています。

Explicitly disallow tag 0. This will ensure we flag an error when decoding a buffer of all zeros. Without this code, we would decode and skip an all-zero buffer of even length. [0 0] is [tag=0/wiretype=varint varint-encoded-0].

PersonのUnmarshal

今回の.protoで定義したPersonは以下のような構造体となります。

type Person struct {
    Name *Name // tag: 1
    Age  *Age  // tag: 2
}

このPerson型に対してUnmarshalを実装します。今回Person型には、Length-delimited(type 2)になるフィールドしかないため、wireが意味を持つのはcase 2のときのみです。 tagはName(1)とAge(2)があるので、場合分けします。

func (p *Person) Unmarshal(b []byte) error {
    l := New(b)
    for l.hasNext() {
        key := uint64(l.readCurByte())
        tag := key >> 3
        wire := int(key) & 7

        switch wire {
        case 2:
            length := int(l.readCurByte())
            v := l.readBytes(length)

            switch tag {
            case 0:
                return errors.New("illegal tag 0")
            case 1:
                p.Name = &Name{}
                if err := p.Name.Unmarshal(v); err != nil {
                    return err
                }
            case 2:
                p.Age = &Age{}
                if err := p.Age.Unmarshal(v); err != nil {
                    return err
                }
            }
        default: // Person型はwire type 2以外は存在しない
            return fmt.Errorf("unexpected wire type: %d", wire)
        }
    }

    return nil
}

NameのUnmarshal

Personと同じように.protoで定義したNameは以下のような構造体となります。

type Name struct {
    Value string // tag: 1
}

このName型に対してUnmarshalを実装します。今回Name型には、Length-delimited(type 2)になるフィールドしかないため、wireが意味を持つのはPersonと同じくcase 2のときのみです。 tagはValue(1)のみなので、読み込んだバイト列をstringとしてデコードします。

func (n *Name) Unmarshal(b []byte) error {
    l := New(b)
    for l.hasNext() {
        key := uint64(l.readCurByte())
        tag := key >> 3
        wire := int(key) & 7

        switch wire {
        case 2:
            length := int(l.readCurByte())
            v := l.readBytes(length)

            switch tag {
            case 0:
                return errors.New("illegal tag 0")
            case 1:
                n.Value = string(v)
            }
        default: // Name型はwire type 2以外は存在しない
            return fmt.Errorf("unexpected wire type: %d", wire)
        }

    }
    return nil
}

AgeのUnmarshal

Person、Nameと同じように.protoで定義したAgeは以下のような構造体となります。

type Age struct {
    Value int32 // tag: 1
}

このAge型に対してUnmarshalを実装します。今回Age型には、Varint(type 0)になるフィールドしかないため、wireが意味を持つのはcase 0のときのみです。 tagはValue(1)のみなので、読み込んだバイト列をdecodeVarint()でint32としてデコードします。

func (a *Age) Unmarshal(b []byte) error {
    l := New(b)

    for l.hasNext() {
        key := uint64(l.readCurByte())
        tag := key >> 3
        wire := int(key) & 7

        switch wire {
        case 0:
            switch tag {
            case 0:
                return errors.New("illegal tag 0")
            case 1:
                i, err := l.decodeVarint()
                if err != nil {
                    return err
                }
                a.Value = int32(i)
            }
        default: // Age型はwire type 1以外は存在しない
            return fmt.Errorf("unexpected wire type: %d", wire)
        }

    }
    return nil
}

以上でデコーダ本体の実装は完了です。お疲れ様でした。

テスト

最後にテストを書いていきます。今回の例で使ったバイナリ、ゼロ値(nil)になるパターン、マルチバイトになるVarintをテストパターンとします。

package decoder

import (
    "encoding/hex"
    "testing"

    "github.com/google/go-cmp/cmp"
)

func atob(s string) []byte {
    b, _ := hex.DecodeString(s)
    return b
}

func TestUnmarshalPerson(t *testing.T) {
    tests := []struct {
        b      []byte
        expect Person
    }{
        {
            // 今回の例
            b: atob("0a070a05416c69636512020814"),
            expect: Person{
                Name: &Name{Value: "Alice"},
                Age:  &Age{Value: 20},
            },
        },
        {
            // ゼロ値
            b:      atob(""),
            expect: Person{},
        },
        {
            // Ageのみゼロ値
            b: atob("0a070a05416c696365"),
            expect: Person{
                Name: &Name{Value: "Alice"},
            },
        },
        {
            // Nameのみゼロ値
            b: atob("12020814"),
            expect: Person{
                Age: &Age{Value: 20},
            },
        },
        {
            // Varintが2バイトになる場合
            b: atob("1203088301"),
            expect: Person{
                Age: &Age{Value: 131},
            },
        },
        {
            // Varintが3バイトになる場合
            b: atob("120408928002"),
            expect: Person{
                Age: &Age{Value: 32786},
            },
        },
    }

    for i, tt := range tests {
        p := Person{}
        if err := p.Unmarshal(tt.b); err != nil {
            t.Fatalf("test[%d - failed to Unmarshal. got err:%q", i, err)
        }
        if diff := cmp.Diff(p, tt.expect); diff != "" {
            t.Fatalf("test[%d - failed to Unmarshal. expected=%q, got=%q", i, tt.expect, p)
        }
    }
}

ちゃんとテストが通ります。

❯ go test ./decoder
ok      github.com/cipepser/protobufDecoder/decoder 0.006s

最後に

というわけで、Protocol Buffersのバイナリをデコードしてみました。全体を表示しても以下のように165行程度なのでだいぶコンパクトに実装できたと思います。

f:id:cipepser:20181209140919p:plain

今回はPerson、Name、AgeとそれぞれUnmarshalを実装しましたが、同じような処理になるのでコード生成したいですね。あと.protoからバイナリを生成するMarshalのほうとかも実装していきたいです。

ご指摘等あればtwitterまでご連絡ください。

References

Go言語でつくるインタプリタ

作者: Thorsten Ball,設樂洋爾
出版社/メーカー: オライリージャパン
発売日: 2018/06/16
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

2018-12-03

Rustでマルチインターフェースパケットキャプチャを実装する

この記事は Rust Advent Calendar 2018 の3日目の記事です。

本記事では、タイトルの通り、Rustでマルチインターフェースパケットキャプチャを実装します。今回の記事で達成したい目標は以下2点です。

Rustでネットワークプログラミングをしたい
マルチインターフェースにすることでマルチスレッド対応したい

どうやって低レイヤを扱うか

Rustでネットワークプログラミングを行うには、libpnetが便利なので、今回はこちらを利用します。libpnetを使えるようCargo.tomlには以下を記載しておきます。

[dependencies]
serde = "1.0"
serde_derive = "1.0"

[dependencies.pnet]
version = "0.21.0"

アーキテクチャ

今回実装するパケットキャプチャのアーキテクチャは以下です。

f:id:cipepser:20181202012641p:plain

I/F1からI/Fnの各インターフェース用のスレッドがrxを監視します。 rxで受信したパケットをqueueに渡します。 packet handlerは、queueにあるパケットを一つずつ処理（標準出力に表示）する役割を果たします。 tcpdumpなどでは対象や表示形式など引数を設定できますが、今回はL2-4までを対象として、表示対象を以下の通りとします。ARPは遊び心で加えました。

Layer	表示対象
L2	送信元MACアドレス
L2	宛先MACアドレス
L2-3	ARP request
L2-3	ARP reply
L3	送信元IPアドレス
L3	宛先IPアドレス
L4	送信元ポート番号
L4	宛先ポート番号

実装

パケットの実装

各パケットが どのインターフェースから着信したものか を保持するために、queueに渡すパケットを以下の構造体にまとめます。

#[derive(Clone, Debug)]
struct PacketWithInterface {
    interface: NetworkInterface,
    packet: Vec<u8>,
}

Queueの実装

各インターフェースのrxを監視する部分をマルチスレッドで実装します。各スレッドからqueueを共有できるようArcとMutexで包みます。

#[derive(Clone, Debug)]
struct Queue<T: Send> {
    inner: Arc<Mutex<VecDeque<T>>>,
}

上記Queueに対してnew、get、addを実装します。注意が必要なのはget、addを行う際にlockを取ってあげることくらいでしょうか。なお、lockを取った際に_queueで束縛しており、_queueがスコープから外れたタイミングで自動的にunlockされます。

impl<T: Send> Queue<T> {
    fn new() -> Self {
        Self { inner: Arc::new(Mutex::new(VecDeque::new())) }
    }

    fn get(&self) -> Option<T> {
        let _queue = self.inner.lock();
        if let Ok(mut queue) = _queue {
            queue.pop_front()
        } else {
            None
        }
    }

    fn add(&self, obj: T) -> usize {
        let _queue = self.inner.lock();
        if let Ok(mut queue) = _queue {
            queue.push_back(obj);
            queue.len()
        } else {
            0
        }
    }
}

packet handlerの実装

queueからパケットを取り出す部分はmain内で実装するので、ここでは取り出したパケットの処理することに注力します。基本的にはバイト列の先頭からL2 -> L3 -> L4と、各レイヤーのヘッダを確認し、該当するフィールドを表示する処理になります。なお、ARPパケットはEthernetヘッダに記載されているEtherTypeで判断できます。

fn handle_ethernet_frame(interface: &NetworkInterface, ethernet: &EthernetPacket) {
    println!(
        "{}: {} > {}",
        interface.name,
        ethernet.get_source(),
        ethernet.get_destination(),
    );

    print!("  {}: ", ethernet.get_ethertype());
    match ethernet.get_ethertype() {
        EtherTypes::Arp => {
            let arp = arp::ArpPacket::new(ethernet.payload()).unwrap();
            match arp.get_operation() {
                arp::ArpOperations::Reply => {
                    println!(
                        "ARP reply({}): {} -> {}",
                        arp.get_sender_proto_addr(),
                        arp.get_sender_hw_addr(),
                        arp.get_target_hw_addr()
                    );
                }
                arp::ArpOperations::Request => {
                    println!(
                        "ARP request({}): {} -> {}",
                        arp.get_target_proto_addr(),
                        arp.get_sender_hw_addr(),
                        arp.get_target_hw_addr()
                    );
                }
                _ => (),
            }
        }
        EtherTypes::Ipv4 => {
            let ip = Ipv4Packet::new(ethernet.payload()).unwrap();
            println!("{} -> {}", ip.get_source(), ip.get_destination());
            handle_ip_packet(&interface, &ip)
        }
        _ => (),
    }
}

fn handle_ip_packet(interface: &NetworkInterface, ip: &Ipv4Packet) {
    print!("    {}: ", ip.get_next_level_protocol());
    match ip.get_next_level_protocol() {
        IpNextHeaderProtocols::Tcp => {
            let tcp = tcp::TcpPacket::new(ip.payload()).unwrap();
            handle_tcp_packet(&interface, &tcp);
        }
        IpNextHeaderProtocols::Udp => {
            let udp = udp::UdpPacket::new(ip.payload()).unwrap();
            handle_udp_packet(&interface, &udp);
        }
        _ => (),
    }
}

fn handle_tcp_packet(_interface: &NetworkInterface, tcp: &tcp::TcpPacket) {
    println!("{} -> {}", tcp.get_source(), tcp.get_destination());
}

fn handle_udp_packet(_interface: &NetworkInterface, udp: &udp::UdpPacket) {
    println!("{} -> {}", udp.get_source(), udp.get_destination());
}

mainの実装

インターフェースを初期化

キャプチャ対象とするインターフェースをここで指定します。 configファイルから読み取る実装もしてみましたが、今回は簡単のためmainにべた書きとしました。

let interface_names: HashSet<&str> = vec!["RT2_veth0", "RT2_veth1"]
    .into_iter()
    .collect();

let interfaces: Vec<NetworkInterface> = datalink::interfaces()
    .into_iter()
    .filter(|interface: &NetworkInterface| interface_names.contains(interface.name.as_str()))
    .collect();

パケットを受信する

各インターフェースのrxを取得して、ループでrxを監視します。そしてrxで受信したパケットをqueueに投げ込みます。
今回の実装でqueueに投げ込む部分が一番ハマりました。 rx.next()で受信できるパケットは&[u8]なので参照を渡そうとすると、spawnで作ったクロージャより長生きできず全然コンパイルが通りませんでした。

let mut handles: Vec<_> = interfaces.into_iter()
    .map(|interface| {
        let queue = queue.clone();
        thread::spawn(move || {
            let mut rx = datalink::channel(&interface, Default::default())
                .map(|chan| match chan {
                    Ethernet(_, rx) => rx,
                    _ => panic!("could not initialize datalink channel {:?}", interface.name),
                }).unwrap();

            loop {
                match rx.next() {
                    Ok(src) => {
                        queue.add(PacketWithInterface {
                            interface: interface.clone(),
                            packet: src.to_owned(),
                        });
                    }
                    Err(_) => {
                        continue;
                    }
                }
            }
        })
    }
    )
    .collect();

パケットを処理する

queueからパケットを取り出し、EthernetPacketにmatchした後、handle_ethernet_frameに渡します。渡した後は上述のpacket handlerの責務です。異常パケットを受信した場合はパケットをドロップし、無視します。異常パケット1つ受信しただけでpanicしてプロセスごと落ちない設計としました。

handles.push(thread::spawn(move || {
    loop {
        let queue = queue.clone();
        match queue.get() {
            Some(packet_with_interface) => {
                let _packet = packet_with_interface.packet.deref();
                match EthernetPacket::new(_packet) {
                    Some(packet) => {
                        handle_ethernet_frame(&packet_with_interface.interface, &packet);
                    },
                    _ => {
                        continue;
                    }
                }
            },
            _ => {
                continue;
            }
        }
    }
}));

実際に動かしてみる

環境

検証用の環境は以下の通りです。

$ uname -a
Linux vagrant-ubuntu-trusty-64 3.13.0-161-generic #211-Ubuntu SMP Wed Oct 3 14:52:35 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

ネットワーク構築

netnsで以下のネットワークを用意します。構築スクリプトはこちら。

RT2の★マークの箇所RT2_veth0とRT2_veth1がパケットキャプチャの対象インターフェースです。

f:id:cipepser:20181202011833p:plain

pingを打ったときのパケットキャプチャ

hostの192.168.0.1からRT1の192.168.1.254へpingを打ってみます。

# host
$ ping 192.168.1.254 -c 1
PING 192.168.1.254 (192.168.1.254) 56(84) bytes of data.
64 bytes from 192.168.1.254: icmp_seq=1 ttl=63 time=0.706 ms

--- 192.168.1.254 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 0.706/0.706/0.706/0.000 ms

このときのパケットキャプチャは以下のようになりました。

# RT2
$ sudo ./target/debug/pcap
RT2_veth1: d6:c7:d0:99:8e:bc > ff:ff:ff:ff:ff:ff
  Arp: ARP request(192.168.1.254): d6:c7:d0:99:8e:bc -> 00:00:00:00:00:00
RT2_veth1: f6:63:73:99:cc:cd > d6:c7:d0:99:8e:bc
  Arp: ARP reply(192.168.1.254): f6:63:73:99:cc:cd -> d6:c7:d0:99:8e:bc
RT2_veth1: d6:c7:d0:99:8e:bc > f6:63:73:99:cc:cd
  Ipv4: 192.168.0.1 -> 192.168.1.254
    Icmp: RT2_veth1: f6:63:73:99:cc:cd > d6:c7:d0:99:8e:bc
  Ipv4: 192.168.1.254 -> 192.168.0.1
    Icmp: RT2_veth1: f6:63:73:99:cc:cd > d6:c7:d0:99:8e:bc

最初はまったく通信がないので、ARPによってIPアドレスからMACアドレスの解決を行っています。その後、192.168.0.1から192.168.1.254へのICMP通信が発生し、その応答が返ってきていることがわかります。

TCP通信を発生させたときのパケットキャプチャ

RT1で以下のように1234ポートでリッスンしておきます。

# RT1
$ nc -l -p 1234

hostの192.168.0.1からRT1の192.168.1.254:1234へ接続します。

# host
$ nc 192.168.1.254 1234

このときのパケットキャプチャは以下のようになりました。

# RT2
RT2_veth1: d6:c7:d0:99:8e:bc > f6:63:73:99:cc:cd
  Ipv4: 192.168.0.1 -> 192.168.1.254
    Tcp: 45693 -> 1234
RT2_veth1: f6:63:73:99:cc:cd > d6:c7:d0:99:8e:bc
  Ipv4: 192.168.1.254 -> 192.168.0.1
    Tcp: 1234 -> 45693
RT2_veth1: d6:c7:d0:99:8e:bc > f6:63:73:99:cc:cd
  Ipv4: 192.168.0.1 -> 192.168.1.254
    Tcp: 45693 -> 1234

正しくキャプチャできていますね。 45693は送信元なのでhighポートがOSによって割り当てられています。また、3つ目のパケットから、ncコマンドでリッスンしていると応答がないのでTCPの再送が行われていることがわかります。

最後に

以上、Rustによるマルチインターフェースパケットキャプチャでした。本文中でも述べましたがlifetimeですごいハマりました。少しずつRustを勉強していますが、まだまだですね。今回みたいになにか作っているといろいろハマって理解が深まるので前向きにがんばります。

ご指摘等あればtwitterまでご連絡ください。

双線形とは何なのか

ベクトル空間における線形性（その1）

ベクトル空間における線形性（その2）

双線形の例

双線形な例

双線形じゃない例2

BLS署名における双線形

References

背景

開封の儀

Bitcoin Coreのインストール

HDDのマウント

Bitcoin Coreの設定

Bitcoin Coreの起動

References

環境情報

発生事象

復旧

方針

環境情報

復旧手順

Mac側

Ubuntu側

etc/fstabを正しく設定する

References

環境、ビルド対象

OS

haskell-ide-engine

解決策

その他

Makefileのどのコマンドで失敗していたか

他にも試してもうまくいかなかった方法たち

References

各章の所感

第1章 Compilers & Virtual Machines

第2章 Hello Bytecode!

第3章 Compiling Expressions

第4章 Conditionals

第5章 Keeping Track of Names

第6章 String, Array and Hash

第7章 Functions

第8章 Built-in Functions

第9章 Closures

第10章 Taking Time

最後に

References

どこまで実装するか

バイナリの生成

Protocol Buffersのバイナリの読み方

Varintの仕様について

実装

Lexer

Varintのデコード

Unmarshalの実装

tagを0にしたとき

PersonのUnmarshal

NameのUnmarshal

AgeのUnmarshal

テスト

最後に

References

どうやって低レイヤを扱うか

実装

パケットの実装

Queueの実装

packet handlerの実装

mainの実装

インターフェースを初期化

パケットを受信する

パケットを処理する

実際に動かしてみる

環境

ネットワーク構築

pingを打ったときのパケットキャプチャ

TCP通信を発生させたときのパケットキャプチャ

最後に

References

双線形じゃない例²

`etc/fstab`を正しく設定する

`tag`を`0`にしたとき