共计 12200 个字符，预计需要花费 31 分钟才能阅读完成。
家喻户晓，大型 eBPF 程序构建过程中 eBPF map 必不可少。火山引擎边缘计算在数据面也大量应用了 eBPF 及其 map 机制。如何用好 map 是 eBPF 网络编程中要害的一环，不同 map 的性能差别也较大。本文组织 eBPF map 相干的底层实现，为大家具体解析 eBPF map 的原理及性能。
援用
1、什么是 eBPF map
2、eBPF map 原理
3、eBPF map 性能
4、总结
01 背景
家喻户晓，大型 eBPF 程序构建过程中 eBPF map 必不可少。map 是买通数据面和管制面的要害机制。在理论应用过程中，咱们能够通过 map 存储弹性公网 IP 配置数据、在数据面匹配时通过 map 来查问弹性公网 IP，而后执行限速、NAT 等逻辑，以及通过 map 来存储链接等。
火山引擎边缘计算在数据面也大量应用了 eBPF 及其 map 机制，并基于 eBPF 实现了 VPC 网络、负载平衡、弹性公网 IP、外网防火墙等一系列高性能、高可用的云原生网络解决方案。
火山引擎边缘计算云平台架构图
eBPF map 有多种不同类型，反对不同的数据结构，最常见的例如 Array、Percpu Array、Hash、Percpu Hash、lru Hash、Percpu lru Hash、lpm 等等。那么选取哪个类型的 map，如何用好 map 就是 eBPF 网络编程中要害的一环，不同 map 的性能也是相差很大的。本文组织 eBPF map 相干的底层实现，为大家具体解析 eBPF map 的原理及性能。
02 什么是 eBPF map
eBPF map 是一个通用的数据结构存储不同类型的数据，提供了用户态和内核态数据交互、数据存储、多程序共享数据等性能。官网形容[1]：
eBPF maps are a generic data structure for storage of different data types. Data types are generally treated as binary blobs, so a user just specifies the size of the key and the size of the value at map-creation time. In other words, a key/value for a given map can have an arbitrary structure.
A user process can create multiple maps (with key/value-pairs being opaque bytes of data) and access them via file descriptors. Different eBPF programs can access the same maps in parallel. It’s up to the user process and eBPF program to decide what they store inside maps.
eBPF 数据面中怎么应用 map
在 eBPF 数据面中，咱们应用 eBPF map 只须要依照标准定义 map 的构造，而后应用 bpf_map_lookup_elem、bpf_map_update_elem、bpf_map_delete_elem 等 helper function 就能够对 map 进行查问、更新、删除等操作。
上面以开源我的项目 cilium[2] 展现了一个 map 的应用例子：
1、map 的定义：定义全局的变量 ENDPOINTS_MAP，定义了 map 相干属性，比方类型 hash、key value 的大小、map 的大小等等。
struct bpf_elf_map __section_maps ENDPOINTS_MAP = {
.type = BPF_MAP_TYPE_HASH,
.size_key = sizeof(struct endpoint_key),
.size_value = sizeof(struct endpoint_info),
.pinning = PIN_GLOBAL_NS,
.max_elem = ENDPOINTS_MAP_SIZE,
.flags = CONDITIONAL_PREALLOC,
};2、查问 map：
static __always_inline __maybe_unused struct endpoint_info *
__lookup_ip4_endpoint(__u32 ip)
{struct endpoint_key key = {};
key.ip4 = ip;
key.family = ENDPOINT_KEY_IPV4;
return map_lookup_elem(&ENDPOINTS_MAP, &key);
}能够看到：map_lookup_elem 帮忙函数只须要传入 &ENDPOINTS_MAP 和 key 即可。
那么问题来了：
- 在内核态中 ENDPOINTS_MAP 的内存是怎么调配的？
- 内核态不同的 eBPF 程序怎么复用同一个 ENDPOINTS_MAP，每个程序怎么拿到 ENDPOINTS_MAP 的内存地址？
- 用户态程序又是怎么应用 map，怎么关联上 ENDPOINTS_MAP 并对其进行操作？
03 eBPF map 原理
eBPF 加载器与 map
eBPF 编程绕不开的是：将编写好的 eBPF 程序加载到内核，而后在内核态执行 eBPF 程序。因而须要有一个加载器将 eBPF 程序以及程序应用的 eBPF map 加载到内核中（或者复用已存在的 map）。
eBPF 加载器介绍
eBPF 程序加载的实质是 BPF 零碎调用，Linux 内核通过 BPF 零碎调用提供 eBPF 相干的所有操作，比方：程序加载、map 创立删除等。常见的 loader 都是对这个零碎调用的封装，局部 loader 提供更加原生靠近零碎调用的操作，局部 loader 则是进行了更多封装使得编程更便捷。上面介绍一下常见的 loader。
iproute2
iproute2[3] 提供 ip 命令、tc 命令将 eBPF 程序加载到内核并挂载到网口，提供更多封装能力。开发者只须要实现 eBPF 代码，应用 ip/tc 命令指定挂载的 eBPF 程序和挂载的网口即可。
static __always_inline __maybe_unused struct endpoint_info *
__lookup_ip4_endpoint(__u32 ip)
{struct endpoint_key key = {};
key.ip4 = ip;
key.family = ENDPOINT_KEY_IPV4;
return map_lookup_elem(&ENDPOINTS_MAP, &key);
}iproute2 提供了更便当的应用形式，比方：下面看到定义的 ENDPOINTS_MAP 中，定义了 pinning 属性为 PIN_GLOBAL_NS。iproute2 就会将这个 map pin 到 eBPF 文件系统中，如果 eBPF 文件系统已存在一个 pinned 的 map 则间接复用，实现多个程序共享一个 map 的成果。
典型案例：cilium 我的项目应用 iproute2 加载 BPF 程序。
libbpf 库
内核实现的 libbpf 库[4]，封装了 BPF 零碎调用，使得加载 BPF 程序更便捷。libbpf 不像 iproute2，它可能使 BPF 相干操作更为便捷，没有做过多封装。如果要将程序加载到内核，则须要本人实现一个用户态程序，调用 libbpf 的 API 去加载到内核。如果要复用 pinned 在 BPF 文件系统的 MAP，也须要用户态程序调用 libbpf 的 API，在加载程序时进行相干解决。
典型案例：Facebook 开源的 katran 我的项目应用 libbpf 加载 eBPF 程序。
cilium/ebpf 库
cilium/ebpf 库[5] 是一个 GO 语言版本的 libbpf 库，它封装了 BPF 零碎调用，与内核提供的 libbpf 相似。应用 cilium/ebpf 库实现用户态程序加载 eBPF 到内核，在很多方面都相似 libbpf，区别在于这个库是 GO 语言的，更加方便使用 GO 语言构建一套 eBPF 程序的管制面计划。
bcc
bcc[6] 实现了将用户态编译、加载、绑定的性能都集成了起来，不便用户应用，对用户的接口更敌对。反对 Python 接口以及很多基于 eBPF 实现的剖析工具。
BPF 零碎调用
Linux 内核通过 BPF 零碎调用并提供 BPF 相干的能力。对于 eBPF 编程中的 map，当然也有 BPF 零碎调用提供的能力。BPF 零碎调用定义：
SYSCALL_DEFINE3(bpf, int, cmd, union bpf_attr __user *, uattr, unsigned int, size)
{return __sys_bpf(cmd, USER_BPFPTR(uattr), size);
}BPF 零碎调用通过第一个参数 cmd 来辨别相干的 BPF 操作，map 常见的 cmd 有：创立 MAP、查问 MAP 中元素、更新 MAP 中元素、删除 MAP 中元素等等。cmd 如下：
enum bpf_cmd {
BPF_MAP_CREATE,
BPF_MAP_LOOKUP_ELEM,
BPF_MAP_UPDATE_ELEM,
BPF_MAP_DELETE_ELEM,
BPF_MAP_GET_NEXT_KEY,
// ...
}eBPF map 的创立
仔细的你可能曾经发现 BPF 零碎调用有一个 BPF_MAP_CREATE 的 cmd，这就能答复咱们下面的第一个问题：在内核中，ENDPOINTS_MAP 的内存是怎么调配的？
map 是须要调用 BPF 零碎调用来创立的。内核态的零碎调用执行过程有几步：
- 依据 MAP 类型，调用具体 MAP 类型的解决，并依据指定的 key size、value size、map size 调配内核态的内存；
- 为 MAP 调配惟一的 id；
- 为 MAP 创立一个匿名 fd，并返回；
在咱们的 eBPF 代码中，仅须要定义 map 全局变量，即可在代码中间接应用了，没有相干调用 bpf syscall 创立 map 的逻辑。那么其外部机制是怎么的？是 map 创立的过程而后由 loader 加载器实现的，编译器和加载器依据同一个约定实现这项工作。
下面 cilium 的例子中，ENDPOINTS_MAP 的全局变量定义时有一个关键字 __section_maps，这个关键字是一个宏，最终展现是 __attribute__((section(“maps”)))。这个编译器属性通知编译器将 ENDPOINTS_MAP 变量放在编译生成的 .o 文件 (elf) 中，名为 maps 的 section。
在应用 iproute2 加载程序时，关上 .o 文件时，会读取 maps 命名的 section，并将其中存储的一个个 map 读取进去，而后调用 BPF 零碎调用在内核创立 eBPF map。
如果是 libbpf 或 cilium/ebpf 库，须要调用 API 将 .o 文件关上，也反对相应的解析 elf 文件工作。并依据 API 调用标准，后续调用相干 API 创立 MAP。所以，这些 lib 库须要咱们本人实现用户态的程序加载 BPF 代码到内核，而 iproute2 齐全封装了这些流程。当然应用 lib 库可能更加灵便去做一些工作。
比方，在 libbpf 的 API bpf_object__open 关上 .o 文件的过程，就会解析文件中 section 名字为 maps 的段，将每个 map 解析进去。调用链：
bpf_object__open
__bpf_object__open_xattr
__bpf_object__open
bpf_object__init_maps
bpf_object__init_user_maps // 解析一个个 MAP另外有一个点值得注意，libbpf 和 iproute2 对 map 的构造定义是不一样的。libbpf 是：
struct bpf_map_def {
unsigned int type;
unsigned int key_size;
unsigned int value_size;
unsigned int max_entries;
unsigned int map_flags;
};而 iproute2 是：
struct bpf_elf_map {
__u32 type;
__u32 size_key;
__u32 size_value;
__u32 max_elem;
__u32 flags;
__u32 id;
__u32 pinning;
};能够看到 iproute2 的定义是减少了 id 和 pinning 两个字段，用于提供更加便捷的性能。比方：pinning 用于指定这个 map 是否须要 pin 到 BPF 文件系统，用于复用 map。
其实内核提供的 BPF 零碎调用，只须要 5 个要害属性作为参数（type/key_size/value_size/max_entries/map_flags），这个构造叫什么是什么并不重要，如果你本人实现 loader 来解析 .o 文件，也能够自定义 map 构造，只须要在 loader 最终调用 BPF 零碎调用时有这几个参数即可。
总结来说，loader 会调用 BPF 的零碎调用到内核创立 eBPF map，而后内核返回创立 map 的 fd。
eBPF 程序与 map 关联
咱们程序代码中间接应用 map 时，间接应用 map 全局变量，怎么与 loader 通过零碎调用创立的 map 关联？
事实上，程序拜访 map，要害的实现如下：
- 在 loader 加载 BPF 程序到内核之前，loader 都会先将所有定义在“maps”section 中的 map 创立在内核中（也可能是复用内核已有的 map），内核会返回 map 的 fd。
- loader 将内核返回的 map 的 fd，替换到应用的 map eBPF 指令的常量字段中，相当于间接批改编译后的 BPF 指令。
- loader 在指令替换 map fd 后，才会调用 cmd 为 BPF_PROG_LOAD 的 bpf syscall，将程序加载到内核。
- 内核在加载 eBPF 程序零碎调用过程中，会依据 eBPF 指令中常量字段存储的 MAP fd，找到内核态中的 map，而后将 map 内存地址替换到对应的 BPF 指令。
- 最终，BPF 程序在内核执行阶段能依据指令存储的内存地址拜访到 map。
下面一句话听起来有点形象，咱们将实现分析一下。
首先，在上文曾经介绍了 loader 会解析“maps”命名的 section，libbpf 会将 map 数据保留在一个 bpf_object 构造并返回。而后，用户态的程序还须要调用 libbpf 的 API bpf_object__load 将 bpf_object 构造真正加载到内核（注：iproute2 不须要你调用这么多 API，只须要依据其编码标准定义相干构造，而后它会帮你实现这所有）。
bpf_object__load API 对于 MAP 的解决调用链：
- 先依据解析好的 map，调用 BPF 零碎调用到内核创立 map；
- 将 map 的 fd 替换到 BPF 指令中；
- 采纳 BPF 程序（指令）调用 BPF 零碎调用将程序加载到内核；
bpf_object__load
bpf_object__load_xattr
bpf_object__create_maps // 将解析的 map 创立
bpf_object__relocate // 将 map 的 fd 替换到指令
bpf_object__load_progs // 将程序加载到内核
loader 是怎么将 map 的 fd 替换到指令中的呢？
在 BPF 程序编译后，生成的 .o 文件是可重定位的对象文件(Relocatable file)，在个别的程序编译过程中，还须要一步链接，链接器将各个指标文件组装在一起，解决符号依赖，库依赖关系，最终生成可执行文件。对于 BPF 编程来说，只须要生成 .o 文件，而后将文件加载到内核。对于 Loader，在将文件加载到内核前，会把 .o 文件中的 BPF 指令读取进去，解决 map 的“重定位”，而后再将指令加载到内核。Loader 算是实现了 map 的“链接”工作。
上面以一个程序理论例子来阐明 map 重定位过程，有趣味能够查看各个 loader 的实现，最终的后果是统一的。对于 BPF 编程，定义一个程序的格局会在函数前定义 SEC()。以 Facebook katran 代码为例子：
SEC("xdp-root")
int xdp_root(struct xdp_md *ctx) {return root_tail_call(ctx, &root_array);
}
__attribute__((__always_inline__))
static inline int root_tail_call(struct xdp_md *ctx, void *root_array){#pragma clang loop unroll(full)
for (__u32 i = 0; i < ROOT_ARRAY_SIZE; i++) { // ROOT_ARRAY_SIZE 是 4
bpf_tail_call(ctx, root_array, i);
}
return XDP_PASS;
}而 SEC 宏：实际上是通知编译器将上面函数代码放到 .o 文件中以 NAME 命名的 section。
#define SEC(NAME) __attribute__((section(NAME), used))所以，通过 readelf -S 查看编译生成的 .o 文件，能够看到一个以 xdp-root 命名的 section，这个 section 寄存的就是 xdp_root 的 BPF 程序编译后的 BPF 指令。同时，咱们能够看到有一个 .rel 前缀加上 xdp-root 命名的 section，这个 section 寄存的就是 xdp-root 代码中须要重定位的符号 symbol。这个 .relxdp-root section 的头部信息能够看到 type 是 REL，Info 是 13（对应 xdp-root 的 section id）：
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[13] xdp-root PROGBITS 0000000000000000 00006740
00000000000000b0 0000000000000000 AX 0 0 8
[14] .relxdp-root REL 0000000000000000 00024388
0000000000000040 0000000000000010 67 13 8通过命令 readelf -x 14 能够将可重定位对象文件 (.o) 的 .relxdp-root section 读取进去：
Hex dump of section '.relxdp-root':
0x00000000 08000000 00000000 01000000 44030000 ............D...
0x00000010 30000000 00000000 01000000 44030000 0...........D...
0x00000020 58000000 00000000 01000000 44030000 X...........D...
0x00000030 80000000 00000000 01000000 44030000 ............D...依据 Section Headers 信息可知 .relxdp-root 这个 section 每个 entry 的大小是 0x10（16 字节），对应上述 Hex dump 进去的每一行的大小。所以 .relxdp-root section 共有 4 个 entry。
对应上述 dump 解决的数据，每一个重定位的 entry 的组成：
- 低 64 位是 offset，用于关联以后 entry 对应代码 section 中具体的指令。代码 section 指令地位到其 section 起始地址，偏移的长度 offset 等于这个 offset；
- 高 64 位是 Info，其中的低 32 位对应重定位 symbol 的 type，高 32 位对应重定位 symbol 的 index（在 symbol 表的 id）。
因为字节序问题，上述 dump 对应 entry 构造反过来看：
以第一个 entry 为例子：symbol index 是 44030000（字节序转换后：0x0344），通过 readelf -s 命令查看符号表 836(0x344) 对应的符号是 root_array，合乎咱们上 xdp-root 的代码。咱们看到重定向 entry 有 4 条，都是对应 root_array 符号，代码共 4 次循环调用 root_array 符号（BPF 编译会将循环展开）：
# readelf -s
Symbol table '.symtab' contains 847 entries:
Num: Value Size Type Bind Vis Ndx Name
836: 000000000000001c 28 OBJECT GLOBAL DEFAULT 19 root_array通过 readelf 间接将 xdp-root section 打印进去（都是 BPF 指令）：
Hex dump of section 'xdp-root':
NOTE: This section has relocations against it, but these have NOT been applied to this dump.
0x00000000 bf160000 00000000 18020000 00000000 ................
0x00000010 00000000 00000000 b7030000 00000000 ................
0x00000020 85000000 0c000000 bf610000 00000000 .........a......
0x00000030 18020000 00000000 00000000 00000000 ................
0x00000040 b7030000 01000000 85000000 0c000000 ................
0x00000050 bf610000 00000000 18020000 00000000 .a..............
0x00000060 00000000 00000000 b7030000 02000000 ................
0x00000070 85000000 0c000000 bf610000 00000000 .........a......
0x00000080 18020000 00000000 00000000 00000000 ................
0x00000090 b7030000 03000000 85000000 0c000000 ................
0x000000a0 b7000000 02000000 95000000 00000000 ................依据第一个重定位 entry 的 offset 是 08000000 00000000（字节序转换后是 0x8），找到对应指令（编译后 .o 文件中的 BPF 指令都是 8 字节为单位）：18020000 00000000。
在编译后的汇编指令构造是：
struct bpf_insn {
__u8 code; /* opcode */
__u8 bpf_registers; /* dest & source register */
__s16 off; /* signed offset */
__s32 imm; /* signed immediate constant */
};
18020000 00000000 指令的 opcode 是 0x18。opCode 意义是：load memory、immediate value、size 是 double(64 bits)，用于拜访 map 的指令。在 loader 层面对于依据重定向 entry 找到的指令，且这个重定向 entry 关联的 symbol 是 map 状况下，会将 map 的 fd 写到这条指令的常量字段(imm)，并将指令的 src 寄存器设置为 BPF_PSEUDO_MAP_FD。最终，loader 将程序加载到内核时，对于拜访 map 的 BPF 指令的常量字段就存储了 map 的 fd。
内核零碎调用的解决
加载 eBPF 程序的零碎调用处理过程中，会针对替换到指令的 map fd 进行解决，将其改为 MAP 的内存地址。
零碎调用 eBPF 程序加载调用过程中，会调用 resolve_pseudo_ldimm64 函数：遍历全副指令，找到拜访 MAP 的指令（opcode 是 0x18、src_reg 是 1），将 MAP 的 fd 替换为 MAP 的内存地址（写到指令的常量字段），这样 BPF 指令执行过程中就能间接拜访 MAP。外围代码：
static int resolve_pseudo_ldimm64(struct bpf_verifier_env *env){
struct bpf_insn *insn = env->prog->insnsi;
int insn_cnt = env->prog->len;
int i, j, err;
for (i = 0; i < insn_cnt; i++, insn++) { // 遍历全副指令
if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) { // opcode 是 0x18
struct bpf_map *map;
struct fd f;
u64 addr;
u32 fd
// ... 校验逻辑
switch (insn[0].src_reg) {
case BPF_PSEUDO_MAP_IDX_VALUE:
case BPF_PSEUDO_MAP_IDX:
// ...
default:
fd = insn[0].imm; // 重常量字段拿到 loader 写入的 MAP 的 fd
break;
}
f = fdget(fd); // 依据 fd 找到 f
map = __bpf_map_get(f); // 创立 map 时，会将 map 指针存储到 file 的 private_data 中
if (insn[0].src_reg == BPF_PSEUDO_MAP_FD ||
insn[0].src_reg == BPF_PSEUDO_MAP_IDX) {addr = (unsigned long)map; // 拿到 map 的内存地址（内核态）}
insn[0].imm = (u32)addr; // 将 64 位内存地址别离存储到两条指令的常量字段，这也解释了下面汇编看到的 0x18 code 的 8 字节指令前面紧跟 8 字节全 0 指令的意义
insn[1].imm = addr >> 32;
// ...
insn++;
i++;
continue;
}
}
/* now all pseudo BPF_LD_IMM64 instructions load valid
* 'struct bpf_map *' into a register instead of user map_fd.
* These pointers will be used later by verifier to validate map access.
*/
return 0;
}eBPF map 原理小结
联合上述的剖析，能够说 eBPF map 是编译器、加载器、Linux 内核协同实现的。
- 编译器标准了咱们的编码方式，比方须要定义 map 寄存在命名为 maps 的 section。
- 加载器束缚了 map 定义的构造，并且会解析 .o 文件在内核创立 map，同时实现“重定位”性能将 map 的 fd 写到相干指令的常量，再将程序指令加载到内核。
- 内核依据 fd 找到 map 的内存地址，再替换到指令中，最终 bpf 指令执行时可能依据内存地址间接拜访 map。比方，咱们应用 bpf_map_lookup_elem helper 来查问 map，在内核中就能间接拿到 map 的内存地址进行拜访。
另外，多个 eBPF 程序共享一个 MAP 的原理也就不难理解了：
- 内核提供了一个 BPF 文件系统，咱们能够将 map pin 到文件系统中，而后多程序就能在文件系统找到 MAP 的 fd（不同程序返回不同的 fd，对应的 MAP 是同一个 id）。
- 在 loader 层面将共享的 map 的 fd 写到程序指令的常量，内核零碎调用解决时将对应 map 的地址替换给指令，最终指令执行就能拜访到 map。
- 不同的 BPF 程序拜访同一个内存地址，就实现了 map 的共享，最终能够构建更为简单的 eBPF 程序。
04 eBPF map 性能
eBPF map 位于在内核的内存中，eBPF 程序在执行时是间接拜访内存的，一般来说咱们通过 helper function 来拜访 map，比方查问 map 是通过 bpf_map_lookup_elem。不同类型的 map 查问、更新、删除的实现都是不同的，性能也是差异很大，针对不同场景应用不同类型的 map，以及理解不同 map 性能差别对于 eBPF 编程来说相当重要。
这里给出通过测试验证的论断及倡议：
- 一般来说 eBPF 程序作为数据面更多是查问，罕用的 map 的查问性能：array > percpu array > hash > percpu hash > lru hash > lpm。map 查问对 eBPF 性能有不少的影响，比方：lpm 类型 map 的查问在咱们测试发现最大影响 20% 整体性能、lru hash 类型 map 查问影响 10%。
- 特地留神，array 的查问性能比 percpu array 更好，hash 的查问性能也比 percpu hash 更好 ，这是因为 array 和 hash 的 lookup helper 层面在内核有更多的优化。 对于数据面读多写少状况下，应用 array 比 percpu array 更优（hash、percpu hash 同理），而对于须要数据面写数据的状况应用 percpu 更优，比方统计计数。
- 尽可能在一个 map 中查问到更多的数据，缩小 map 查问次数。
- 尽可能应用 array map，在管制面实现更简单的逻辑，如调配一个 index，将一些 hash map 查问转换为 array map 查问。
- eBPF map 也能够指定 numa 创立，另外不同类型的 map 也会有一些额定的 flags 能够用来调整个性，比方：lru hash map 有 no_common_lru 选项来优化写入性能。
05 总结
通过上述原理的分析以及理论的性能测试调优，咱们对于如何写好 eBPF 程序有了更粗浅的了解。在此基础之上，咱们通过 eBPF 实现了一套高性能高可用的云原生网络解决方案，欢送大家应用火山引擎边缘计算相干产品。也欢送优良的你退出咱们，摸索有限可能。
Tips：岗位详情及简历投递请微信分割火山引擎边缘计算小助手（微信：19117352830）！
参考资料：
[1] https://man7.org/linux/man-pa…
[2] https://github.com/cilium/cilium
[3] https://github.com/shemminger…
[4] https://github.com/torvalds/l…
[5] https://github.com/cilium/ebpf
[6]https://github.com/iovisor/bcc