BPF_MAP_TYPE_HASH，带 PERCPU 和 LRU 变体¶
注意
BPF_MAP_TYPE_HASH在内核版本 3.19 中引入BPF_MAP_TYPE_PERCPU_HASH在版本 4.6 中引入BPF_MAP_TYPE_LRU_HASH和BPF_MAP_TYPE_LRU_PERCPU_HASH都在版本 4.10 中引入
BPF_MAP_TYPE_HASH 和 BPF_MAP_TYPE_PERCPU_HASH 提供通用哈希映射存储。键和值都可以是结构体，允许复合键和值。
内核负责分配和释放键/值对，直到您指定的最大条目限制。哈希映射默认使用哈希表元素的预分配。BPF_F_NO_PREALLOC 标志可用于在内存开销过大时禁用预分配。
BPF_MAP_TYPE_PERCPU_HASH 为每个 CPU 提供一个单独的值槽。每个 CPU 的值内部存储在一个数组中。
BPF_MAP_TYPE_LRU_HASH 和 BPF_MAP_TYPE_LRU_PERCPU_HASH 变体为其各自的哈希表添加了 LRU 语义。当哈希表达到容量时，LRU 哈希将自动逐出最近最少使用的条目。LRU 哈希维护一个内部 LRU 列表，用于选择要逐出的元素。此内部 LRU 列表在 CPU 之间共享，但在调用 bpf_map_create 时，可以使用 BPF_F_NO_COMMON_LRU 标志请求每个 CPU 的 LRU 列表。下表概述了 LRU 映射的属性，具体取决于映射类型和用于创建映射的标志。
标志 |
|
|
|---|---|---|
BPF_F_NO_COMMON_LRU |
每个 CPU 的 LRU，全局映射 |
每个 CPU 的 LRU，每个 CPU 的映射 |
!BPF_F_NO_COMMON_LRU |
全局 LRU，全局映射 |
全局 LRU，每个 CPU 的映射 |
用法¶
内核 BPF¶
bpf_map_update_elem()¶
long bpf_map_update_elem(struct bpf_map *map, const void *key, const void *value, u64 flags)
可以使用 bpf_map_update_elem() 辅助函数添加或更新哈希条目。此辅助函数原子地替换现有元素。flags 参数可用于控制更新行为
BPF_ANY将创建新元素或更新现有元素BPF_NOEXIST仅在元素不存在时创建新元素BPF_EXIST将更新现有元素
bpf_map_update_elem() 成功时返回 0，失败时返回负错误码。
bpf_map_lookup_elem()¶
void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
可以使用 bpf_map_lookup_elem() 辅助函数检索哈希条目。此辅助函数返回指向与 key 关联的值的指针，如果未找到条目，则返回 NULL。
bpf_map_delete_elem()¶
long bpf_map_delete_elem(struct bpf_map *map, const void *key)
可以使用 bpf_map_delete_elem() 辅助函数删除哈希条目。此辅助函数成功时返回 0，失败时返回负错误码。
每个 CPU 的哈希¶
对于 BPF_MAP_TYPE_PERCPU_HASH 和 BPF_MAP_TYPE_LRU_PERCPU_HASH，bpf_map_update_elem() 和 bpf_map_lookup_elem() 辅助函数自动访问当前 CPU 的哈希槽。
bpf_map_lookup_percpu_elem()¶
void *bpf_map_lookup_percpu_elem(struct bpf_map *map, const void *key, u32 cpu)
可以使用 bpf_map_lookup_percpu_elem() 辅助函数在特定 CPU 的哈希槽中查找值。返回与 cpu 上的 key 关联的值，如果未找到条目或 cpu 无效，则返回 NULL。
并发¶
存储在 BPF_MAP_TYPE_HASH 中的值可以由在不同 CPU 上运行的程序并发访问。自内核版本 5.1 起，BPF 基础设施提供了 struct bpf_spin_lock 来同步访问。参见 tools/testing/selftests/bpf/progs/test_spin_lock.c。
用户空间¶
bpf_map_get_next_key()¶
int bpf_map_get_next_key(int fd, const void *cur_key, void *next_key)
在用户空间中，可以使用 libbpf 的 bpf_map_get_next_key() 函数遍历哈希的键。通过调用 bpf_map_get_next_key() 并将 cur_key 设置为 NULL，可以获取第一个键。后续调用将获取当前键的下一个键。bpf_map_get_next_key() 成功时返回 0，如果 cur_key 是哈希中的最后一个键则返回 -ENOENT，失败时返回负错误码。
请注意，如果 cur_key 被删除，则 bpf_map_get_next_key() 将返回哈希表中的第一个键，这是不希望的。如果键删除与 bpf_map_get_next_key() 混用，建议使用批量查找。
示例¶
请参阅 tools/testing/selftests/bpf 目录以获取功能示例。下面的代码片段演示了 API 用法。
此示例演示如何声明一个带有结构体键和结构体值的 LRU 哈希。
#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>
struct key {
__u32 srcip;
};
struct value {
__u64 packets;
__u64 bytes;
};
struct {
__uint(type, BPF_MAP_TYPE_LRU_HASH);
__uint(max_entries, 32);
__type(key, struct key);
__type(value, struct value);
} packet_stats SEC(".maps");
此示例演示如何使用原子指令创建或更新哈希值
static void update_stats(__u32 srcip, int bytes)
{
struct key key = {
.srcip = srcip,
};
struct value *value = bpf_map_lookup_elem(&packet_stats, &key);
if (value) {
__sync_fetch_and_add(&value->packets, 1);
__sync_fetch_and_add(&value->bytes, bytes);
} else {
struct value newval = { 1, bytes };
bpf_map_update_elem(&packet_stats, &key, &newval, BPF_NOEXIST);
}
}
用户空间遍历上述声明的映射元素
#include <bpf/libbpf.h>
#include <bpf/bpf.h>
static void walk_hash_elements(int map_fd)
{
struct key *cur_key = NULL;
struct key next_key;
struct value value;
int err;
for (;;) {
err = bpf_map_get_next_key(map_fd, cur_key, &next_key);
if (err)
break;
bpf_map_lookup_elem(map_fd, &next_key, &value);
// Use key and value here
cur_key = &next_key;
}
}
内部实现¶
本文档的此部分面向 Linux 开发人员，描述了映射实现中不被视为稳定 ABI 的方面。以下细节可能会在内核的未来版本中发生变化。
BPF_MAP_TYPE_LRU_HASH 及其变体¶
更新 LRU 映射中的元素时，当映射容量达到上限时，可能会触发逐出行为。更新算法尝试了各种步骤来强制执行 LRU 属性，这些步骤对涉及以下操作尝试的其他 CPU 产生了越来越大的影响
尝试使用 CPU 本地状态批量操作
尝试从全局列表中获取
target_free空闲节点尝试从全局列表中拉取任何节点并将其从哈希映射中移除
尝试从任何 CPU 的列表中拉取任何节点并将其从哈希映射中移除
一次从全局列表借用的节点数量，target_free，取决于映射的大小。更大的批量大小会减少锁竞争，但也可能耗尽全局结构。该值在映射初始化时计算，通过将所有 CPU 的总保留限制在映射大小的一半来避免耗尽，最小值为单个元素，最大预算为每次 128 个。
此算法在下图中有视觉描述。有关相应操作的完整解释，请参阅 commit 3a08c2fd7634 (“bpf: LRU List”) 中的描述
BPF_MAP_TYPE_LRU_HASH 及其变体在映射更新期间的 LRU 哈希逐出。有关内核函数名称代码引用，请参阅点文件源。¶
映射更新从右上角的椭圆形“begin bpf_map_update()”开始，通过图表向下推进，最终结果可能是成功更新或带有各种错误代码的失败。右上角的图例提供了特定操作可能涉及的锁的指示符。这旨在作为推理映射争用如何影响更新操作的视觉提示，尽管映射类型和标志可能会根据上表中描述的逻辑影响这些锁的实际争用。例如，如果映射是使用类型 BPF_MAP_TYPE_LRU_PERCPU_HASH 和标志 BPF_F_NO_COMMON_LRU 创建的，则所有映射属性都将是每个 CPU 的。