OpenFlowのメッセージをAttoparsecで解析する

2016-05-15 / [network] [haskell] [openflow]

はじめに

最近OpenFlowをもう一度見直すべきではないか、という念がふつふつと湧いてきており、OpenFlowのメッセージのエンコード/デコードを行うプログラムをHaskellで書こうとしています。

この記事ではそのデコードに必要な解析器(parser)を作る上でのポイントをメモしておきます。

先に結論

実際にparserを書いてみて解ったことは下記のとおり。

1. 固定長フィールドは素直にAttoparsecのAPIを使えば解析できる

2. 可変長フィールドを解析するためには、事前に動的に変わるフィールドの長さを解析する

3. 可変長フィールドの中身は前もってまとめてByteStringとして読み込む

4. 読み込んだByteStringを使って一度parserを実行する

残った疑問は下記のとおり。

???: parserの中でparserを実行する以外にこの要求を実現する方法はないのだろうか?

parser内でサブのparserを実行するというデザインに違和感を抱えた形になりました。まだこれの代替デザインは見つかっていません。

OpenFlowのメッセージ用parserの特徴

OpenFlowのフレームフォーマットは、固定長フィールド+可変長フィールドで構成されています。 JSONのように{}や[]など識別子を頼りに字句解析をするのではなく、フィールドの長さを頼りにデータを解析する必要があります。

市井のHaskellベースのparserを見ていると、フィールドの長さをベースにデータ解析をおこなう例があまり見当たりません(あってもWebSocket)。多くの場合HTTPやJSON, SMTP, LDAPなどテキストから識別子を解析するプロトコルの実装です。固定長フィールド+可変長フィールドのフレーム解析はニーズが少ないせいか見かけません。

そうした固定長フィールド+可変長フィールドのフレーム解析にAttoparsecを使ってみて得られた、要点や注意点をお伝えできればと思います。

JavaのネットワークライブラリであるNettyにはこういうかゆいところに手が届くAPIがあるんですよね。Nettyの成熟っぷりが凄まじい。

ゴール

OpenFlowのEchoRequestメッセージの解析をゴールとします。

ここで示すコードではたまたまOpenFlowを使うだけで、あまりOpenFlowの機能や特徴に突っ込んだことは書きません。TLV形式のフレームフォーマットを見たことがある方ならご理解いただけると思います。

OpenFlowのハンドシェークシーケンスでは通常Helloメッセージの送受信が先にくるのですが、Helloはいつの間にか複雑になっていたので、ここでは書かないことにしました。

OpenFlow

OpenFlowはネットワークパケットが持つ様々なヘッダ情報をもとに「フロー」として分類し、フロー単位にスイッチングを行うOpenFlowスイッチを制御するためのプロトコルです。OpenFlowスイッチを制御するためのアプリケーションをOpenFlowコントローラと呼びます。

ここで想定しているのはOpenFlow1.3です。

フレームフォーマット

解析するのに最低限必要なOpenFlowのフォーマットを記します。ごく簡単なメッセージを例にとるので、さほど理解に苦しむことはない（はず）です。

理解に苦しむところがあったら私の記述のせいなのでむしろご指摘ください。。。。

OpenFlowヘッダ

すべてのOpenFlowプロトコルのデータについてくるヘッダです。

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| version (8)   | type (8)      | length (16)                   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| xid (32)                                                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

このヘッダでは「OpenFlowのどのバージョンのプロトコルか」や「そのあとにどんな種類のメッセージが続くか」を示します。

version : OpenFlowプロトコルのバージョン

type : OpenFlowヘッダのあとに続くペイロードの種類 (Hello, EchoRequest, FlowMod etc.)

length : OpenFlowヘッダそのものも含めたフレーム長

xid : トランザクションID

今回はtypeフィールドは常にEchoRequest(2)を指すと考えてください。

これをデータ型として定義すると下記のようになるでしょう。

data OpenFlow
  = OpenFlow
  { _version :: Word8
  , _type    :: Word8
  , _length  :: Word16
  , _xid     :: Word32
  }

レコードのフィールド名に_がついているのは、予約語や関数名の衝突を避けるためです。

EchoRequestメッセージ

EchoRequestはOpenFlowを喋るホスト同士での死活監視に利用されます。

OpenFlowヘッダのあとに任意の長さのデータが続くのが特徴です。

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| version (8)   | type (8)      | length (16)                   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| xid (32)                                                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| arbitary-length data field                                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

arbitary-length data fieldがそのデータに相当します。このデータがOpenFlowのメッセージEchoRequest特有のフィールドになります。

EchoRequestをヘッダに格納するためにOpenFlowのデータ型をもう少し拡張します。

data OpenFlow
  = OpenFlow
  { _version :: Word8
  , _type    :: Word8
  , _length  :: Word16
  , _xid     :: Word32
  , _payload :: OpenFlowPayload -- payloadをフィールドとして追加
  }

-- payloadそのものの定義
data OpenFlowPayload
  = EchoRequest { _data :: ByteString }

データ型の定義ができました。バイナリーデータからこのデータ構造を出力するparser(解析器)を定義します。

解析の進め方

前述のデータ構造OpenFlowを出力するparserを定義していきます。

ここではHaskellのAttoparsecというライブラリを使います。

A fast parser combinator library, aimed particularly at dealing efficiently with network protocols and complicated text/binary file formats

とあるとおりネットワークプロトコルの解析に威力を発揮します。

固定長フィールドの解析

