eBPFでQUICパケットをルーティングしていく

はじめに

LinuxのeBPFを使ってQUICパケットのDestination Connection IDを元にQUICサーバーのSO_REUSEPORTした特定のソケットへパケットを送り込む試みについて記述します。

ユースケース

TCPを扱う典型的なマルチスレッドサーバーの一例としては、各スレッドでlisten、受信データの処理を行います。カーネルがパケットの面倒は全て見てくれるため、アプリケーションはソケットからデータの送受信だけをしていれば良かったのです。QUICはUDPパケットのハンドリングはカーネル任せですがその先は、ユーザースペースで実装する必要があります。UDPでSO_REUSEPORTを使って複数ソケットで同じアドレスで待ち受けすることはできますが、IPアドレス、ポートの四つ組で振り分けされることになります。QUICは概ねこれでも行けそうですが、QUICはコネクションのマイグレーション、すなわち、クライアントのIPアドレス、ポートが変更になってもQUIC接続を維持できる機能が組み込まれています。これの実現のために、Connection IDを使って接続を認識しています。というわけでConnection IDでパケットを特定のソケットに振り分けたいという需要が生まれるのです。

そんなことしなくても、受け取ったQUICパケットのConnection IDを見て再度適切なスレッドに振り分けることもできるでしょう。どちらが効率良いかは比較していないのでどうも分かりません。

QUICパケットとConnection ID

まずQUICパケットですが、UDP datagramのペイロードに格納されたデータということになります。QUICパケットにはいくつか種類があり、この記事に必要な範囲でいうと二つの種類があります。

1. ロングヘッダーパケット
2. ショートヘッダーパケット

文字通りQUICパケットのヘッダーが長いか短いかで分かれているのですが、ロングヘッダーパケットはハンドシェークの時に使い、ショートヘッダーパケットはハンドシェーク完了後に使うものとなっています。ロングヘッダーパケットには、Initialパケット、Handshakeパケットがあります(0RTTパケットもありますがこの記事では省略)。

draft-32の場合、Initialパケットは以下のようなレイアウトとなっており:

   Initial Packet {
     Header Form (1) = 1,
     Fixed Bit (1) = 1,
     Long Packet Type (2) = 0,
     Reserved Bits (2),
     Packet Number Length (2),
     Version (32),
     Destination Connection ID Length (8),
     Destination Connection ID (0..160),
     Source Connection ID Length (8),
     Source Connection ID (0..160),
     Token Length (i),
     Token (..),
     Length (i),
     Packet Number (8..32),
     Packet Payload (..),
   }

Destination Connection IDは、その長さが5バイト目(0ベース)、データが6バイト目から保存されています。Handshakeパケットも同じ場所に格納されています。

ショートヘッダーパケットの場合:

   Short Header Packet {
     Header Form (1) = 0,
     Fixed Bit (1) = 1,
     Spin Bit (1),
     Reserved Bits (2),
     Key Phase (1),
     Packet Number Length (2),
     Destination Connection ID (0..160),
     Packet Number (8..32),
     Packet Payload (..),
   }

Destination Connection IDは1バイト目に格納されています。長さがないのは受信側は長さを知っているはずなので省略されています。

基本的にDestination Connection IDは、そのパケットを受け取る受信側が相手にSource Connection IDとして送信した物を使うのですが、例外はクライアントが最初のInitialパケットをサーバーへ送信する時です。この時はクライアントは8バイト以上のランダムなDestination Connection IDを生成してサーバーへ送信します。サーバーはConnection IDを生成し、Source Connection IDとしてクライアントに送ります。クライアントは以後は受信したSource Connection IDをDestination Connection IDとして使います。基本的なハンドシェークとConnection IDについては以下のようになります:

Client                                 Server
| Initial (D, C) --->                    |
|                  <--- Initial (C, S)   |
|                  <--- Handshake (C, S) |
|                  <--- Short (C, _)     |
| Handshake (S, C) --->                  |
| Short (S, _) --->                      |

(A, B): AがDestination Connection ID, BがSource Connection ID, _の場合はフィールドが存在しない

Dがクライアントがランダムに生成したDestination Connection IDになります。CはクライアントのSource Connection ID。Sがサーバーが生成するSource Connection ID。

