BPF cpumask kfuncs

BPF cpumask kfunc 소개

이 문서는 `GPL-2.0` license를 따르며 `cpumasks-header-label` anchor에서 BPF cpumask kfunc를 설명합니다.

`struct cpumask`는 index가 system의 CPU를 나타내는 kernel bitmap data structure입니다. cpumask의 일반적인 활용은 다음과 같습니다.

• task가 affinity를 갖는 CPU를 추적합니다.
• scheduling domain에 연결된 core를 추적합니다.
• machine에서 idle 상태인 core 등을 추적합니다.

BPF는 program이 cpumask를 allocate, mutate, query, free할 수 있도록 `kfuncs-header-label`에서 설명하는 kfunc 집합을 제공합니다.

BPF가 사용하는 두 cpumask object

BPF program에서 사용할 수 있는 cpumask type은 두 가지입니다.

`struct bpf_cpumask *`는 BPF program을 대신해 BPF가 allocate하며 lifecycle 전체를 BPF가 제어하는 cpumask입니다.

이 cpumask는 RCU-protected이고 mutate할 수 있으며 kptrs로 사용할 수 있습니다. 또한 `struct cpumask *`로 안전하게 cast할 수 있습니다.

struct bpf_cpumask lifecycle

`struct bpf_cpumask *`의 allocate, acquire, release에는 `kernel/bpf/cpumask.c`에서 문서화한 다음 function을 사용합니다.

• `bpf_cpumask_create`: 새 BPF cpumask를 allocate합니다.
• `bpf_cpumask_acquire`: 기존 BPF cpumask reference를 acquire합니다.
• `bpf_cpumask_release`: 보유한 BPF cpumask reference를 release합니다.

Cpumask 생성과 map kptr 저장 예제

다음 예제는 `struct bpf_cpumask __kptr *` field를 가진 array map을 정의하고 새 cpumask의 ownership을 map으로 이전합니다.

struct cpumask_map_value {
        struct bpf_cpumask __kptr * cpumask;
};

struct array_map {
        __uint(type, BPF_MAP_TYPE_ARRAY);
        __type(key, int);
        __type(value, struct cpumask_map_value);
        __uint(max_entries, 65536);
} cpumask_map SEC(".maps");

static int cpumask_map_insert(struct bpf_cpumask *mask, u32 pid)
{
        struct cpumask_map_value local, *v;
        long status;
        struct bpf_cpumask *old;
        u32 key = pid;

        local.cpumask = NULL;
        status = bpf_map_update_elem(&cpumask_map, &key, &local, 0);
        if (status) {
                bpf_cpumask_release(mask);
                return status;
        }

        v = bpf_map_lookup_elem(&cpumask_map, &key);
        if (!v) {
                bpf_cpumask_release(mask);
                return -ENOENT;
        }

        old = bpf_kptr_xchg(&v->cpumask, mask);
        if (old)
                bpf_cpumask_release(old);

        return 0;
}

/**
 * A sample tracepoint showing how a task's cpumask can be queried and
 * recorded as a kptr.
 */
SEC("tp_btf/task_newtask")
int BPF_PROG(record_task_cpumask, struct task_struct *task, u64 clone_flags)
{
        struct bpf_cpumask *cpumask;
        int ret;

        cpumask = bpf_cpumask_create();
        if (!cpumask)
                return -ENOMEM;

        if (!bpf_cpumask_full(task->cpus_ptr))
                bpf_printk("task %s has CPU affinity", task->comm);

        bpf_cpumask_copy(cpumask, task->cpus_ptr);
        return cpumask_map_insert(cpumask, task->pid);
}

`cpumask_map_insert()`는 먼저 null kptr를 가진 map value를 만들고 다시 lookup한 뒤 `bpf_kptr_xchg()`로 새 `mask`를 저장합니다. 교체된 `old` pointer가 있으면 `bpf_cpumask_release(old)`로 reference를 반환합니다. update나 lookup이 실패한 경로에서도 입력 `mask`를 release하므로 ownership leak이 없습니다.

