あどけない話

Internet technologies

Developing network related libraries in Haskell in 2022FY

Haskell http2 QUIC DNS

This article is my annual report of 2022FY(fiscal year in Japan; from April 2022 to March 2023). My mission in IIJ is contribute to standardizations of new network protocols by their implementations. As you may know, I maintain some network-related libraries in Haskell.

HTTP/2

Background: the http2 library originally provided HTTP/2 frame and HPACK encoder/decoder only. This was integrated into Warp to provide the HTTP/2 server functionality. This functionality was extracted into the server side in http2. Then the client side was implemented.

Version 3.0.x were released in 2021FY to fix the vulnerabilities reported in "HTTP/2 implementations do not robustly handle abnormal traffic and resource exhaustion".

Version 4.0.0

RFC 9113 was published in June 2022 and obsoleted RFC 7540. The main purpose of this version is to catch up this new RFC. The major version up was due to a lot of breaking changes.

Version 4.1.0

The server side has been tested well in the real world but the client side is not. Evgeny Poberezkin kindly reported some bugs relating to streaming in the client side. This version should fix these bugs. I thank him a lot.

The major version up again because the internal data type was changed resulting in the build break of http3. A new version of http3 to catch up this change was also released.

QUIC

Background: the quic/http3 library have been developed since 2019 and were released after RFC9000 was published in 2021.

Version 0.0.x adopts the fusion crypto engine for performance reasons. After releasing version 0.0.x, I noticed that it supports the Intel architecture only. I should have quickly worked around but my interest went to QUIC version 2 and the version negotiation. After implementing these new technologies, I had integrated the fusion and cryptonite to let run the quic library on all platforms.

At this moment, I had a dilemma: I cannot release a new version of quic since the numbers of QUIC version 2 and the trasnport parameter for the version negotiation would change. (The value of QUIC version 2 was 0x709a50c4 in drafts and is 0x6b3343cf finally. It's not 0x00000002 at all!)

Meanwhile, I spend time to support Windows. The UDP implementation of Windows is really awkward. See the following blog article for more information.

Based on this experience, I have released the network-udp library which provides best current practice for UDP clients and servers. (This library is also used in the dnsext-do53 library described later.)

Though RFCs of QUIC version 2 and the version negotiation have not been released, the numbers have been fixed. So, I released the quic library v0.1.0 finally in Feb 2023.

DNS

Background: to implement anti-spam technologies such as SPF and DKIM, I have started implementing the dns library purely in Haskell since 2010. Thanks to GHC's concurrency, the stub resolver functionality is highly concurrent. Fortunately this library is used widely but unfortunately two down-sides were turned out:

  1. Resource records are not extensible: resource records are implemented as a sum type. The third party library cannot extend them. The only way to extend them is to send a pull request to the dns library.
  2. Resource records are not friendly to caching: some resource records use ByteString internally. So, if they are cached for a long time, fragmentation happens.

dnsext

It appeared impossible to maintain backward compatibilities to the dns library. So, new libraries whose prefix is dnsext- were created.

  • dnsext-types: basic types with encoders/decoders. To solve 1), I introduced typeclasses. To fix 2), ShortByteString is used as an internal representation.

The following is the definition of extensible resource records:

class (Typeable a, Eq a, Show a) => ResourceData a where
    resourceDataType :: a -> TYPE
    putResourceData  :: CanonicalFlag -> a -> SPut ()

-- | A type to uniform 'ResourceData' 'a'.
data RData = forall a . (Typeable a, Eq a, Show a, ResourceData a) => RData a

A basic type Domain is defined using ShortByteString instead of ByteString:

data Domain = Domain {
    -- The representation format. Case-sensitive, escaped.
    representation  :: ShortByteString
    -- Labels in wire format. Case-sensitive, not escaped.
  , wireLabels      :: [ShortByteString]
  -- | Eq and Ord key for Canonical DNS Name Order.
  --   Lower cases, not escaped.
  --   https://datatracker.ietf.org/doc/html/rfc4034#section-6.1
  , canonicalLabels :: ~[ShortByteString]
  }
  • dnsext-do53: DNS over UDP port 53

The following is a typical usage of the stub resolver:

> withLookupConf defaultLookupConf $ \env -> lookupA env "www.iij.ad.jp"
Right [202.232.2.180]

My current interest is SVCB(Service Binding)/HTTPS resource records and DNS over new transport protocols.

  • dnsext-svcb: SVCB related resource records. This is an extension example of dnsext-types.
  • dnsext-dox: DNS over HTTP2, HTTP3, TLS and QUIC

After Kei Hibino joined to IIJ, he has focused implementing DNSSEC verifier and a full resolver.

  • dnsext-dnssec: DNSSEC verifier
  • dnsext-full-resolver: a full resolver (aka a cache server)

