BPF 映射类型 | 糖醋鱼的小破站

type

Post

status

Published

slug

2022/12/17/BPF Mapping type

summary

1 晗希表映射

哈希表映射是添加到 BPF 中的第一个通用映射。映射类型定义为 BPF_MAP_TYPE_HASH 。它们与你熟悉的哈希表在实现和用法上相似。该映射可以使用任意大小的键和值，内核会按需分配和释放它们。当在哈希表映射上使用 bpf_map_update_elem 时，内核会自动更新元素。

哈希表映射经过了优化，可以非常快速地进行查找，这对于经常被读取的结构化的数据很有用。让我们看一个用来跟踪网络 IP 及其速率限制的示例程序：


#define IPV4_FAMILY 1
struct ip_key {
  union {
    __u32 v4_addr;
    __u8 v6_addr[16];
  }; 
  __u8 family;
};

struct bpf_map_def SEC("maps") counters = {
      .type = BPF_MAP_TYPE_HASH,
      .key_size = sizeof(struct ip_key),
      .value size = sizeof(uint64_t),
      .max_entries = 100,
      .map_flags = BPF_F_NO_PREALLOC
};

在该代码中，我们声明了结构化的键，用它来保留 IP 地址信息。程序中将使用该映射来跟踪速率限制。我们在该映射中将 IP 地址作为键。映射的值是 BPF 程序从特定 IP 地址上接收网络数据包的次数。

让我们写一个小代码片段来更新内核中 counters 的值:


uint64_t update_counter(uint32_t ipV4) {
  uint64_t value;
  struct ip_key key = {};
  key.v4_addr = ip4;
  key.family = IPV4_FAMILY;
  bpf_map_lookup_elem(counters, &key, &value);
  (*value) += 1;
}

该函数从网络数据包中提取 IP 地址，井使用声明的复合键对映射进行查找。这里，我们假设之前初始化 counters 设置为零；否则， bpf_map_lookup_elem 调用将返回负数。

2 数组映射

数组映射是添加到内核的第二个 BPF 映射。映射类型定义为 BPF_MAP_TYPE_ARRAY 。对数组映射初始化时，所有元素在内存中将预分配空间井设置为零。因为映射由切片元素组成，键是数组中的索引，大小必须恰好为四个字节。

使用数组映射的一个缺点是映射中的元素不能删除，无法使数组变小。如果在数组映射上使用 bpf_map_delete_elem ，调用将失败，得到 EINVAL 错误。

数组映射通常用于保存值可能会更新的信息，但是行为通常固定不变。例如，我们通常使用数组映射保存预分配的全局变量。由于无法删除元素，可以假设特定位置的元素总是代表相同的元素。

需要记住的另一点是类似于哈希表映射，数组映射上使用的 bpf_map_update_elem 不是原子性的。如果程序执行更新操作，程序在相同的时间从相同位置上能读取不同的值。如果将计数器保存在数组映射中，你可以使用内核的内置函数 __sync _fetch_and_add 来对映射的值执行原子性操作。

3 程序数组映射

程序数组映射是添加到内核的第一个专用映射。映射类型定义为 BPF_MAP_TYPE_PROG_ARRAY 。这种类型保存对 BPF 程序的引用，即 BPF 程序的文件描述符。程序数组映射类型可以与帮助函数 bpf_tail_call 结合使用，实现在程序之间跳转，突破单个 BPF 程序最大指令的限制，并且可以降低实现的复杂性。

使用这个专用映射时，你要考虑如下事情。首先要记住的是键和值的大小都必须为四个字节。第二点要记住的是当跳到新程序时，新程序将使用相同的内存栈，因此程序不会耗尽所有有效的内存。最后，如果跳转到映射中不存在的程序，尾部调用将失败，返回继续执行当前程序。

让我们深入研究一个详细示例，来了解如何更好地使用这种类型的映射 :


struct bpf_map_def SEC( " maps") programs {
  .type = BPF_MAP_TYPE_PROG_ARRAY,
  .key_size = 4,
  .value size = 4,
  .max entries = 1024,
};

首先，我们需要声明新的程序映射，如前所述，键和值大小将为四个字节 :


