编写 eBPF 程序和利用 HyperLogLog 统计包的信息¶

前段时间在写概率论与数理统计的期末论文，讨论的主题是如何对一个十分巨大的多重集合（或者是流）中相异元素个数进行估计，写的是 HyperLogLog 等算法。联想到前段时间 LWN 上多次提到的 eBPF 和 BCC 的文章，我准备自己用 eBPF 实现一个高效的估计 inbound packet 中来相异源地址的个数和 outbound packet 中相异目的地址的个数。经过了许多的尝试和努力，最终是写成了 jiegec/hll_ebpf ，大致原理如下：

由于 eBPF 是一个采用专用的 bytecode 并且跑在内核中的语言，虽然我们可以用 clang 写 C 语言然后交给 LLVM 生成相应地 eBPF bytecode，但仍然收到许多的限制。而且，我很少接触 Linux 内核开发，于是在找内核头文件时费了一番功夫。首先是核心代码：

struct bpf_map_def SEC("maps") hll_ebpf_out_daddr = {
    .type = BPF_MAP_TYPE_PERCPU_ARRAY,
    .key_size = sizeof(u32),
    .value_size = sizeof(u32),
    .max_entries = 256,
    .pinning = 2 // PIN_GLOBAL_NS
};

SEC("out_daddr")
int bpf_out_daddr(struct __sk_buff *skb) {
  u32 daddr = get_daddr(skb);
  u32 hash = Murmur3(daddr, 0);
  update_hll(&hll_ebpf_out_daddr, hash);
  return 0;
}

首先是声名一个类型为 PERCPU_ARRAY 的 eBPF MAP 类型。这里的 MAP 不是字典，Array 才是真是的数据结构，只不过提供的 API 是类似于字典的。SEC 宏则是指定这个东西要放在哪一个段，这个在后面会提到。这个函数的作用就是，获取 IP 包的目的地址（其实应该判断一下是否是 IPv4 的），然后根据 HyperLogLog 的要求，进行哈希（这里采用的是 Murmur3），然后对得到的哈希值分段，前一部分用于索引，后一部分的 nlz（clz, whatever）用于估计。具体算法详情可以参考 HyperLogLog 的论文。

接着，我们可以把这个 eBPF 函数进行编译，并且应用起来：

$ export KERN=4.16.0-2 # or use uname -r with awk, see Makefile
$ clang -O2 -I /usr/src/linux-headers-${KERN}-common/include -I /usr/src/linux-headers-${KERN}-common/arch/x86/include -emit-llvm -c bpf.c -o - | llc -march=bpf -filetype=obj -o bpf.o
$ export IFACE=en0 
$ sudo tc qdisc add dev ${IFACE} clsact || true
$ sudo tc filter del dev ${IFACE} egress
$ sudo tc filter add dev ${IFACE} egress bpf obj bpf.o sec out_daddr
$ sudo tc filter del dev ${IFACE} ingress
$ sudo tc filter add dev ${IFACE} ingress bpf obj bpf.o sec in_saddr

我们需要在用户态读出上面这个 MAP 中的内容。由于它是全局的，我们可以在 /sys/fs/bpf/tc/globals 中找到他们。然后，把统计得到的数据进行综合，得到结果：

void read_file(const char *file) {
  int fd = bpf_obj_get(file);
  const static int b = 6;
  const static int m = 1 << b;
  int M[m] = {0};
  int V = 0;
  double sum = 0;
  for (unsigned long i = 0; i <m; i++) {
    unsigned long value[2] = {0};
    bpf_map_lookup_elem(fd, &i, &value);
    M[i] = value[0] > value[1] ? value[0] : value[1]; // assuming 2 CPUs, will change later
    if (M[i] == 0)
      V++;
    sum += pow(2, -M[i]);
  }
  double E = 0.709 * m * m / sum;
  if (E <= 5 * m / 2) {
    if (V != 0) {
      E = m * log(1.0 * m / V);
    }
  } else if (E> pow(2, 32) / 30) {
    E = -pow(2, 32) * log(1 - E / pow(2, 32));
  }
  printf("%ld\n", lround(E));
}

可以手动通过 nmap 测试，例如扫描一个段，可以看到数据会增长许多。如果扫描相同的段，则数字不会变化，但如果扫描新的段，数字会有变化。这是一个利用了 eBPF 的 HyperLogLog 的实现。

编写 eBPF 程序和利用 HyperLogLog 统计包的信息¶

评论