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。
并发¶
运行在不同 CPU 上的程序可以并发访问存储在 BPF_MAP_TYPE_HASH 中的值。从内核版本 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 本地状态来批量操作
尝试从全局列表中获取空闲节点
尝试从全局列表中拉取任何节点，并将其从哈希映射中删除
尝试从任何 CPU 的列表中拉取任何节点，并将其从哈希映射中删除
此算法在以下图中以图形方式描述。有关相应操作的完整说明，请参阅 commit 3a08c2fd7634 (“bpf: LRU List”)。
BPF_MAP_TYPE_LRU_HASH 及其变体的映射更新期间的 LRU 哈希驱逐。有关内核函数名称代码引用，请参阅 dot 文件源。¶
映射更新从右上角的椭圆“开始 bpf_map_update()”开始，并通过图表向底部推进，其中结果可能是成功的更新或具有各种错误代码的失败。右上角的键提供了有关特定操作中可能涉及哪些锁的指示。这旨在作为一种视觉提示，用于推理映射争用如何影响更新操作，尽管映射类型和标志可能会基于上表中描述的逻辑影响这些锁上的实际争用。例如，如果使用类型 BPF_MAP_TYPE_LRU_PERCPU_HASH 和标志 BPF_F_NO_COMMON_LRU 创建映射，则所有映射属性都将是每个 CPU 的。