int key = 1;
struct bpf_insn prog[] = {
  BPF_MOV64_IMM(BPF_REGO，o)，// assign ro=o
  BPF_EXIT_INSN()， // return ro
};
prog_fd = bpf_prog_load(BPF_PROG_TYPE_KPROBE，prog，sizeof(prog)，"GPL");
bpf_map_update_elem(&programs，&key，&prog_fd，BPF_ANY);

随后，我们需要声明要跳转到的程序。这里，我们编写一个 BPF 程序，程序唯一的目的是返回 0 。使用 bpf_prog_load 将它加载到内核中，然后将程序的文件描述符添加到程序映射中。现在我们已经有了一个程序，可以编写另一个 BPF 程序跳到它。只有相同类型的 BPF 程序才能跳转。这里，我们会将程序附加到 kprobe 跟踪上，像第 2 章中介绍的那样 :


SEC("kprobe/seccomp_phase1")
int bpf_kprobe_program(struct pt_regs *ctx) {
  int key=1;/* dispatch into next BPF program */
  bpf_tail_call(ctx，&programs，&key);

  /* fall through when the program descriptor is not in the map */
  char fmt[] ="missing program in prog_array map\n";
  bpf_trace_printk(fmt，sizeof(fmt));
  return 0;
}

这里我们使用 bpf_tail_call 和 BPF_MAP_TYPE_PROG_ARRAY ，可以最多达到 32 次嵌套调用。这个明确的限制可以防止无限循环和内存耗尽。

4 Perf 事件数组映射

这种类型映射将 perf_events 数据存储在环形缓存区中，用于 BPF 程序和用户空间程序进行实时通信。映射类型定义为 BPF_MAP_TYPE_PERF_EVENT_ARRAY。它可以将内核跟踪工具发出的事件转发给用户空间程序，以便做进步处理。这是非常有用的映射类型之一，它是许多可观测性工具的基础。通过这种类型映射，用户空间程序可以充当侦听器来侦听内核的事件，在这种情况下，你需要确保代码在内核 BPF 程序初始化之前开始侦听。

下面让我们看一个 Perf 事件数组映射的示例，该示例实现了对计算机上执行的所有程序进行跟踪。在进入 BPF 程序代码之前，我们需要声明内核发送到用户空间的 event 结构体:


struct data_t {
  u32 pid;
  char program_name[16];
};

现在，我们需要创建映射用来发送 event 到用户空间:


struct bpf_mapdef SEC("maps") events = {
  .type = BPF_MAP_TYPE_PERF_EVENT_ARRAY,
  .key_size = sizeof(int),
  .value size = sizeof(u32),
  .max entries = 2,
};

声明数据类型和映射后，我们可以创建 BPF 程序用来捕获数据并发送到用户空间 :


SEC("kprobe/sys_exec")
int bpf_capture_exec(struct pt_reg s *ctx) {
  data_t data;
  // bpf_get_current_pid_tgid returns the current process identifier
  data.pid bpf_get_current_pid_tgid()>> 32;
  // bpf_get_current_comm loads the current executable name 
  bpf_get_current_comm(&data.program_name, sizeof(data.program_name));
  bpf_perf_event_output(ctx, &events, 0, &data, sizeof(data));
  return 0;
}

在该代码段中，我们使用 bpf_perf_event_output 函数将 data 附加到映射上。由于映射是 BPF 程序和用户空间程序之间的实时缓存，所以不必担心映射中元素的键。内核负责将新元素添加到映射中，用户空间程序对其进行处理后会进行刷新。

5 单 CPU 哈希映射

这种类型的映射是 BPF_MAP_TYPE_HASH 的改进版本。映射类型定义为 BPF_MAP_TYPE_PERCPU_HASH 。我们可以给该类型映射分配 CPU ，那么每个 CPU 会看到自己独立的映射版本，这样对于高性能查找和聚合更有效。同时，对于在哈希表映射上收集指标和指标聚合的 BPF 程序，这种映射类型很有用。

6 单 CPU 数组映射

这种类型的映射也是 BPF_MAP_TYPE_ARRAY 的改进版本。映射类型定义为 BPF_MAP_TYPE_PERCPU_ARRAY 。像上一个映射一样，我们可以给该类型映射分配 CPU ，那么每个 CPU 会看到自己独立的映射版本，这样对于高性能查找和聚合更有效。

7 栈跟踪映射

