[BPF 入门] BPF Map 之 LPM Trie

原创 Hengqi Chen eBPF

Linux 内核 commit b95a5c4db09b 引入了一个 BPF Map 类型

BPF_MAP_TYPE_LPM_TRIE：

bpf: add a longest prefix match trie map implementation

This trie implements a longest prefix match algorithm that can be used

to match IP addresses to a stored set of ranges.

从这个提交信息里，我们可以了解到它可以用来匹配 IP 地址范围，比如

203.0.113.0/24 。

作为一个字典树，当然，我们也可以用它来匹配字符串。

这个 Map 的使用非常简单，Key 是我们期望匹配的最长序列，Value 是任意的，按照需求来选择。

⚠️ 限制

Map Flags 一定要包含 BPF_F_NO_PREALLOC
Key 的前四个字节用于指明最长前缀的长度，单位为比特（bit）
Value 不能为空

这是最初的提交中引入的限制，新版本略有不同：

/* check sanity of attributes */if (attr->max_entries == 0 ||    attr->map_flags != BPF_F_NO_PREALLOC ||    attr->key_size < sizeof(struct bpf_lpm_trie_key) + 1   ||    attr->key_size > sizeof(struct bpf_lpm_trie_key) + 256 ||    attr->value_size == 0)        return ERR_PTR(-EINVAL);

示例

例如，对于 203.0.113.0/24 ，可以表示如下：

其中 Prefix length 占用 4 个字节，指定匹配 24 比特的数据。将其插入 LPM Trie 中，可以用来匹配：

但不能匹配：

当然，我们也可以用它来匹配字符串，感兴趣的读者可以自己测试一下。

代码

#include <assert.h>#include <stdint.h>#include <stdio.h>#include <arpa/inet.h>#include <errno.h>#include <unistd.h>#include <bpf/bpf.h>
struct trie_key {        uint32_t prefix_length;        uint32_t ip;};
int main(){        LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);        const char *map_name = "lpm_trie_test";        const unsigned int max_entries = 1;        struct trie_key key = {};        int map_fd, ret, value;
        libbpf_set_strict_mode(LIBBPF_STRICT_ALL);
        map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, map_name,                                sizeof(struct trie_key), sizeof(int),                                max_entries, &opts);        if (map_fd < 0) {                ret = -errno;                perror("bpf_map_create");                return ret;        }
        key.prefix_length = 24;        inet_pton(AF_INET, "203.0.113.0", &key.ip);        value = 216;        ret = bpf_map_update_elem(map_fd, &key, &value, BPF_ANY);        if (ret) {                perror("bpf_map_update_elem");                goto cleanup;        }
        key.prefix_length = 24;        inet_pton(AF_INET, "203.0.113.127", &key.ip);        value = 0;        ret = bpf_map_lookup_elem(map_fd, &key, &value);        if (ret) {                perror("bpf_map_lookup_elem");                goto cleanup;        }        assert(value == 216);
        key.prefix_length = 24;        inet_pton(AF_INET, "203.0.112.0", &key.ip);        value = 0;        ret = bpf_map_lookup_elem(map_fd, &key, &value);        if (ret != -ENOENT) {                perror("bpf_map_lookup_elem");                goto cleanup;        }        assert(value == 0);
cleanup:        close(map_fd);        return 0;}

结语

第一次看到这个 Map 类型的提交信息的时候，我马上就意识到可以用它来实现一个类似于 tcpdump 的抓包工具，后面的文章我们将使用 LPM Trie + Socket Filter 来实现一个这样的的工具。

继续滑动看下一个