eBPF Talk: XDP 支持 traceroute

不管 traceroute 具体的工作原理是什么，只需要抓住一点：如果当前的包 IP 头里的 TTL 是 1，那么就可以回一个 ICMP TtlExceeded 包，这样就可以支持 traceroute 和 mtr 了。

TL;DR XDP 程序里的处理逻辑比较简单：

判断 IP 头里的 TTL 是否为 1。
干掉当前包里的 payload。
扩充包头部空间，加上 IP 头和 ICMP 头的空间大小。
填充 IP 头并计算校验和。
填充 ICMP 头并计算校验和。

demo 效果

1
2


# ./xdp-traceroute --dev enp0s1
2023/12/17 06:20:36 traceroute is running on enp0s1

P.S. 下图中标出的 DSCP 0x2b 是因为在 xdp-traceroute 里把 IP 头里的 tos 字段设置为了 0x2b，这样可以方便在 wireshark 里过滤出来。

下图中，Time to live exceeded in Transit 的包是 xdp-traceroute 生成的，其他的包是内核协议栈生成的。

xdp-traceroute

1. 判断 IP 头里的 TTL 是否为 1

该判断逻辑比较简单，如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


SEC("xdp")
int traceroute(struct xdp_md *ctx)
{
    struct ethhdr *eth = (struct ethhdr *)((void *)(__u64) ctx->data), copied;
    struct iphdr *iph = (struct iphdr *)(eth + 1);
    // ...

    if ((void *)(__u64) (iph + 1) > (void *)(__u64) ctx->data_end)
        return XDP_PASS;

    if (eth->h_proto != bpf_htons(ETH_P_IP))
        return XDP_PASS;

    if (iph->ttl > 1)
        return XDP_PASS;

    // ...
}

2. 干掉当前包里的 payload

这里的 payload 指的是 TCP/UDP/ICMP 等协议的数据部分，这里的处理逻辑复杂一些：

通过 ctx->data_end - ctx->data 计算出当前包的大小。
~~通过 IP 头里的 ihl 字段计算出 IP 头的大小~~ 通过 IP 头里的 protocol 字段判断 TCP/UDP/ICMP。
通过当前包的大小减去 ETH 头、IP 头和 TCP/UDP/ICMP 头的大小，得到需要干掉的包大小。
调用 bpf_xdp_adjust_tail() 来干掉 payload。

P.S. 干掉 payload 的同时，计算出 TtlExceeded 包里 ICMP 头的 payload 大小，方便后面计算 ICMP 头的校验和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


static __always_inline int
__trim_payload(struct xdp_md *ctx, struct ethhdr *eth, struct iphdr *iph,
               __u64 *icmp_payload)
{
    int pkt_len = ctx->data_end - ctx->data, trim_size;
    int payload_len, iph_len = sizeof(*iph);
    // ...

    switch (iph->protocol) {
    case IPPROTO_TCP:
        payload_len = iph_len + sizeof(struct tcphdr);
        // ...
        break;

    case IPPROTO_UDP:
        payload_len = iph_len + sizeof(struct udphdr);
        // ...
        break;

    case IPPROTO_ICMP:
        payload_len = iph_len + sizeof(struct icmphdr);
        // ...
        break;

    default:
        return XDP_PASS;
    }

    *icmp_payload = payload_len;
    trim_size = pkt_len - sizeof(*eth) - payload_len;
    if (trim_size < 0)
        return XDP_PASS;

    if (trim_size > 0 && bpf_xdp_adjust_tail(ctx, -trim_size))
        return XDP_PASS;

    return 0;
}

3. 扩充包头部空间，加上 IP 头和 ICMP 头的空间大小

这里的处理逻辑也比较简单，通过 bpf_xdp_adjust_head() 来扩充包头部空间：

1
2
3
4
5
6
7


static __always_inline int
__expand_icmp_headroom(struct xdp_md *ctx)
{
    const int siz = (sizeof(struct iphdr) + sizeof(struct icmphdr));

    return bpf_xdp_adjust_head(ctx, -siz);
}

填充 ETH 头

这里只需要注意一点，就是填充 ETH 头的时候，需要把源 MAC 和目的 MAC 交换一下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


static __always_inline int
__encode_icmp_packet(struct xdp_md *ctx, struct ethhdr *org_eth,
                     __u64 icmp_payload, __u32 sip, __u16 id)
{
    struct ethhdr *eth = (struct ethhdr *)((void *)(__u64) ctx->data);
    // ...

    if ((void *)(__u64) (icmph + 1) + icmp_payload > (void *)(__u64) ctx->data_end)
        return XDP_PASS;

    __builtin_memcpy(eth->h_dest, org_eth->h_source, ETH_ALEN);
    __builtin_memcpy(eth->h_source, org_eth->h_dest, ETH_ALEN);
    eth->h_proto = bpf_htons(ETH_P_IP);

    // ...

    return XDP_TX;
}

SEC("xdp")
int traceroute(struct xdp_md *ctx)
{
    struct ethhdr *eth = (struct ethhdr *)((void *)(__u64) ctx->data), copied;
    // ...

    __builtin_memcpy(&copied, eth, sizeof(copied));

    // ...

    return __encode_icmp_packet(ctx, &copied, icmp_payload, sip, id);
}

计算校验和

在 XDP 里计算校验和并不是一件容易的事情，因为 XDP 里在计算校验和之前，需要计算出包的大小；而如果使用 ctx->data_end - ctx->data 来计算包的大小，那么 bpf verifier 会报错：