`record_task_cpumask` tracepoint program은 `bpf_cpumask_create()`로 object를 만들고, `task->cpus_ptr`가 full mask인지 query한 뒤 `bpf_cpumask_copy()`로 task의 CPU affinity를 복사합니다. 마지막에는 `cpumask_map_insert()`가 task PID key에 kptr를 기록합니다.

Map kptr와 RCU 보호

위 예제처럼 `struct bpf_cpumask *` object는 map에 저장해 kptrs로 사용할 수 있습니다. map에 있는 reference는 `bpf_kptr_xchg()`로 제거하거나 RCU를 사용해 opportunistically acquire할 수 있습니다.

/* struct containing the struct bpf_cpumask kptr which is stored in the map. */
struct cpumasks_kfunc_map_value {
        struct bpf_cpumask __kptr * bpf_cpumask;
};

/* The map containing struct cpumasks_kfunc_map_value entries. */
struct {
        __uint(type, BPF_MAP_TYPE_ARRAY);
        __type(key, int);
        __type(value, struct cpumasks_kfunc_map_value);
        __uint(max_entries, 1);
} cpumasks_kfunc_map SEC(".maps");

/* ... */

/**
 * A simple example tracepoint program showing how a
 * struct bpf_cpumask * kptr that is stored in a map can
 * be passed to kfuncs using RCU protection.
 */
SEC("tp_btf/cgroup_mkdir")
int BPF_PROG(cgrp_ancestor_example, struct cgroup *cgrp, const char *path)
{
        struct bpf_cpumask *kptr;
        struct cpumasks_kfunc_map_value *v;
        u32 key = 0;

        /* Assume a bpf_cpumask * kptr was previously stored in the map. */
        v = bpf_map_lookup_elem(&cpumasks_kfunc_map, &key);
        if (!v)
                return -ENOENT;

        bpf_rcu_read_lock();
        /* Acquire a reference to the bpf_cpumask * kptr that's already stored in the map. */
        kptr = v->cpumask;
        if (!kptr) {
                /* If no bpf_cpumask was present in the map, it's because
                 * we're racing with another CPU that removed it with
                 * bpf_kptr_xchg() between the bpf_map_lookup_elem()
                 * above, and our load of the pointer from the map.
                 */
                bpf_rcu_read_unlock();
                return -EBUSY;
        }

        bpf_cpumask_setall(kptr);
        bpf_rcu_read_unlock();

        return 0;
}

예제는 map에 미리 저장된 `struct bpf_cpumask *` kptr를 lookup한 뒤 `bpf_rcu_read_lock()`으로 RCU read-side critical section에 들어갑니다. `v->cpumask`를 읽어 null이 아니면 `bpf_cpumask_setall(kptr)`에 전달하고 `bpf_rcu_read_unlock()`으로 나옵니다.

pointer가 null이면 map lookup과 pointer load 사이에 다른 CPU가 `bpf_kptr_xchg()`로 object를 제거한 race가 발생한 것입니다. 이 경로는 RCU lock을 해제하고 `-EBUSY`를 반환합니다.

struct cpumask와 안전한 cast 방향

`struct cpumask`는 실제로 query·mutate하는 cpumask bitmap을 담는 object입니다. `struct bpf_cpumask`가 내부에서 `struct cpumask`를 감싸므로 `struct bpf_cpumask *`를 `struct cpumask *`로 cast하는 것은 안전합니다.

반대 방향인 `struct cpumask *`에서 `struct bpf_cpumask *`로의 cast는 안전하지 않습니다. verifier는 이를 시도하는 program을 reject합니다.

cpumask argument를 mutate하는 kfunc는 해당 argument를 `struct bpf_cpumask *`로 받습니다. 단순히 cpumask를 query하는 argument는 `struct cpumask *`로 받습니다.

Mutation과 query kfunc 구분