这种类型的映射保存运行进程的钱跟踪信息。映射类型定义为 BPF_MAP_TYPE_STACK_TRACE 。同时，内核开发人员已经添加了帮助函数 bpf_get_stackid 用来帮助将栈跟踪信息写入该映射。该帮助函数会将映射作为参数，井附加特定的标志，以便你可以指定仅跟踪内核栈或用户空间栈信息，或者两个栈同时跟踪。该帮助函数将返回元素的键添加到映射中。

8 cgroup 数组映射

这种类型的映射保存对 cgroup 的引用。映射类型定义为 BPF_MAP_TYPE_CGROUP_ARRAY 。从本质上讲，它们的行为类似于 BPF_MAP_TYPE_PROG_ARRAY，只是它们存储指向 cgroup 的文件描述符。

当你要在 BPF 映射之间共享 cgroup 引用控制流量、调试和测试时，这种类型映射非常有用。让我们通过下面的示例看一下如何将信息写入这种映射类型。下面的示例从映射定义开始 :


struct bpf_map_def SEC("ma ps ") cgroups_map = {
  .type = BPF_MAP_TYPE_CGROUP_ARRAY,
  .key_size = sizeof(uint32_t),
  .value_size = sizeof(uint32_t),
  .max_entries = 1,
};

我们可以通过打开包含 cgroup 文件，获得 cgroup 内进程的文件描述符。我们将打开控制 Docker 容器的基本 CPU 共享的 cgroup ，并将 cgroup 内进程的文件描述符保存到映射中:


int cgroup_fd, key = 0;
cgroup_fd = open("/sys/fs/cgroup/cpu/docker/cpu.shares", O_RDONLY);
bpf_update_elem(&cgroups_map, &key, &cgroup_fd, 0);

9 LRU 晗希和单 CPU 的 LRU 晗希映射

这两种映射都是哈希表映射，同时它们还实现了内部 LRU 缓存。 LRU 代表最近最少使用的元素，如果映射已满，则会删除映射中不经常使用的元素，为映射中的新元素留出空间。因此，这种映射可以插入超出最大限制的元素，只要不介意最近不经常使用的元素被删除。该映射类型被分别定义为 BPF_MAP_TYPE_LRU_HASH 和 BPF_MAP_TYPE_LRU_PERCPU_HASH 。

这种映射的每个 CPU 版本与之前看到的其他每个 CPU 映射略有不同。该映射仅保留一个哈希表来存储映射中的所有元素，每个 CPU 使用不同的 LRU 缓存，这样可以确保每个 CPU 中最常用的元素保存在映射中。

10 LPM Tire 映射

LPM Tire 映射是使用最长前缀匹配 (LPM) 算陆来查找映射元素。LPM 是一种使用最长查找项选择树中元素的算法。此算法用于路由器和其他设备的流量转发表上，用来匹配 IP 地址到特定的路由表项上。映射类型被定义为 BPF_MAP_TYPE_LPM_TRIE。

该映射要求键大小为 8 的倍数，范围从 8 到 2048 。如果你不想实现自己的键，内核会提供一个结构 bpf_lpm_trie_key ，可以使用这些键。

下一个示例中，我们向映射添加三条转发路由，井匹配 IP 地址到正确路由上。首先，我们需要创建映射:


struct bpf_map_def SEC("maps") routing_map {
  .type = BPF_MAP_TYPE_LPM_TRIE,
  .key_size = 8,
  .value_size = sizeof(uint64_t),
  .max_entries = 10000,
  .map_flags = BPF_F_NO_PREALLOC,
};

我们将以下三条转发路由写入此映射 192.168.0.0/16 、 192.168.0.0/24 和 192.168.1.0/24


uint64_t value 1 = 1;
struct bpf_lpm_trie_key route_1 = {.data = {192, 168, 0, 0}, .prefixlen = 16};
uint64_t value_2 = 2;
struct bpf_lpm_trie_key route_2 = {.data = {192, 168, 0, 0}, .prefixlen = 24};
uint64_t value_3=3;
struct bpf_lpm_trie_key route_3 = {.data = {192, 168, 1, 0}, .prefixlen = 24};

bpf_map_update_elem(&routing_map,&route_1,&value_1,BPF ANY);
bpf_map_update_elem(&routing_map,&route_2,&value_2,BPF_ANY);
bpf_map_update_elem(&routing_map,&route 3,&value_3,BPF_ANY);

现在，我们使用相同的键结构来查找路由表项匹配 IP 地址 192.168.1.1/32 :