今回扱うのはQUICサーバーなのでD、Sを使ってパケットを特定のソケットへ流すことをeBPFで実現したい、というのが目的となります。

eBPF

今回使うのはsk_reuseportという物で、struct sk_reuseport_md *reuse_mdでパケットを受け取り、bpf_sk_select_reuseport()を使ってSO_REUSEPORTしたソケットを選択することになります。

簡単にするためにソケットの数を4にしています。

struct {
  __uint(type, BPF_MAP_TYPE_REUSEPORT_SOCKARRAY);
  __uint(max_entries, 255);
  __uint(key_size, sizeof(__u32));
  __uint(value_size, sizeof(__u32));
} reuseport_array SEC(".maps");

typedef struct quic_hd {
  __u8 *dcid;
  __u32 dcid_offset;
  __u32 dcid_len;
  __u8 type;
} quic_hd;

#define SV_DCIDLEN 18
#define MAX_DCIDLEN 20
#define MIN_DCIDLEN 8

#define NUM_SOCKETS 4

SEC("sk_reuseport")
int _select_by_skb_data(struct sk_reuseport_md *reuse_md) {
  __u32 sk_index;
  int rv;
  quic_hd qhd;
  __u32 a, b;
  __u8 *p;

  rv = parse_quic(&qhd, reuse_md);
  if (rv != 0) {
    return SK_DROP;
  }

  switch (qhd.type) {
  case 0x0: /* Initial */
  case 0x1: /* 0-RTT */
    if (reuse_md->data + sizeof(struct udphdr) + 6 + 8 > reuse_md->data_end) {
      return SK_DROP;
    }

    p = (__u8 *)reuse_md->data + sizeof(struct udphdr) + 6;
    a = (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];
    b = (p[4] << 24) | (p[5] << 16) | (p[6] << 8) | p[7];

    sk_index = jhash_2words(a, b, reuse_md->hash) % NUM_SOCKETS;

    break;
  case 0x2: /* Handshake */
    if (qhd.dcid_len != SV_DCIDLEN) {
      return SK_DROP;
    }

    if (reuse_md->data + sizeof(struct udphdr) + 6 + 1 > reuse_md->data_end) {
      return SK_DROP;
    }

    sk_index =
        *((__u8 *)reuse_md->data + sizeof(struct udphdr) + 6) % NUM_SOCKETS;

    break;
  case 0xff: /* Short */
    if (qhd.dcid_len != SV_DCIDLEN) {
      return SK_DROP;
    }

    if (reuse_md->data + sizeof(struct udphdr) + 1 + 1 > reuse_md->data_end) {
      return SK_DROP;
    }

    sk_index =
        *((__u8 *)reuse_md->data + sizeof(struct udphdr) + 1) % NUM_SOCKETS;
    break;
  default:
    return SK_DROP;
  }

  rv = bpf_sk_select_reuseport(reuse_md, &reuseport_array, &sk_index, 0);
  if (rv != 0) {
    return SK_DROP;
  }

  return SK_PASS;
}

reuseport_arrayはユーザースペースのプログラムとデータを共有するための物ですが、ここにはソケットのインデックスとfile descriptorを保存してあります。保存の方法は後述。

parse_quic()はQUICパケットヘッダーからパケットの種類とDestination Connection IDを得るための関数です。
ソケットはインデックスで選択することになるので、パケット種類に応じてインデックスを決定するのですが、Initialパケットの場合、Destination Connection IDは最低8バイトあるのでそれをjhashしてインデックスを決定しています。本来はDestination Connection ID全体を使うべきでしょう。これは明らかに手抜きです。reuse_md->hashはおそらくアドレス四つ組からのハッシュだと思われるんですが、これはjhashの初期値として与えることにしました。これについてはよくわかっていない。

Handshakeパケット、ショートヘッダーパケットについてはDestination Connection IDの最初のバイトだけでソケットのインデックスを決定しています。これはサーバーが生成するSource Connection IDの0バイト目にソケットのインデックスをエンコードするようにしているからです。Connection IDは暗号化されない部分だしサーバーの内部処理で使う値が外に出ているのはいまいちな気がしますね。

parse_quic()は以下のようになっています:

static inline int parse_quic(quic_hd *qhd, struct sk_reuseport_md *reuse_md) {
  __u64 len = sizeof(struct udphdr) + 1;
  __u8 *p;
  __u64 dcidlen;

  if (reuse_md->data + len > reuse_md->data_end) {
    return -1;
  }

  p = reuse_md->data + sizeof(struct udphdr);

  if (*p & 0x80) {
    len += 4 + 1;
    if (reuse_md->data + len > reuse_md->data_end) {
      return -1;
    }

    p += 1 + 4;

    dcidlen = *p;

    if (dcidlen > MAX_DCIDLEN || dcidlen < MIN_DCIDLEN) {
      return -1;
    }

    len += 1 + dcidlen;

    if (reuse_md->data + len > reuse_md->data_end) {
      return -1;
    }

    ++p;

    qhd->type =
        (*((__u8 *)(reuse_md->data) + sizeof(struct udphdr)) & 0x30) >> 4;
    qhd->dcid = p;
    qhd->dcid_offset = sizeof(struct udphdr) + 6;
    qhd->dcid_len = dcidlen;
  } else {
    len += SV_DCIDLEN;
    if (reuse_md->data + len > reuse_md->data_end) {
      return -1;
    }

    qhd->type = 0xff;
    qhd->dcid = (__u8 *)reuse_md->data + sizeof(struct udphdr) + 1;
    qhd->dcid_offset = sizeof(struct udphdr) + 1;
    qhd->dcid_len = SV_DCIDLEN;
  }

  return 0;
}

eBPFプログラムのコンパイルですがclang-10を使う場合、カーネルヘッダーを用意して:

$ clang-10 -O2 -Wall -target bpf -g -c reuseport_kern.c -o reuseport_kern.o \
   -I/path/to/kernel/include

のようにすればコンパイルできます。カーネルヘッダーについては https://www.kernel.org/doc/Documentation/kbuild/headers_install.txt を読むとインストールの方法は分かります。

次にサーバーの方ですが、eBPFプログラムをロードするには:

#include <linux/bpf.h>
#include <bpf/libbpf.h>
#include <bpf/bpf.h>

int prog_fd;
int reuseport_array;

bpf_object *obj;
if (bpf_prog_load("reuseport_kern.o", BPF_PROG_TYPE_SK_REUSEPORT, &obj,
                  &prog_fd) != 0) {
  std::cerr << "bpf_prog_load: " << strerror(errno) << std::endl;
  exit(EXIT_FAILURE);
}

prog_fdを使って後ほどソケットにアタッチします。reuseport_arrayのユーザースペース側の口を用意します:

auto map = bpf_object__find_map_by_name(obj, "reuseport_array");
reuseport_array = bpf_map__fd(map);

次にソケットの用意です。ソケット4つ用意して、それぞれでSO_REUSEPORTします。eBPFプログラムをアタッチするのは最初のソケットだけで良いようです:

if (svindex == 0) {
  setsockopt(fd, SOL_SOCKET, SO_ATTACH_REUSEPORT_EBPF, &prog_fd,
             static_cast<socklen_t>(sizeof(prog_fd)));
}

bind(fd, ...);

bpf_map_update_elem(reuseport_array, &svindex, &fd, BPF_NOEXIST)

svindexがソケットのインデックスです。fdがソケットのfile descriptor。

今後

これでひとまずDestination Connection IDを使って特定のソケットまで誘導できてはいるんですが、QUICの仕様に詳しい人はもう気づいたことでしょう。Initialパケットはクライアントが生成するランダムConnection IDだけではなく、サーバーが生成するSource Connection IDで送信される場合もあります。この記事の方法だとこれに対応できていない。QUICの初期の仕様ではInitialパケットは必ずランダムなConnection IDと限定されていたのですが、今は二種類あるので状況が複雑です。このようなことが起こるのはパケットロスが発生した時やサーバーのInitialパケットが多数ありクライアントがACKを送信してしまう、0RTTパケットをサーバーのInitialパケット受信後も送信し続けると言った限定されたところなので、一旦は別のソケット(スレッド)に行ってしますが、この事象を検出できれば適切なソケットへ横流しするバイパスを設けてやれば解決すると思われます。

参考

• 本記事で解説した完全なソースコード: https://github.com/ngtcp2/ngtcp2/tree/bpf