He wrote three articles on this topic in Japanese (article 1, article 2, article 3).

dnsext-full-resolver provides a command line interface called dug. It shows how iterative resolve works if the -i option is specified:

% dug -i www.iij.ad.jp
resolve-just: dc=0, ("www.iij.ad.jp.",A)
    "a.root-servers.net." ["198.41.0.4","2001:503:ba3e::2:30"]
    "b.root-servers.net." ["199.9.14.201","2001:500:200::b"]
    "c.root-servers.net." ["192.33.4.12","2001:500:2::c"]
        ...
iterative: selected addrs: (198.41.0.4,"jp.",A)
iterative: selected addrs: (2001:503:ba3e::2:30,"jp.",A)
iterative: selected addrs: (199.9.14.201,"jp.",A)
...
    "a.dns.jp." ["203.119.1.1","2001:dc4::1"]
    "b.dns.jp." ["202.12.30.131","2001:dc2::1"]
    "c.dns.jp." ["156.154.100.5","2001:502:ad09::5"]
        ...
iterative: selected addrs: (203.119.1.1,"ad.jp.",A)
iterative: selected addrs: (2001:dc4::1,"ad.jp.",A)
iterative: selected addrs: (202.12.30.131,"ad.jp.",A)
...
    "a.dns.jp." ["203.119.1.1","2001:dc4::1"]
    "b.dns.jp." ["202.12.30.131","2001:dc2::1"]
    "c.dns.jp." ["156.154.100.5","2001:502:ad09::5"]
        ...
iterative: selected addrs: (203.119.1.1,"iij.ad.jp.",A)
iterative: selected addrs: (2001:dc4::1,"iij.ad.jp.",A)
iterative: selected addrs: (202.12.30.131,"iij.ad.jp.",A)
...
    "dns0.iij.ad.jp." ["210.130.0.5","2001:240::105"]
    "dns1.iij.ad.jp." ["210.130.1.5","2001:240::115"]
iterative: selected addrs: (210.130.0.5,"www.iij.ad.jp.",A)
iterative: selected addrs: (2001:240::105,"www.iij.ad.jp.",A)
iterative: selected addrs: (210.130.1.5,"www.iij.ad.jp.",A)
...
    "dns0.iij.ad.jp." ["210.130.0.5","2001:240::105"]
    "dns1.iij.ad.jp." ["210.130.1.5","2001:240::115"]
resolve-just: selected addrs: (210.130.0.5,"www.iij.ad.jp.",A)
resolve-just: selected addrs: (2001:240::105,"www.iij.ad.jp.",A)
resolve-just: selected addrs: (210.130.1.5,"www.iij.ad.jp.",A)
resolve-just: selected addrs: (2001:240::115,"www.iij.ad.jp.",A)
--------------------
;; HEADER SECTION:
;Standard query, NoError, id: 8338
;Flags: Authoritative Answer


;; OPTIONAL PSEUDO SECTION:
;UDP: 1232, Data:[]

;; QUESTION SECTION:
;www.iij.ad.jp.     IN  A

;; ANSWER SECTION:
www.iij.ad.jp.  300(5 mins) IN  A   202.232.2.180

If the -d auto option is specified, dug first resolves SVCB RR and selects DNS over X according to its response.

% dug @94.140.14.140 -d auto www.iij.ad.jp
;; 2a10:50c0::2:ff#443/HTTP/3, Tx:42bytes, Rx:58bytes, 132usec

;; HEADER SECTION:
;Standard query, NoError, id: 43730
;Flags: Recursion Desired, Recursion Available

;; OPTIONAL PSEUDO SECTION:
;UDP: 0, Data:[]

;; QUESTION SECTION:
;www.iij.ad.jp.     IN  A

;; ANSWER SECTION:
www.iij.ad.jp.  300(5 mins) IN  A   202.232.2.180

We don't have a releasing plan at this moment. We should concentrate the field test of the full resolver in 2023FY.

atomicModifyIORef' の歴史

Haskell

Haskellの並行プログラミングの奥義であるatomicModifyIORef'の歴史。内容は予告なく修正される。

atomicModifyIORef'は「IORef」と「関数」を引数に取る。その関数は、IORefが現在指している「古い値」を受け取り、IORefが新たに指すべき「新しい値」と「帰り値」をタプルで返すように書く。

atomicModifyIORef' :: IORef a -> (a -> (a, b)) -> IO b

新しい値は、サンクが作られた時点で、古い値と不可分にスワップされ、その後評価される。評価は重くとも、サンクを作ることは軽いので、スワップは多くの場合成功する。

atomicModifyIORef の問題点

もうすっかり忘れていたが、Mightyの開発過程で、atomicModifyIORefがスペースリークをすることを発見し、解決策を2011年の Monad.Reader issue 19に執筆した。

