BPF_MAP_TYPE_ARRAY and BPF_MAP_TYPE_PERCPU_ARRAY

Array map 구조와 mmap 지원

`BPF_MAP_TYPE_ARRAY and BPF_MAP_TYPE_PERCPU_ARRAY` 문서는 `GPL-2.0-only` license를 따르며 `Copyright (C) 2022 Red Hat, Inc.`를 명시합니다.

`BPF_MAP_TYPE_ARRAY`와 `BPF_MAP_TYPE_PERCPU_ARRAY`는 generic array storage를 제공합니다. Key type은 4-byte unsigned 32-bit integer이고 map size는 고정입니다. Array size는 생성할 때 `max_entries`로 정하며 모든 element를 미리 allocate하고 zero initialize합니다.

`BPF_MAP_TYPE_PERCPU_ARRAY`는 CPU마다 서로 다른 memory region을 사용하지만 `BPF_MAP_TYPE_ARRAY`는 모든 CPU가 같은 region을 사용합니다. Value는 어떤 size든 저장할 수 있으나 모든 array element는 8 byte에 align됩니다.

Kernel 5.5부터 `BPF_F_MMAPABLE` flag를 설정해 `BPF_MAP_TYPE_ARRAY`의 memory mapping을 enable할 수 있습니다. Map definition은 page-aligned되어 첫 page에서 시작하고, 모든 array value를 담을 page-sized·page-aligned memory block은 두 번째 page부터 allocate됩니다. 경우에 따라 memory가 필요 이상으로 allocate될 수 있습니다.

Memory mapping을 사용하면 performance와 usability가 좋아집니다. Userspace program이 data에 접근하고 변경하기 위해 helper function을 호출하지 않아도 되기 때문입니다.

Kernel BPF lookup과 update helper

Kernel BPF에서 array element를 조회하는 helper prototype은 다음과 같습니다.

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

`bpf_map_lookup_elem()`은 array element 내부를 가리키는 pointer를 반환합니다. Userspace가 value를 읽는 동안 in-place update와 data race가 발생하지 않도록 `__sync_fetch_and_add()` 같은 primitive를 사용해야 합니다.

Array element를 update하는 helper prototype은 다음과 같습니다.

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

`bpf_map_update_elem()`은 성공하면 0을, 실패하면 negative error를 반환합니다. Array size가 고정이므로 `bpf_map_delete_elem()`은 지원하지 않습니다. Element를 clear하려면 해당 index에 zero value를 `bpf_map_update_elem()`으로 넣습니다.

Per-CPU array 접근

`BPF_MAP_TYPE_ARRAY`의 value는 서로 다른 CPU에서 실행되는 여러 program이 함께 접근할 수 있습니다. Storage를 한 CPU로 제한하려면 `BPF_MAP_TYPE_PERCPU_ARRAY`를 사용합니다.

`BPF_MAP_TYPE_PERCPU_ARRAY`에서 `bpf_map_update_elem()`과 `bpf_map_lookup_elem()`은 current CPU의 slot에 자동으로 접근합니다.

특정 CPU의 array value를 조회하는 helper prototype은 다음과 같습니다.

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

`bpf_map_lookup_percpu_elem()`은 지정한 CPU의 array value를 찾습니다. 성공하면 value를 반환하고 entry가 없거나 `cpu`가 invalid하면 `NULL`을 반환합니다.

Concurrency와 userspace API

Kernel 5.1부터 BPF infrastructure는 concurrent access를 synchronize하기 위한 `struct bpf_spin_lock`을 제공합니다.

Userspace에서는 위 helper와 같은 name의 libbpf API를 사용하며 map은 `fd`로 식별합니다.

Kernel BPF array 선언과 접근 예제

기능 예제는 `tools/testing/selftests/bpf` directory에 있습니다. 다음 code는 key `u32`, value `long`, `max_entries` 256인 `BPF_MAP_TYPE_ARRAY`를 `.maps` section에 선언합니다.

struct {
        __uint(type, BPF_MAP_TYPE_ARRAY);
        __type(key, u32);
        __type(value, long);
        __uint(max_entries, 256);
} my_map SEC(".maps");

