BPF_MAP_TYPE_HASH, with PERCPU and LRU Variants

Hash, per-CPU, LRU variant 개요

`BPF_MAP_TYPE_HASH` 문서는 `GPL-2.0-only`, `Copyright (C) 2022 Red Hat, Inc.`, `Copyright (C) 2022-2023 Isovalent, Inc.`를 명시합니다.

`BPF_MAP_TYPE_HASH`와 `BPF_MAP_TYPE_PERCPU_HASH`는 general-purpose hash map storage를 제공합니다. Key와 value 모두 struct일 수 있으므로 composite key와 composite value를 구성할 수 있습니다.

Kernel은 지정된 `max_entries` 한도까지 key/value pair를 할당하고 해제합니다. Hash map은 기본적으로 hash table element를 pre-allocation하며, memory 비용이 너무 크면 `BPF_F_NO_PREALLOC` flag로 이를 끌 수 있습니다.

`BPF_MAP_TYPE_PERCPU_HASH`는 CPU마다 별도의 value slot을 제공하며 per-CPU value는 내부 array에 저장됩니다.

`BPF_MAP_TYPE_LRU_HASH`와 `BPF_MAP_TYPE_LRU_PERCPU_HASH`는 각각의 hash table에 LRU semantics를 추가합니다. Capacity에 도달하면 internal LRU list를 사용해 least recently used entry를 자동으로 evict합니다.

기본 LRU list는 CPU 사이에서 공유됩니다. `bpf_map_create` 호출 시 `BPF_F_NO_COMMON_LRU`를 지정하면 per-CPU LRU list를 요청할 수 있습니다. Map type과 flag 조합별 특성은 다음과 같습니다.

Kernel BPF update, lookup, delete

Hash entry를 추가하거나 갱신할 때는 다음 `bpf_map_update_elem()` helper를 사용합니다. Existing element는 atomically 교체됩니다.

long bpf_map_update_elem(struct bpf_map *map, const void *key, const void *value, u64 flags)

Update behavior는 `flags` parameter로 제어합니다.

• `BPF_ANY`: 새 element를 만들거나 기존 element를 갱신합니다.
• `BPF_NOEXIST`: element가 없을 때만 새로 만듭니다.
• `BPF_EXIST`: 기존 element만 갱신합니다.

`bpf_map_update_elem()`은 성공하면 0, 실패하면 negative error를 반환합니다.

Hash entry를 가져올 때는 다음 `bpf_map_lookup_elem()` helper를 사용합니다.

void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)

Lookup은 `key`에 연결된 value pointer를 반환하며 entry가 없으면 `NULL`을 반환합니다.

Hash entry를 삭제할 때는 다음 `bpf_map_delete_elem()` helper를 사용합니다.

long bpf_map_delete_elem(struct bpf_map *map, const void *key)

Delete는 성공하면 0, 실패하면 negative error를 반환합니다.

Per-CPU slot과 concurrency

`BPF_MAP_TYPE_PERCPU_HASH`와 `BPF_MAP_TYPE_LRU_PERCPU_HASH`에서 `bpf_map_update_elem()` 및 `bpf_map_lookup_elem()`은 현재 CPU의 hash slot에 자동으로 접근합니다.

특정 CPU의 slot을 조회하려면 다음 `bpf_map_lookup_percpu_elem()` helper를 사용합니다.

void *bpf_map_lookup_percpu_elem(struct bpf_map *map, const void *key, u32 cpu)

Helper는 지정한 `cpu`에서 `key`에 연결된 value를 반환합니다. Entry가 없거나 `cpu`가 유효하지 않으면 `NULL`을 반환합니다.

`BPF_MAP_TYPE_HASH`의 value는 서로 다른 CPU에서 실행되는 program이 동시에 접근할 수 있습니다. `Kernel version 5.1`부터 BPF infrastructure는 access synchronization을 위한 `struct bpf_spin_lock`을 제공하며 예제는 `tools/testing/selftests/bpf/progs/test_spin_lock.c`에 있습니다.

Userspace key 순회

Userspace에서는 libbpf의 다음 `bpf_map_get_next_key()` function으로 hash key를 순회할 수 있습니다.

int bpf_map_get_next_key(int fd, const void *cur_key, void *next_key)

첫 key는 `cur_key`를 `NULL`로 지정해 가져옵니다. 이후 호출은 current key 다음의 key를 반환합니다. 성공 시 0, `cur_key`가 마지막 key이면 `-ENOENT`, 그 밖의 실패에는 negative error를 반환합니다.

순회 중 `cur_key`가 삭제되면 `bpf_map_get_next_key()`는 hash table의 첫 key를 반환하므로 바람직하지 않습니다. Key 삭제가 순회와 섞일 수 있다면 batched lookup을 사용하는 것이 권장됩니다.

LRU hash 선언과 update·순회 예제

Functional example은 `tools/testing/selftests/bpf` directory에 있으며 다음 snippet은 API 사용법을 보여 줍니다. 첫 예제는 struct key와 struct value를 갖는 LRU hash `packet_stats`를 선언합니다.

#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");

다음 `update_stats()`는 먼저 `packet_stats`에서 source IP key를 조회합니다. Existing value가 있으면 `__sync_fetch_and_add()` atomic instruction으로 packet과 byte counter를 더하고, 없으면 `BPF_NOEXIST`로 새 value를 만듭니다.

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);
        }
}

다음 userspace code는 앞서 선언한 map의 element를 순회합니다. `cur_key = NULL`에서 시작해 next key를 얻고 value를 lookup한 뒤 current key pointer를 갱신합니다.

#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;
        }
}

LRU eviction 내부 동작

이 절은 Linux developer를 위한 implementation 설명이며 stable ABI가 아닙니다. 세부 동작은 이후 kernel version에서 바뀔 수 있습니다.

LRU map이 capacity에 도달한 상태에서 element를 update하면 eviction이 일어날 수 있습니다. Algorithm은 다른 CPU에 미치는 영향이 점차 커지는 다음 순서로 LRU property를 유지하려고 시도합니다.

• CPU-local state를 사용해 operation을 batch합니다.
• Global list에서 `target_free`개의 free node를 가져옵니다.
• Global list에서 임의의 node를 가져와 hashmap에서 제거합니다.
• 임의 CPU의 list에서 node를 가져와 hashmap에서 제거합니다.

한 batch에서 global list로부터 빌리는 node 수 `target_free`는 map size에 따라 정해집니다. 큰 batch는 lock contention을 줄이지만 global structure를 고갈시킬 수 있으므로, 모든 CPU의 총 reservation이 map size 절반을 넘지 않게 init 시 계산합니다. 최소 한 element, 한 번에 최대 128개가 budget입니다.

Commit `3a08c2fd7634` (`bpf: LRU List`)는 다음 update flow의 operation을 자세히 설명합니다.

원문의 `map_lru_hash_update.dot` kernel figure는 `BPF_MAP_TYPE_LRU_HASH`와 variant의 map update 중 LRU eviction 단계를 나타내며 kernel function name code reference를 포함합니다.

Update는 오른쪽 위의 `begin bpf_map_update()` oval에서 시작해 아래쪽의 성공 또는 여러 error code로 진행합니다. Graph의 key는 각 operation에 관여할 수 있는 lock을 표시해 contention을 추론하도록 돕습니다.

실제 lock contention은 map type과 flag에 따라 달라집니다. 예를 들어 `BPF_MAP_TYPE_LRU_PERCPU_HASH`에 `BPF_F_NO_COMMON_LRU`를 지정하면 모든 map property가 per-CPU가 됩니다.