앞 절에서는 `struct bpf_cpumask *`를 allocate, acquire, release하는 kfunc를 설명했습니다. 이 절에서는 cpumask를 mutate하고 query하는 kfunc를 다룹니다.

일부 cpumask kfunc는 argument를 변경하지 않는 read-only function이고, 다른 function은 하나 이상의 argument를 mutate합니다. mutate 대상은 앞서 설명한 대로 반드시 `struct bpf_cpumask *`여야 합니다.

이하의 mutation 절은 argument를 하나 이상 바꾸는 모든 cpumask kfunc를 설명하며, `cpumasks-querying-label` 절은 read-only kfunc를 설명합니다.

CPU bit와 전체 mask 설정·해제

`bpf_cpumask_set_cpu()`와 `bpf_cpumask_clear_cpu()`는 각각 `struct bpf_cpumask`에서 지정한 CPU bit를 set하거나 clear합니다. 두 function은 `kernel/bpf/cpumask.c`에서 kernel-doc으로 문서화됩니다.

다음 tracepoint 예제는 set, clear, query를 함께 보여 줍니다.

/**
 * A sample tracepoint showing how a cpumask can be queried.
 */
SEC("tp_btf/task_newtask")
int BPF_PROG(test_set_clear_cpu, struct task_struct *task, u64 clone_flags)
{
        struct bpf_cpumask *cpumask;

        cpumask = bpf_cpumask_create();
        if (!cpumask)
                return -ENOMEM;

        bpf_cpumask_set_cpu(0, cpumask);
        if (!bpf_cpumask_test_cpu(0, cast(cpumask)))
                /* Should never happen. */
                goto release_exit;

        bpf_cpumask_clear_cpu(0, cpumask);
        if (bpf_cpumask_test_cpu(0, cast(cpumask)))
                /* Should never happen. */
                goto release_exit;

        /* struct cpumask * pointers such as task->cpus_ptr can also be queried. */
        if (bpf_cpumask_test_cpu(0, task->cpus_ptr))
                bpf_printk("task %s can use CPU %d", task->comm, 0);

release_exit:
        bpf_cpumask_release(cpumask);
        return 0;
}

program은 cpumask를 만들고 CPU 0을 set한 뒤 `bpf_cpumask_test_cpu(0, cast(cpumask))`로 bit가 설정됐는지 확인합니다. 이어 CPU 0을 clear하고 다시 query합니다. `task->cpus_ptr`처럼 원래부터 `struct cpumask *`인 pointer도 직접 query할 수 있습니다. 모든 경로는 마지막에 `bpf_cpumask_release(cpumask)`를 호출합니다.

개별 bit와 전체 mask를 변경하는 관련 kfunc는 다음과 같습니다.

• `bpf_cpumask_test_and_set_cpu()`와 `bpf_cpumask_test_and_clear_cpu()`는 CPU bit를 atomic하게 test한 뒤 set 또는 clear합니다.
• `bpf_cpumask_setall()`은 `struct bpf_cpumask *`의 모든 bit를 한 operation으로 set합니다.
• `bpf_cpumask_clear()`는 `struct bpf_cpumask *` 전체를 한 operation으로 clear합니다.

Cpumask 사이의 bitwise operation과 copy

한 cpumask의 개별 CPU를 set·clear하는 것 외에도 caller는 여러 cpumask 사이에서 `bpf_cpumask_and()`, `bpf_cpumask_or()`, `bpf_cpumask_xor()`로 bitwise operation을 수행할 수 있습니다.

다음 예제에는 뒤에서 더 자세히 설명할 query kfunc도 일부 포함됩니다.

/**
 * A sample tracepoint showing how a cpumask can be mutated using
   bitwise operators (and queried).
 */