다음 BPF program은 packet의 IP protocol을 index로 사용해 array element를 찾습니다. `bpf_skb_load_bytes()`로 IP header를 읽고 `bpf_map_lookup_elem()`으로 value pointer를 얻은 뒤 `__sync_fetch_and_add()`로 packet length를 atomic하게 더합니다.

int bpf_prog(struct __sk_buff *skb)
{
        struct iphdr ip;
        int index;
        long *value;

        if (bpf_skb_load_bytes(skb, ETH_HLEN, &ip, sizeof(ip)) < 0)
                return 0;

        index = ip.protocol;
        value = bpf_map_lookup_elem(&my_map, &index);
        if (value)
                __sync_fetch_and_add(value, skb->len);

        return 0;
}

Userspace array 생성·초기화·조회

Userspace의 첫 예제는 `bpf_map_create_opts`로 `BPF_F_MMAPABLE` flag를 설정하고 `bpf_map_create()`로 `BPF_MAP_TYPE_ARRAY`를 생성합니다. Key는 `__u32`, value는 `long`, 최대 entry 수는 256입니다.

#include <bpf/libbpf.h>
#include <bpf/bpf.h>

int create_array()
{
        int fd;
        LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_MMAPABLE);

        fd = bpf_map_create(BPF_MAP_TYPE_ARRAY,
                            "example_array",       /* name */
                            sizeof(__u32),         /* key size */
                            sizeof(long),          /* value size */
                            256,                   /* max entries */
                            &opts);                /* create opts */
        return fd;
}

다음 예제는 0부터 255까지 순회하면서 각 index와 같은 `long` value를 `BPF_ANY` flag로 저장합니다. Update가 실패하면 negative return value를 즉시 반환합니다.

int initialize_array(int fd)
{
        __u32 i;
        long value;
        int ret;

        for (i = 0; i < 256; i++) {
                value = i;
                ret = bpf_map_update_elem(fd, &i, &value, BPF_ANY);
                if (ret < 0)
                        return ret;
        }

        return ret;
}

마지막 array 예제는 index 42를 `bpf_map_lookup_elem()`으로 조회해 userspace buffer `value`에 받고 결과가 42인지 확인합니다.

int lookup(int fd)
{
        __u32 index = 42;
        long value;
        int ret;

        ret = bpf_map_lookup_elem(fd, &index, &value);
        if (ret < 0)
                return ret;

        /* use value here */
        assert(value == 42);

        return ret;
}

Userspace per-CPU array 예제

Per-CPU array를 initialize할 때 `libbpf_num_possible_cpus()`로 가능한 CPU 수를 구하고 `long values[ncpus]` buffer를 준비합니다. 각 map index마다 모든 CPU slot을 같은 값으로 채운 뒤 `bpf_map_update_elem()`에 전체 buffer를 전달합니다.

int initialize_array(int fd)
{
        int ncpus = libbpf_num_possible_cpus();
        long values[ncpus];
        __u32 i, j;
        int ret;

        for (i = 0; i < 256 ; i++) {
                for (j = 0; j < ncpus; j++)
                        values[j] = i;
                ret = bpf_map_update_elem(fd, &i, &values, BPF_ANY);
                if (ret < 0)
                        return ret;
        }

        return ret;
}

Per-CPU value를 조회할 때도 `ncpus` element를 담을 buffer를 전달합니다. 조회 후 각 CPU slot을 순회하여 index 42에 저장한 값이 모두 42인지 확인합니다.

int lookup(int fd)
{
        int ncpus = libbpf_num_possible_cpus();
        __u32 index = 42, j;
        long values[ncpus];
        int ret;

        ret = bpf_map_lookup_elem(fd, &index, &values);
        if (ret < 0)
                return ret;

        for (j = 0; j < ncpus; j++) {
                /* Use per CPU value here */
                assert(values[j] == 42);
        }

        return ret;
}

Per-CPU userspace semantics

Userspace에서 `BPF_MAP_TYPE_PERCPU_ARRAY`에 접근하면 각 map value는 `ncpus` element를 가진 array로 표현됩니다.

이 map type에 `bpf_map_update_elem()`을 호출할 때는 `BPF_NOEXIST` flag를 사용할 수 없습니다. 모든 element가 생성 시점에 이미 allocate되어 존재하기 때문입니다.