先頭から固定長のフィールドを読んでいくのはとても簡単です。 AttoparsecのParserを素直に使えばいいだけです。

version_ <- anyWord8
type_    <- anyWord8
length_  <- anyWord16
xid_     <- anyWord32
-- anyWord16とanyWord32は標準ではついていないので適当に自作します

こうすると到着したフレームの先頭から順次固定長フィールドを取り出すことができます。

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| version (8)   | type (8)      | length (16)                   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| xid (32)                                                      | ← ここまでは読み込めました
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

この時点で残っているフィールドは可変長データのみになります。

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| arbitary-length data field                                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

可変長フィールドの解析

ここは今までのように単純なparserを組み合わせるだけではダメそうです。読み込むフィールドの長さが、今まで解析した結果に依存するからです。

読み込むフィールドの長さは事前に読み込んだlengthから計算できます。 lengthはOpenFlowヘッダを含んだフレームの長さです。

length = OpenFlowヘッダ長(8) + ペイロードのデータ長

いま知りたいのはフレームからOpenFlowヘッダを除いた残りの部分のデータ長です。

ペイロードのデータ長 = length - OpenFlowヘッダ長(8)

なのでlength - 8が残りのフィールドの長さになります。これをHaskellで書くとこんな感じです。NオクテットのデータをByteStringとして読み込むtakeを使います。

payloadBytes <- take (length_ - 8)

あとはこのペイロードを解析すればいいだけです。

可変長データ用parserを実行する

上記の手順まで進むと、解決すべき残りの課題は

手元にある payloadBytes :: ByteString のみを使ってペイロードをparseする

になります。

これを満たす関数は

parseOnly :: Parser a -> ByteString -> Either String a

でしょう。つまり一度parserの内部で別のparserを実行する必要があるのです。

ペイロード用のparser

ここでペイロードとはEchoRequestに付随する可変データ長フィールドです。

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| arbitary-length data field                                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

任意の長さのデータを取り出してEchoRequestのペイロードとするため下記のような定義になります。

payloadParser :: Parser OpenFlowPayload
payloadParser = EchoRequest <$> takeByteString

takeByteStringは残りのデータをByteStringとして読み込むparserです。

ヘッダのparserとペイロードのparserを組み合わせる

いままでのコードと合わせるとこんな感じになります。

-- 固定長フィールドはそのまま読み込む
version_     <- anyWord8
type_        <- anyWord8
length_      <- anyWord16
xid_         <- anyWord32

-- 可変長フィールドを含んだデータを切り出す
payloadBytes <- take (length - 8)

-- 1. 読み込んだpayloadBytesをもとにpayloadParserを実行する
case parseOnly (payloadParser <* endOfInput) payloadBytes of

  -- 2. Either String a が返却されるので中身を取り出す
  --   3. 失敗した場合はエラーメッセージをParserの失敗として呼び出し元に知らせる
  Left err     -> fail err

  --   4. 成功した場合はそのデータを持つParserとして返却
  Right payload -> return $ OpenFlow version_ type_ length_ xid_ payload

payload :: ByteStringとpayload解析用のpayloadParserをparseOnlyに渡す
返却されるEither String aをパターンマッチで剥がして結果を取り出す
Leftによってエラーメッセージが返される場合は、それをparserの失敗とする
Rightによってpayloadの解析値が返される場合は、それを使ってOpenFlowデータを構築する

残った違和感

これで固定長フィールド+可変長フィールドのデータを解析することができます。

ポイントは下記の通りです。

事前に可変長フィールドの長さを解析・算出する
長さをもとに一度ByteStringを取り出す
取り出したByteStringを使っていったんparserを実行する

そして書いてみて解ったことがあります。

このparserはちょっとスマートでない

ような気がするということです。理想としていたparserの作り方とずれているのです。

理想のparserの作り方

理想のparserの作り方とは

parserを組み上げることに専念できる

ような方法です。 parserを実行する方法については後で考えればいいのです。今はparserを組み合わせることだけに集中したい。そんな時、他のことを考えるのはノイズなのです。

HaskellのParser combinatorの良さは小さなparserを組み合わせて大きなparserを作れることです。大きなparserを組み上げたら、あとは一回parserを実行すれば結果が得られます。

parserを組み合わせる
できあがったparserを実行する

parserを書いているときには1に集中すればいいわけです。そのparserをどう実行するかは1が終わってからじっくり考えてもいいのです。

それはとてもプログラマに優しい構成方法です。

現実に出来上がったparser

でも今回作ったparserはちょっと違いました。

parserを組み合わせる
一度parserを実行して途中の結果を取り出す
結果をもとにparserを組み上げる
出来上がったparserを実行する

2と3に余計なステップが入っています。私はparserを組んでいるだけのはずなのに、何故かparserの実行方法について途中で時間を費やす必要があるのです。これがノイズだと感じました。

私のparserの組み方が間違っているのではないか。 何度もそう考えたのですが、まだ他の方法が見つかっていません。

いやーでも型検査は通っているし、テストはパスしているしまあいっか（雑）ってなりました。

そもそもそんな違和感を気にするべきなのでしょうか？実は大した問題じゃないのかもしれませんが、今の私はなんだか気になっています。

何かヒントになる論文が無いか探してます。

まとめ

今回はネットワークから到着した固定長フィールド+可変長フィールドのフォーマットをもったOpenFlowメッセージをHaskellのAttoparsecで解析する方法について書いてみました。

解ったのは下記の4つのパターンです。