SEC("tp_btf/task_newtask")
int BPF_PROG(test_and_or_xor, struct task_struct *task, u64 clone_flags)
{
        struct bpf_cpumask *mask1, *mask2, *dst1, *dst2;

        mask1 = bpf_cpumask_create();
        if (!mask1)
                return -ENOMEM;

        mask2 = bpf_cpumask_create();
        if (!mask2) {
                bpf_cpumask_release(mask1);
                return -ENOMEM;
        }

        // ...Safely create the other two masks... */

        bpf_cpumask_set_cpu(0, mask1);
        bpf_cpumask_set_cpu(1, mask2);
        bpf_cpumask_and(dst1, (const struct cpumask *)mask1, (const struct cpumask *)mask2);
        if (!bpf_cpumask_empty((const struct cpumask *)dst1))
                /* Should never happen. */
                goto release_exit;

        bpf_cpumask_or(dst1, (const struct cpumask *)mask1, (const struct cpumask *)mask2);
        if (!bpf_cpumask_test_cpu(0, (const struct cpumask *)dst1))
                /* Should never happen. */
                goto release_exit;

        if (!bpf_cpumask_test_cpu(1, (const struct cpumask *)dst1))
                /* Should never happen. */
                goto release_exit;

        bpf_cpumask_xor(dst2, (const struct cpumask *)mask1, (const struct cpumask *)mask2);
        if (!bpf_cpumask_equal((const struct cpumask *)dst1,
                               (const struct cpumask *)dst2))
                /* Should never happen. */
                goto release_exit;

 release_exit:
        bpf_cpumask_release(mask1);
        bpf_cpumask_release(mask2);
        bpf_cpumask_release(dst1);
        bpf_cpumask_release(dst2);
        return 0;
}

예제는 `mask1`의 CPU 0과 `mask2`의 CPU 1을 set합니다. AND 결과 `dst1`은 empty여야 하고, OR 결과에는 CPU 0과 1이 모두 있어야 합니다. 서로 겹치지 않는 두 mask의 XOR 결과 `dst2`는 OR 결과 `dst1`과 equal해야 합니다. 종료 경로에서는 네 cpumask를 모두 release합니다.

• `bpf_cpumask_and()`: 두 source mask의 교집합을 destination에 저장합니다.
• `bpf_cpumask_or()`: 두 source mask의 합집합을 destination에 저장합니다.
• `bpf_cpumask_xor()`: 두 source mask의 배타적 합을 destination에 저장합니다.
• `bpf_cpumask_copy()`: cpumask 전체 내용을 다른 cpumask로 복사합니다.

Read-only cpumask query kfunc

`cpumasks-querying-label`에 정의된 read-only kfunc는 cpumask 내용을 변경하지 않고 검색·검사·계수합니다. `kernel/bpf/cpumask.c`에 문서화된 function은 다음과 같습니다.

• `bpf_cpumask_first`, `bpf_cpumask_first_zero`, `bpf_cpumask_first_and`
• `bpf_cpumask_test_cpu`, `bpf_cpumask_weight`
• `bpf_cpumask_equal`, `bpf_cpumask_intersects`, `bpf_cpumask_subset`
• `bpf_cpumask_empty`, `bpf_cpumask_full`
• `bpf_cpumask_any_distribute`, `bpf_cpumask_any_and_distribute`

Query 예제와 cpumask selftest

앞 절에 query kfunc 사용 예제가 있으므로 여기서는 반복하지 않습니다. 앞에서 언급한 모든 kfunc는 `tools/testing/selftests/bpf/progs/cpumask_success.c`에서 test합니다.

추가 사용 예제는 `https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/tools/testing/selftests/bpf/progs/cpumask_success.c`의 selftest source에서 확인할 수 있습니다.

새 BPF cpumask kfunc 추가

현재 지원하는 BPF cpumask kfunc 집합은 `include/linux/cpumask.h`의 cpumask operation과 아직 일대일로 일치하지 않습니다. 필요해지면 해당 operation을 새 kfunc로 쉽게 감쌀 수 있습니다.

새 cpumask operation을 지원하려면 patch와 함께 다음 작업을 수행해야 합니다.

• 새 cpumask kfunc를 이 문서에 추가해 설명합니다.
• 관련 selftest testcase를 cpumask selftest suite에 추가합니다.