uint64_t result;
struct bpf_lpm_trie_key lookup = {.data {192, 168, 1, 1}, .prefix1en 32};
int ret = bpf_map_lookup_e1em(&routing_map, &lookup, &resu1t);
if (ret == 0)
  printf("Va1ue read from the map: '%d'\n", result);

在此示例中， 192.168.0.0/24 和 192.168.1.0/24 都匹配查找的 IP 地址。因为 IP 地址在此两项范围内。由于此映射使用 LPM 算法，最终使用 192.168.1.0/24 作为键值。

11 映射数组和映射晗希

BPF_MAP_TYPE_ARRAY_OF_MAPS 和 BPF_MAP_TYPE_HASH_OF_MAPS 两种映射用来保存其他映射的引用。它们仅支持间接级别引用，因此不能使用它们来保存映射的映射的映射。这样可以确保不会意外存储无限链接的映射而浪费所有内存。

当你要运行时替换整个映射时，这种类型映射是非常有用的。如果所有映射是全局映射的子映射，则我们可以创建全状态快照。当内核对父映射进行更新操作时，首先要确保旧子映射的所有引用被删除之后，才能完成对父映射的更新操作。

12 设备映射的映射

这种特殊类型映射保存了对网络设备的引用。该映射类型定义为 BPF_MAP_TYPE_DEVMAP 。该映射对于在内核级别操作流量的网络应用很有用。你可以建立一个指向特定网络设备端口的虚拟映射，然后使用帮助函数 bpf_redirect_map 重定向网络数据包。

13 CPU 映射的映射

BPF_MAP_TYPE_CPUMAP 是另一种可以转发网络通信的映射类型。该映射用来保存宿主机中不同 CPU 的引用。跟上面的映射类型一样，它也可以与帮助函数 bpf_redirect_map 一起使用重定向数据包。但是该映射可以将数据包发送到不同的 CPU 上。你可以使用该映射为网络栈分配特定的 CPU ，以达到可伸缩性和隔离性。

14 打开套接字映射

BPF_MAP_TYPE_XSKMAP 是一种保存打开套接字引用的映射类型。跟上述映射类型一样，该映射对于在套接字之间转发数据包是很有用的。

15 套接字数组和哈希映射

BPF_MAP_TYPE_SOCKMAP 和 BPF_MAP_TYPE_SOCKHASH 是两种保存内核中打开套接宇引用的专用映射。跟上述映射类型一样，这种类型映射也可以与帮助函数 bpf_redirect_map 一起使用，在当前 XDP 程序到其他套接字的缓冲区之间转发套接字。

它们的主要区别是其中一个使用数组存储套接字，而另一个使用哈希表存储套接字。使用哈希表的优势是可以通过键直接访问套接字，无须遍历完整映射查找。内核中的套接字由五元组键标识。这五个元组包括建立双向网络连接的基本信息。当使用哈希映射时，你可以使用这个五元组作为查找键。

16 cgroup 存储和单 CPU 的 cgroup 存储映射

这两种映射类型用来帮助开发人员将 BPF 程序附加到 cgroup 上。像我们在第 2 章中介绍的 BPF 程序类型，你可以使用 BPF_PROG_TYPE_CGROUP_SKB 将 BPF 程序附加到 cgroup 上和从 cgroup 移除，并且使用特定 cgroup 来实现 BPF 程序运行时隔离。这两种映射类型分别被定义为 BPF_MAP_TYPE_CGROUP_STORAGE 和 BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE 。

从开发人员的角度来看，这两种类型的映射类似于哈希表映射。内核提供了一个结构帮助函数 bpf_cgroup_storage_key 可以为该映射生成包括 cgroup 节点标识和附件类型信息的键。你可以为映射添加任何值，只有附加到 cgroup 的 BPF 程序可以访问这些值。

这种映射有两个限制。首先是无法从用户空间创建映射中的新元素。内核中的 BPF 程序可以使用 bpf_map_update_elem 创建元素。但是，如果从用户空间使用该方法，在键不存在的情况下， bpf_map_update_elem 将失败， errno 设置为 ENOENT 。第二个限制是不能从该映射中删除元素， bpf_map_delete_elem 总会失败， errno 将被设置为 EINVAL 。与上面其他相似的映射相比，两种映射的主要不同是 BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE 保存每个 CPU 的哈希表。

17 重用端口套接字映射