1
2
3
4
5
6
7
8
9


    ; size = ctx_ptr(ctx, data_end) - (void *)(__u64) icmph;
    205: (1c) w4 -= w8                    ; R4_w=scalar() R8_w=pkt(off=34,r=82,imm=0)
    ; sum = bpf_csum_diff(0, 0, data_start, data_size, 0);
    206: (b7) r1 = 0                      ; R1_w=0
    207: (b4) w2 = 0                      ; R2_w=0
    208: (bf) r3 = r8                     ; R3_w=pkt(off=34,r=82,imm=0) R8_w=pkt(off=34,r=82,imm=0)
    209: (b4) w5 = 0                      ; R5_w=0
    210: (85) call bpf_csum_diff#28
    R4 min value is negative, either use unsigned or 'var &= const'

而 demo 里采用的校验和计算方法是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


static __always_inline __u16 csum_fold_helper(__wsum sum)
{
    sum = (sum & 0xffff) + (sum >> 16);
    return ~((sum & 0xffff) + (sum >> 16));
}

static __always_inline __u16
ipv4_csum(void *data_start, int data_size)
{
    __wsum sum = 0;
    sum = bpf_csum_diff(0, 0, data_start, data_size, 0);
    return csum_fold_helper(sum);
}

static __always_inline void
__update_icmp_checksum(struct icmphdr *icmph, int size)
{
    icmph->checksum = 0;
    icmph->checksum = ipv4_csum(icmph, size);
}

static __always_inline void
__update_ip_checksum(struct iphdr *iph)
{
    iph->check = 0;
    iph->check = ipv4_csum(iph, sizeof(*iph));
}

4. 填充 IP 头并计算校验和

这里的处理逻辑也比较简单，就是填充 IP 头并计算校验和：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


static __always_inline int
__encode_icmp_packet(struct xdp_md *ctx, struct ethhdr *org_eth,
                     __u64 icmp_payload, __u32 sip, __u16 id)
{
    struct ethhdr *eth = (struct ethhdr *) ctx_ptr(ctx, data);
    struct iphdr *iph = (struct iphdr *)(eth + 1);
    // ...

    if ((void *)(__u64) (icmph + 1) + icmp_payload > ctx_ptr(ctx, data_end))
        return XDP_PASS;

    // ...

    iph->version = 4;
    iph->ihl = sizeof(*iph) >> 2;
    iph->tos = 0x2b; // Custom TOS to identify the packet.
    iph->tot_len = bpf_htons(sizeof(*iph) + sizeof(*icmph) + icmp_payload);
    iph->id = id;
    iph->frag_off = 0;
    iph->ttl = 64;
    iph->protocol = IPPROTO_ICMP;
    iph->saddr = MY_ADDR; // Custom IP address by Go RewriteContants().
    iph->daddr = sip;
    __update_ip_checksum(iph);

    // ...

    return XDP_TX;
}

SEC("xdp")
int traceroute(struct xdp_md *ctx)
{
    struct ethhdr *eth = (struct ethhdr *) ctx_ptr(ctx, data), copied;
    struct iphdr *iph = (struct iphdr *)(eth + 1);
    __u64 icmp_payload;
    __u32 sip;
    __u16 id;

    // ...

    sip = iph->saddr;
    id = iph->id;

    // ...

    return __encode_icmp_packet(ctx, &copied, icmp_payload, sip, id);
}

5. 填充 ICMP 头并计算校验和

这里的处理逻辑也比较简单，就是填充 ICMP 头并计算校验和：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


static __always_inline int
__encode_icmp_packet(struct xdp_md *ctx, struct ethhdr *org_eth,
                     __u64 icmp_payload, __u32 sip, __u16 id)
{
    struct ethhdr *eth = (struct ethhdr *) ctx_ptr(ctx, data);
    struct iphdr *iph = (struct iphdr *)(eth + 1);
    struct icmphdr *icmph = (struct icmphdr *)(iph + 1);

    if ((void *)(__u64) (icmph + 1) + icmp_payload > ctx_ptr(ctx, data_end))
        return XDP_PASS;

    // ...

    icmph->type = ICMP_TIME_EXCEEDED;
    icmph->code = ICMP_EXC_TTL;
    icmph->un.gateway = 0;
    __update_icmp_checksum(icmph, sizeof(*icmph) + icmp_payload);

    return XDP_TX;
}

SEC("xdp")
int traceroute(struct xdp_md *ctx)
{
    struct ethhdr *eth = (struct ethhdr *) ctx_ptr(ctx, data), copied;
    struct iphdr *iph = (struct iphdr *)(eth + 1);
    // ...

    if (__trim_payload(ctx, eth, iph, &icmp_payload))
        return XDP_PASS;

    // ...

    return __encode_icmp_packet(ctx, &copied, icmp_payload, sip, id);
}

demo 源代码

完整源代码请查看：GitHub xdp-traceroute。

小结

本文介绍了如何使用 XDP 来支持 traceroute 和 mtr，主要的处理逻辑是：

判断 IP 头里的 TTL 是否为 1。
干掉当前包里的 payload。
扩充包头部空间，加上 IP 头和 ICMP 头的空间大小。
填充 IP 头并计算校验和。
填充 ICMP 头并计算校验和。

其中需要注意的地方是：计算校验和的时候，需要明确地知道用于计算校验和的包范围。