BPF_MAP_TYPE_LPM_TRIE

LPM trie key와 prefix 특성

`BPF_MAP_TYPE_LPM_TRIE` 문서는 `GPL-2.0-only` 라이선스와 `Copyright (C) 2022 Red Hat, Inc.`를 명시합니다.

`BPF_MAP_TYPE_LPM_TRIE`는 IP address를 저장된 prefix set과 비교할 수 있는 longest prefix match algorithm을 제공합니다.

내부 data는 `prefixlen,data` pair를 key로 사용하는 unbalanced trie node에 저장됩니다. `data`는 network byte order, 즉 big endian으로 해석되므로 `data[0]`에 most significant byte가 저장됩니다.

LPM trie의 maximum prefix length는 8부터 2048까지 범위에서 8의 배수로 지정할 수 있습니다. Lookup과 update에 사용하는 key는 `struct bpf_lpm_trie_key_u8` 뒤에 `max_prefixlen/8` byte를 확장한 형태입니다.

• IPv4 address의 data length는 4 byte입니다.
• IPv6 address의 data length는 16 byte입니다.

LPM trie에 저장하는 value type은 user가 정의한 어떤 type도 사용할 수 있습니다.

Kernel BPF lookup, update, delete

주어진 data value에 대한 longest prefix entry는 다음 `bpf_map_lookup_elem()` helper로 찾습니다.

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

Helper는 가장 길게 일치하는 `key`에 연결된 value pointer를 반환하며 일치하는 entry가 없으면 `NULL`을 반환합니다.

Longest prefix lookup을 수행할 때 key의 `prefixlen`은 `max_prefixlen`으로 설정해야 합니다. 예를 들어 IPv4 address의 longest prefix match를 찾을 때는 `prefixlen = 32`로 지정합니다.

Prefix 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)

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

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

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

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

Userspace 접근과 trie 순회 순서

Userspace에서는 위와 같은 이름의 libbpf API를 사용하며 map은 `fd`로 식별합니다. LPM trie entry를 순회할 때는 다음 `bpf_map_get_next_key()` function을 사용합니다.

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

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

`bpf_map_get_next_key()`는 LPM trie의 leftmost leaf부터 순회합니다. 따라서 덜 구체적인 key보다 더 구체적인 key가 먼저 반환됩니다.

IPv4 LPM trie 선언과 lookup

Userspace LPM trie example은 `tools/testing/selftests/bpf/test_lpm_map.c`에 있습니다. 다음 BPF code는 IPv4 address prefix를 저장할 새 LPM trie를 선언합니다.

#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>

struct ipv4_lpm_key {
        __u32 prefixlen;
        __u32 data;
};

struct {
        __uint(type, BPF_MAP_TYPE_LPM_TRIE);
        __type(key, struct ipv4_lpm_key);
        __type(value, __u32);
        __uint(map_flags, BPF_F_NO_PREALLOC);
        __uint(max_entries, 255);
} ipv4_lpm_map SEC(".maps");

`struct ipv4_lpm_key`는 `prefixlen`과 32-bit address `data`를 담습니다. Map은 `BPF_MAP_TYPE_LPM_TRIE`, `BPF_F_NO_PREALLOC`, 최대 255개 entry로 선언됩니다.

다음 lookup function은 IPv4 address 전체 32 bit로 longest prefix match를 수행하기 위해 `prefixlen = 32`인 key를 만들고 `ipv4_lpm_map`을 조회합니다.

void *lookup(__u32 ipaddr)
{
        struct ipv4_lpm_key key = {
                .prefixlen = 32,
                .data = ipaddr
        };

        return bpf_map_lookup_elem(&ipv4_lpm_map, &key);
}

Userspace prefix 삽입과 순회

다음 userspace code는 address와 prefix length로 `ipv4_lpm_key`를 구성하고 `BPF_ANY` semantics로 IPv4 prefix entry를 LPM trie에 넣습니다.

int add_prefix_entry(int lpm_fd, __u32 addr, __u32 prefixlen, struct value *value)
{
        struct ipv4_lpm_key ipv4_key = {
                .prefixlen = prefixlen,
                .data = addr
        };
        return bpf_map_update_elem(lpm_fd, &ipv4_key, value, BPF_ANY);
}

다음 program은 LPM trie entry를 순회합니다. `cur_key = NULL`에서 시작해 next key를 얻고 해당 value를 lookup한 뒤 current key pointer를 갱신합니다.

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

void iterate_lpm_trie(int map_fd)
{
        struct ipv4_lpm_key *cur_key = NULL;
        struct ipv4_lpm_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;
        }
}