这种特殊类型的映射用来保存对系统中开放端口的可重用套接字的引用。映射类型被定义为 BPF_MAP_TYPE_REUSEPORT_SOCKARRAY 。这种映射主要与 BPF_PROG_TYPE_SK_REUSEPORT 类型程序一起使用，可以决定如何过滤和处理网络设备的传入数据包。例如，即使两个套接字连接同一端口，我们也可以决定哪个数据包传入哪个套接字上。

18 队列映射

队列映射使用先进先出 (FIFO) 存储映射元素。映射类型被定义为 BPF_MAP_TYPE_QUEUE 。 FIFO 意味着当从映射中获取一个元素，返回是映射中存在时间最长的元素。 bpf 映射的帮助函数以一种可预测的方式来操作这个数据结构。使用 bpf_map_lookup_elem 时，这个映射始终会寻找映射中最旧的元素。使用 bpf_map_update_elem 时，映射会将元素添加到队列末尾，因此，我们需要先读取映射中其余元素，才能获取此元素。同样，你也可以使用帮助函数 bpf_map_lookup_and_delete来获取较旧的元素，然后保持原子性，将其从映射中删除。此映射不支持帮助函数 bpf_map_delete_elem 和 bpf_map_get_next_key。如果使用它们会失败， errno 变量设置为 EINVAL。

关于这种类型映射，你还需要记住如下事情:它们不能使用映射的键进行查找。初始化映射时，键的大小必须为零。元素写入映射时，键必须为空值。让我们看一个如何使用这种类型映射的示例:


struct bpf_map_def SEC("maps") queue_map ={
  .type = BPF_MAP_TYPE_QUEUE,
  .key_size =0,
  .value size = sizeof(int),
  .max entries = 100,
  .map_flags=0,
};

在此映射中插入几个元素，然后以插入的顺序获取它们 :


int i;
for (i=0;i<5;i++)
  bpf_map_update_elem(&queue_map,NULL,&i,BPF_ANY);

int value;
for (i=0;i<5;i++) {
  bpf_map_lookup_and_delete(&queue_map,NULL,&value);
  printf("Value read from the map:%d'\n", value);
}

该程序打印以下内容 :


Value read from the map: '0' 
Value read from the map: '1' 
Value read from the map: '2' 
Value read from the map: '3' 
Value read from the map: '4'

如果从映射中获取一个新元素， bpf_map_lookup_and_delete 将返回负数， errno 变量将设置为 ENOENT 。

19 栈映射

栈映射使用后进先出 (LIFO) 在映射中存储元素。映射类型定义为 BPF_MAP_TYPE_STACK。LIFO 意味着当从映射中获取一个元素，返回是最近添加到映射中的元素。

bpf 映射的帮助函数也以一种可预测的方式来操作这个数据结构。使用 bpf_map_lookup_elem 时，映射始终会寻找映射中的最新元素。使用 bpf_map_update_elem 时，映射始终会将元素添加到栈顶，因此，它可以被第一个获取。同时，也可以使用帮助函数 bpf_map_lookup_and_delete 获取最新元素并保持原子性，从映射中删除元素。该映射不支持帮助函数 bpf_map_delete_elem和bpf_map_get_next_key。如果使用它们会失败errno 变量设置为 EINVAL

让我们看一个如何使用此映射的示例:


struct bpf_map_def SEC("maps") stack_map ={
  .typ e= BPF_MAP_TYPE_STACK,
  .key_size=0,
  .value size = sizeof(int),
  .max entries = 100,
  .map_flags=0,
};

在此映射中插入几个元素，然后以插入相同的顺序获取它们:


int i;
for (i=0;i<5;i++)
  bpf_map_update_elem(&stack_map,NULL,&i,BPF_ANY);

int value;
for(i=0;i<5;i++) {
  bpf_map_lookup_and_delete(&stack_map,NULL，&value);
  printf("Value read from the map:%d'\n",value);
}

该程序打印以下内容:


Value read from the map: '4' 
Value read from the map: '3' 
Value read from the map: '2' 
Value read from the map: '1' 
Value read from the map: '0'

如果从映射中取出一个新元素， bpf_map_lookup_and_delete 将返回负数， errno 变量设置为 ENOENT。

至此，我们介绍了 BPF 程序使用的所有映射类型。你将发现某些映射类型更有用，这取决于你编写的程序类型。