以下は、時間の文字列を1秒に一回作ってキャッシュしておくコード：

atomicModifyIORef ref (\_ -> (tmstr, ()))

サンクが潰れずにスペースリークとなる。解決策として、以下を考案。

x <- atomicModifyIORef ref (\_ -> (tmstr, ()))
x ‘seq‘ return ()

これを Monad.Reader に書いた。その後、バンパターンを使うともっとカッコよく書けることが判明。

!_ <- atomicModifyIORef ref (\_ -> (tmstr, ()))

注意深くコードを読んだ人は疑問に思うだろう。タプルの右側の要素しか評価していないのに、どうして左側の新しい値に起因するスペースリークがなくなるか？

このコードでは、新しく作られる値のサンクを潰すことはできない。しかし、右の要素を評価することでタプルが生成される。すると、左側のサンクは、古い値を参照していないことが分かり、GCが回収できる。

このコードは、IORefが指す古い値と返り値を使わないので、現在では atomicWriteIORef が利用できる。

atomicModifyIORef' の登場

Monad.Reader issue 19をきっかけに、Joey Adams氏が atomicModifyIORef' を提案。以下は、2011年にマージされたAdd strict versions of modifyIORef and atomicModifyIORefより：

atomicModifyIORef' :: IORef a -> (a -> (a,b)) -> IO b
atomicModifyIORef' ref f = do
    b <- atomicModifyIORef ref
            (\x -> let (a, b) = f x
                    in (a, a `seq` b))
    b `seq` return b

baseライブラリ4.6.0以降で atomicModifyIORef'が利用可能となった。つまり、2012年にリリースされた GHC 7.6.1 から利用できる。

Simon Marlow氏が、2013年に発行されたParallel and Concurrent Programming in Haskell の284ページでこのパターンを紹介。atomicModifyIORef' 自体への言及はなし。2014年に発行されたHaskellによる並列・並行プログラミングの363ページでは、僕が atomicModifyIORef' に関する訳注を入れた。

参照はサンクが作られた時点でスワップされて、そのサンクは atomicModifyIORef'の終了後、以下のように評価される。

  • atomicModifyIORefの外側で b を返す前に、bをWHNFにしようとする
  • bを評価するには、内部で仕込まれたseqにより、aもWHNFになる
  • その後bがWHNFになる。

このころはプリミティブな命令として atomicModifyMutVar# があり、atomicModifyIORef は、そのラッパーだった。以下は不可分性はないが、atomicModifyIORef の動作をエミュレートした疑似コードである。

pseudoAtomicModifyIORef :: IORef a -> (a -> (a, b)) -> IO b
pseudoAtomicModifyIORef ref f = do
  x <- readIORef ref
  case f x of
    fx -> do  -- thunk 'fx'
      -- only CAS success case
      writeIORef ref $ fst fx -- thunk 'fst fx'
      putStrLn "swap"
      return $ snd fx -- thunk 'snd fx'

これを使い Joey Adams氏の実装をエミュレートする：

joey :: IORef a -> (a -> (a, b)) -> IO b
joey ref f = do
    b <- pseudoAtomicModifyIORef ref
            (\x -> let (a, b) = f x
                    in (a, a `seq` b))
    b `seq` return b

また、評価順序を知るために、たくさん trace 仕込んだ f を用意する：

f :: Int -> (Int, ())
f n = (trace "tupple" ((trace "new" n + 1), (trace "ret" ())))

GHCiで試してみよう。

> ref <-newIORef (0::Int)
> joey ref f
swap
tupple
new
ret

"new" よりも前に "swap" が表示されているのが分かる。

atomicModifyIORef' にどんなに正格な関数を与えても、サンクが先に IORef に格納されて、その後で新しい値が計算される。以下のような正格な関数を考える：

f' :: Int -> (Int, ())
f' n = let !n' = trace "new" n + 1 in (trace "tupple" (n', (trace "ret" ())))

使ってみよう。

> joey ref f'
swap
new
tupple
ret

"tupple" よりも "new" の方が早く生成されるが、それでも "swap" の後だと分かる。

性能向上

オリジナルの atomicModifyIORef' は、タプルでパターンマッチした後、新しいタプルを作成している。これは無駄である。parcs 氏は、セレクターサンクを使って性能を向上させること提案した。

atomicModifyIORef' ref f = do
    b <- atomicModifyIORef ref $ \a ->
            case f a of
                v@(a',_) -> a' `seq` v
    b `seq` return b

このコードはタプルを生成しない。case文はフィールドを取り出すために使われている。これは、セレクターサンクとなって、GCが高速に扱えるらしい。

しかし、本当にこの方法で、新しい値が評価される前にスワップされるのだろうか？ v を返す前に a' が評価されているように見える！

違う。違う。あなたの解釈は違うのだ。Joey Adams氏の実装は、タプルの遅延性を利用しているからうまくいくと思っているなら、違うのだ。atomicModifyMutVar# が遅延させるのは、関数(ラムダ式)全体であって、タプルの生成には頼っていない。

先ほど、正格な関数 f' を与えても、うまく動作していたことを思い出そう。

parcs氏の実装をエミュレートする：

parcs ref f = do
    b <- pseudoAtomicModifyIORef ref $ \a ->
            case f a of
                v@(a',_) -> a' `seq` v
    b `seq` return b

使ってみる。

> ref <-newIORef (0::Int)
> parcs ref f'
swap
new
tupple
ret

やはり、"swap" が最初に起きていることが分かる。

atomicModifyMutVar2#

David Feuer氏が、ghc proposals 0149を出し、atomicModifyIORefのスペースリークをなくすために、新たなプリミティブである atomicModifyMutVar2# の作成を提案した。

atomicModifyMutVar では、第一フィールドと第二フィールド両方にサンクを作成していた。atomicModifyMutVar2#では、第一フィールドだけにサンクを作る。第二フィールドは正格に評価されるので「サンクの割り当て直後に潰す」という無駄が生じない。

atomicModifyMutVar2# :: MutVar# s a -> (a -> c) -> State# s -> (# State# s, a, c #)

引数の関数の型から、タプルを仮定してないことが分かる。これを一般的なHaskellのコードから呼ぶための関数にするラッパーが、2つある。

atomicModifyIORef2Lazy :: IORef a -> (a -> (a,b)) -> IO (a, (a, b))
atomicModifyIORef2Lazy (IORef (STRef r#)) f =
  IO (\s -> case atomicModifyMutVar2# r# f s of
              (# s', old, res #) -> (# s', (old, res) #))

atomicModifyIORef2 :: IORef a -> (a -> (a,b)) -> IO (a, (a, b))
atomicModifyIORef2 ref f = do
  r@(_old, (_new, _res)) <- atomicModifyIORef2Lazy ref f
  return r

なぜ2つに分かれているのかは不明。現在のatomicModifyIORef'の実装はこう：

atomicModifyIORef' :: IORef a -> (a -> (a,b)) -> IO b
atomicModifyIORef' ref f = do
  (_old, (_new, !res)) <- atomicModifyIORef2 ref $
    \old -> case f old of
       r@(!_new, _res) -> r
  pure res

以下は、日比野さんが書いた検証コード：

pseudoModifyIORef2Lazy :: IORef a -> (a -> (a, b)) -> IO (a, (a, b))
pseudoModifyIORef2Lazy ref f = do
  x <- readIORef ref
  case f x of
    fx -> do
      -- only CAS success case
      writeIORef ref (fst fx)
      putStrLn "swap"
      return (x, fx)

pseudoModifyIORef2 :: IORef a -> (a -> (a,b)) -> IO (a, (a, b))
pseudoModifyIORef2 ref f = do
  r@(_old, (_new, _res)) <- pseudoModifyIORef2Lazy ref f
  return r

pseudoModifyIORef :: IORef a -> (a -> (a,b)) -> IO b
pseudoModifyIORef ref f = do
  (_old, ~(_new, res)) <- pseudoModifyIORef2 ref f
  pure res

david :: IORef a -> (a -> (a,b)) -> IO b
david ref f = do
    (_old, (_new, !res)) <- pseudoModifyIORef2 ref $
        \old -> case f old of
            r@(!_new, _res) -> r
    pure res

動作順序を調べてみる：

> ref <-newIORef (0::Int)
> david ref f'
swap
new
tupple
ret

"swap" が一番最初に出力されているのが分かる。

TLSの符号化

TLS

TLSのデータがどう符号化(シリアライズ)されるかのメモ。簡単にいうと可変長配列だけ先頭に「長さ」が付き、それ以外はそのまま。

基本型

たとえば、ProtocolVersionは uint16 と定義されている。

uint16 ProtocolVersion;

TLSのバージョン1.3の値は、0x0304であり、そのままネットワークバイトオーダー(ビッグエンディアン)で符号化される。

03 04 # TLS 1.3

固定長配列

固定長配列は、角括弧を使って表す。

たとえば、CipherSuiteが以下のように2バイトで定義されている。

uint8 CipherSuite[2];

TLS_AES_256_GCM_SHA384 は 0x1302 と定義されている。

13 02 # TLS_AES_256_GCM_SHA384

可変長配列

可変長配列は、小なり大なりで表す。小なり大なりの中に、長さの最大値が指定されるので、その分の長さを最初に付ける。

CipherSuiteの可変長配列が、後述の構造体の中で、以下のように定義されているとしよう。

CipherSuite cipher_suites<2..2^16-2>;

cipher_suitesはフィールド名である。216 とあるので、長さは2バイトだと分かる。

00 06 # 以下6バイト
13 02 # TLS_AES_256_GCM_SHA384
13 01 # TLS_AES_128_GCM_SHA256
13 03 # TLS_CHACHA20_POLY1305_SHA256

構造体

構造体は struct を使って表す。符号化は、単に上から順に書き出せばよい。

たとえば、ClinetHello は以下のように定義されている。

struct {
    ProtocolVersion legacy_version = 0x0303;    /* TLS v1.2 */
    Random random;
    opaque legacy_session_id<0..32>;
    CipherSuite cipher_suites<2..2^16-2>;
    opaque legacy_compression_methods<1..2^8-1>;
    Extension extensions<8..2^16-1>;
} ClientHello;

opaqueの定義はどこにもないけれど、単なるバイトだと理解する。Extension の定義はこう。

struct {
    ExtensionType extension_type;
    opaque extension_data<0..2^16-1>;
} Extension;

実際のバイト列と照らし合わせてみる。

03 03 # ProtocolVersion: TLS v1.2
96 f7 37 2d 59 66 76 40 68 90 f8 d2 f5 b0 e1 b1 # Random
4b ac 3a ed 7a 25 ab e0 d0 f5 22 15 64 52 51 7f
20 # Session Id Length
95 f8 f0 4d 5c c1 df 3d 72 70 8f c9 28 37 40 eb # Session Id
d0 13 a5 8d 06 fe f2 5e bf 1e 8e 55 fb 70 9a 59
00 06 # Cipher Suites Length
13 02 # Cipher Suite (TLS_AES_256_GCM_SHA384)
13 01 # Cipher Suite (TLS_AES_128_GCM_SHA256)
13 03 # Cipher Suite (TLS_CHACHA20_POLY1305_SHA256)
01 # Compression Methods Length
00 # Compression Method: (null)
00 c4 # Extensions Length
00 33 # ExtensionType (key_share)
00 47 # Extension Length
...
00 0b # ExtensionType (supported_versions)
00 09 # Extension Length
...
00 0d # ExtensionType (signature_algorithms)
00 0a # Extension Length
...
00 0a # ExtensionType (supported_groups)
00 04 # Extension Length
...
00 2d # ExtensionType (psk_key_exchange_modes)
00 03 # Extension Length
...
00 29 # ExtensionType (pre_shared_key)
00 4b # Extension Length
...

supported_versions の定義はこう：

struct {
    select (Handshake.msg_type) {
       case client_hello:
           ProtocolVersion versions<2..254>;
       case server_hello: /* and HelloRetryRequest */
           ProtocolVersion selected_version;
    };
} SupportedVersions;

select があってごちゃごちゃしているが、client_hello用に書き直すとこう。

struct {
    ProtocolVersion versions<2..254>;
} SupportedVersions;

これが Extension の opaque extension_data の部分となる。versionsは、可変長配列だから、長さがだぶったような感じに符号化される。

00 0b # ExtensionType (supported_versions) 再掲
00 09 # Extension Length 再掲
08 # Supported Versions Length
03 04 # TLS 1.3 (0x0304)
7f 1c # TLS 1.3 (draft 28)
7f 1b # TLS 1.3 (draft 27)
7f 1a # TLS 1.3 (draft 26)

Accepting UDP connections

QUIC

When we implements UDP servers, a pair of recvfrom() and sendto() is used typically. Received UDP packets are dispatched, if necessary, to each connection by our server itself. We might want to delegate this job to the OS kernel for the performance reasons.

This article discusses how to create connected sockets from listening sockets on UDP. Unlike TCP, the accept() system call cannot be used for this purpose. Linux behaves differently from BSD variants. macOS (Monterey) and Windows (10) are buggy. We need to find a reasonable method which can work on all of these.

Terminology

  • Wildcard listening socket: {UDP, *:<service-port>, *:*}
  • Interface-specific listening socket: {UDP, <interface-address>:<service-port>, *:* }
  • Connected socket: {UDP, <interface-address>:<service-port>, <peer-address>:<peer-port>}

First approach based on interface-specific listening sockets

I don't remember why I first chose interface-specific listening sockets instead of wildcard listening sockets. But let's get started with this.

This method was fist described in Implementation status of QUIC in Haskell. Suppose we have a interface-specific listening socket, say {UDP, 192.0.2.1:443, *:*} and peer's address:port is 203.0.113.1:50000.

The following method does not work.

  1. Create a new UDP socket with SO_REUSEADDR ({UDP, *:*, *:*})
  2. Bind it to 192.0.2.1:443 ({UDP, 192.0.2.1:443, *:*})
  3. Connect it to 203.0.113.1:5000 ({UDP, 192.0.2.1:443, 203.0.113.1:5000})

Unfortunately, BSD variants reject (2). Linux accepts (2) but race condition would happen. The improved process is as follows:

  1. Create a new UDP socket with SO_REUSEADDR ({UDP, *:*, *:*})
  2. Bind it to *:443 ({UDP, *:443, *:*})
  3. Connect it to 203.0.113.1:5000. ({UDP, 192.0.2.1:443, 203.0.113.1:5000})

This process succeeds even on BSD variants because there is no duplicated entries at anytime. And there is no race conditions on any platforms.

A bug of the first approach

If a server have multiple interface-addresses of the same protocol family, connect() would select a wrong address. Suppose we have another interface-specific address, say 192.0.2.2.

  1. Create a new UDP socket with SO_REUSEADDR ({UDP, *:*, *:*})
  2. Bind it to *:443 ({UDP, *:443, *:*})
  3. Connect it to 203.0.113.1:5000. ({UDP, 192.0.2.2:443, 203.0.113.1:5000})

Since we cannot specify a local address in 2) and 3), 192.0.2.2 is selected in this example.

Another approach based on wildcard listening sockets

This bug does not exist if we use wildcard listening sockets. Suppose we have ({UDP, *:443, *:*}).

  1. Create a new UDP socket with SO_REUSEADDR ({UDP, *:*, *:*})
  2. Bind it to 192.0.2.1:443 ({UDP, 192.0.2.1:443, *:*})
  3. Connect it to 203.0.113.1:5000 ({UDP, 192.0.2.1:443, 203.0.113.1:5000})

This process succeeds because there is no duplicated entries at anytime. And a local address is specified explicitly.

When the first packet of a connection arrives, recvfrom() only tells you <peer-address>:<peer-port>. To know an interface-specific address, recvmsg() should be used. struct in_pktinfo and struct in6_pktinfo contain the interface-specific address for IPv4 and IPv6, respectively.

Integrating two approaches

Two approaches can co-exist. Step 2) binds anyaddr if an interface-specific listening socket is used. It binds an interface-specific address if a wildcard listening socket is used. Note that the bug above exists if an interface-specific listening socket is used.

recvmsg() of macOS is buggy. If it is used for an IPv4 interface-specific listening port, it changes the local address to anyaddr. IPv6 is OK. So, recvmsg() should be used only for a wildcard socket and recvfrom() should be used for an interface-specific address.

Bug, bug and bug

On OpenBSD, IPV6_V6ONLY is always enabled and cannot be changed. So, we should not use IPv4-IPv6 integrated sockets for the purpose of cross-platform. We should prepare IPv6-only sockets and IPv4-only sockets for listening.

This is not used but recvmsg() on Windows is also buggy. Suppose that recvmsg() used for an IPv4-IPv6 integrated socket and an IPv4 packet is received. struct in6_pktinfo (for IPv4-mapped IPv6 address) is not returned.

Windows

On Windows, connected socket can be used for sending. But for receiving, the dispatching in the kernel works very poorly because matching is done based on local address and local port only (destination only).

  1. Interface-specific listening sockets and connected sockets have the same priority
  2. They wins wildcard listening sockets
  3. For tie break of 1), the first-created one wins.

Suppose we don't' give up connected sockets for sending.

Since packet dispatching to connected sockets in the kernel are impossible, a listing socket should catch all received packets and the server should dispatch them by itself. But wildcard listing sockets cannot be used for this purpose because of 2). On Windows, interface-specific listening sockets should be used. They win against connected sockets because they are created at the beginning.

Integrating Fusion and cryptonite in Haskell quic

Haskell QUIC

While Haskell quic version 0.0.1 or earlier supports the x86_64 architecture only, version 0.0.2 or later will supports non-x86_64 architectures.

cryptonite

When I started implementing the quic library in Haskell, I used cryptonite as crypto engine. Since cryptonite takes the functional style where all results are generated newly without side-effects, it is safe to use it among multiple threads.

I defined the following data for payload encryption and decryption:

data Coder = Coder {
    encrypt :: PlainText  -> AssDat -> PacketNumber -> [CipherText]
  , decrypt :: CipherText -> AssDat -> PacketNumber -> Maybe PlainText
  }

Key and Nonce are partially applied at the initialization period and resulting functions are stored in Code. encrypt returns two ByteString in a list, one is a protected header and the other is an encrypted payload. PlainText, CipherText and AssDat (associative data) are ByteString essentially.

For header protection, I defined the following code:

data Protector = Protector {
    protect   :: Sample -> Mask
  , unprotect :: Sample -> Mask
  }

Sample is taken from an encrypted payload and resulting Mask is used for the xor operation on a header.

Fusion

The maximum record size of TLS is 16KiB. After 16KiB plain text is encrypted and sent from the TLS layer, the TCP layer fragments the cipher text into multiple IP packets. Since 16KiB is large enough, cost of initialization and finalization is invisible.

However, the maximum packet size of QUIC is 1,472 bytes. There was no crypto engine to encrypt and decrypt such small data efficiently. Kazuho Oku invented Fusion crypto engine to solve this problem. I decided switch from cryptonite to Fusion in March 2021. New Coder is as follows:

data Coder = Coder {
    encrypt :: Buffer -> BufferSize -> Buffer -> BufferSize -> PacketNumber -> Buffer -> IO Int
t
  , decrypt :: Buffer -> BufferSize -> Buffer -> BufferSize -> PacketNumber -> Buffer -> IO Int
t
  }

The three buffers are input, associative data and output in order. The output buffer is to be modified. The result is the output size. Fusion encryption also calculates the mask of header protection (but not for unprotection). Protector is changed as follows:

data Protector = Protector {
    setSample :: Buffer -> IO ()
  , getMask   :: IO Buffer
  , unprotect :: Sample -> Mask
  }

setSample and getMask are called before and after encrypt, respectively.

Integration

I misunderstood that Fusion uses a slow crypto engine on non-x86_64 architectures. After releasing quic version 0.0.0, I noticed this is not the case. So, I started integrating Fusion and cryptonite in this December. That is, Fusion should be used on the x86_64 architecture while cryptonite should be used on non-x86_64 architectures.

This project was tough since I needed to integrate the functional style and the imperative style. The key idea is to use cryptonite in the imperative style. The body of resulting ByteStrings are copied into a buffer. This buffer approach should be cerebrated by GSO(Generic Segmentation Offload) in the near future.

The resulting Coder and Protector are as follows:

data Coder = Coder {
    encrypt    :: Buffer -> PlainText  -> AssDat -> PacketNumber -> IO Int
  , decrypt    :: Buffer -> CipherText -> AssDat -> PacketNumber -> IO Int
  , supplement :: Maybe Supplement
  }

data Protector = Protector {
    setSample  :: Buffer -> IO ()
  , getMask    :: IO Buffer
  , unprotect :: Sample -> Mask
  }

I'm satisfied with this signature.

Bugs found

One single buffer is used for decryption in a QUIC connection. So, this buffer should be occupied by the receiver thread. However, the dispatcher thread of a server calls decrypt with this buffer in the migration procedure. Migration is rare but this is a possible race. In the current code, receiver takes care of migration to kick the race out.

In the integration process, I sometime used undefineds as initial values in tentative data structures of Coder. After initializing Coder, we cannot touch the undefineds. However, the test suite was trapped. This reveals that dropping keys (which stores the initial values again) is too early. The current code delays the key drop timing.

If the cryptonite is used, the test suite sometime gets stuck. Visualizing packet sequences illustrates that a client is waiting for Fin forever since a server does not send Fin. In the server side, the server thread and sender thread are racing. Since encrypt called by sender is slow, the server is finished before sender actually sends a packet. So, I modified that shutdownStream and closeStream wait for the completion of Fin packet sending.

我田引水的な「関数プログラミングの入門」資料紹介

Haskell

これは、Haskell Advent Calendar 2021の2日目を埋めるために書いた記事です。実は単に僕が作った「関数プログラミングの入門」の資料の宣伝です。

ちなみに、僕の関数プログラミングの定義は「不変データプログラミング」であり、おそらく最も厳しい定義です。なので内容が分かれば、関数プログラミングに入門できた言ってもよいのではないかと思います。

関数プログラミングことはじめ

僕は毎年、岡山大学の三年生に向けて、2コマで関数プログラミングを教えています。その資料が、「Cプログラマーのための関数プログラミングことはじめ」です。岡山大学工学部情報系学科の学生は、C言語を習っているので、C言語に似た文法を独自に定義して、関数プログラミングを説明しています。

［入門］関数プログラミング

［入門］関数プログラミングは、WEB+DB PRESS Vol.67に掲載された記事です。編集部のご厚意により、オンラインで公開していただきました。関数型言語は記述力が高いので、この少ない分量で、赤黒木やパーサの実装まで辿り着けています。利用している言語はHaskellなので、Haskellの入門としても使えます。

再帰ドリル

再帰ドリルは、宮崎大学での集中講義の資料です。関数プログラミングとは切っても切り離せない再帰をドリル形式で解説しています。分かりやすく、包括的な内容になっていると思います。使用言語はHaskellです。コードを読めば、Haskellでのテストの書き方も習得できるかもしれません。

GHCのIOマネージャの歴史と僕の苦悩

Haskell

これは、Haskell Advent Calendar 2021 の8日目の記事です。

Haskellのコンパイラとして事実上一択となったGHCには、「軽量スレッド」が実装されています。軽量スレッドは、ネイティブスレッドよりも軽量なスレッドで、他の言語では「グリーンスレッド」とも呼ばれています。Haskellerが並行プログラミングをするときは、軽量スレッドを息を吸うかのように使います。

複数の軽量スレッドの入出力を束ねるのが、IOマネージャです。IOマネージャも単なる軽量スレッドであり、OSから入出力のイベントを受け取り、それぞれの軽量スレッドにイベントを通知します。

軽量スレッド(っぽい)機能を提供する他の言語では、GHCのIOマネージャを参考にしているようです。僕はIOマネージャの開発に深く関わっています。この記事ではIOマネージャの歴史をまとめるとともに、主にmacOSでの実装に関する苦悩を備忘録として残します。

第1世代

  • 論文 "Extending the Haskell Foreign Function Interface with Concurrency" で解説されています。
  • 2005年3月にリリースされたGHC 6.4で導入されました。

pollシステムコールを使って実装されています。pollはイベントの登録と監視が一体となったシステムコールです。このため、ある軽量スレッドが新たに入出力の登録を依頼する場合は、ブロックされているIOマネージャを一旦起こさないといけません(pollをやめさせなければなりません)。

これを実現するための画期的なアイディアが、wakeupパイプです。IOマネージャは、監視対象としてwakeupパイプも指定して、pollを呼びます。軽量スレッドがwakeupパイプにバイト列を書き込めば、IOマネージャはpollから抜けることができ、新たなイベントを加えて再度pollを呼び出します。

pollシステムコールの弱点は以下の通りです。

  • 登録できるイベントの個数に制限がある。
  • 受け取ったイベントを線形探索する必要があるので、イベントの個数が多くなるとスケールしない。

第2世代

  • 論文 "Scalable Event Handling for GHC" で解説されています。
  • 2010年11月にリリースされたGHC 7.0で導入されました。

pollの問題点を克服するために、Linuxではepoll、BSDではkqueueを使うようになりました。epollやkqueueは、pollのスーパーセットという限定的な利用方法が用いられています。

第2世代のIOマネージャの欠点は、マルチコア環境で性能が出ないことです。この理由としては、グローバルロックが使われていたことなどが挙げられます。

第3世代

  • 論文 "Mio: A High-Performance Multicore IO Manager for GHC" で解説されいます。
  • 2014年4月にリリースされたGHC 7.8で導入されました。

マルチコア環境ででスケールさせるために、グローバルロックが分割されると共に、コアごとにIOマネージャが起動されることになりました。

また、デフォルトではwakeupパイプは利用されなくなりました。これが実現できるのは、epollやkqueueが、イベントの登録と監視を独立させているからです。たとえば、epollでは登録がepoll_ctlで、監視はepoll_waitを使います。IOマネージャがepoll_waitでブロックされていても、別のスレッドはepoll_ctlでイベントを登録できるのです。登録されたイベントは削除しないといけませんが、削除の手間を省くために、使われたら削除される「one shot」というモードが利用されています。

Windows

WindowsのIOマネージャに関しては詳しくないので、New Windows I/O manager in GHC 8.12を参照してください。GHC 8.12は、GHC 9.0に置き換えて読んでください。

嗚呼、macOS

第3世代のIOマネージャは、Andreas Voellmyさんがepoll版を開発し、僕がkqueueに移植しました。この移植後、macOS上でGHCの並列ビルドが失敗するようになるという問題が発生しました。BSDでは問題ないのに、macOSでは問題が生じます。この問題は結局解決できずに、macOS上ではone shotモードを諦めて、wakeupパイプを使い続けるという方法で回避されました。(FreeBSDなどでは、one shotモードが使われています。)

その後、kqueueのIOマネージャに書き込みイベントの登録が失敗するというバグが発見されます。epoll_ctlの EPOLLIN や EPOLLOUT はフラグ(ビットマスク)ですが、kqueue の EVFILT_READ と EVFILT_WRITE はフラグではありません。kqueueで読み書き両方を登録するには、読み込みイベントと書き込みイベントの2つを登録する必要があります。移植の際に、この事実に気づかずバグを入れ込んでいました。one shot用のコードでも、wakeupパイプ用のコードでも、このバグは直されました。GHC 8.4から恩恵にあずかれます。

これでmacOSの並列ビルドの問題も解決したと勘違いして、macOSでone shotモードを使おうという提案をしました。しかし、macOSでone shotを使うようになったGHC 9.0.1をmacOSで使ってみると、ネットワーク関係のライブラリでテストが通らなくなっていました。

結局、macOSのkqueueには、one shotにバグがあるというのが僕の結論です。GHC 9.0.2では、再びwakeupパイプが利用されるようになります。