BPF Iterators

두 가지 BPF iterator

BPF는 통틀어 "BPF iterator"라고 부르는 서로 다른 두 entity, 즉 BPF iterator program type과 open-coded BPF iterator를 지원합니다.

BPF iterator program type은 독립적인 BPF program type입니다. user가 attach하고 activate하면 순회하는 각 entity, 예를 들어 `task_struct`나 cgroup마다 한 번씩 호출됩니다. 반면 open-coded iterator는 iterator 기능을 구현하는 BPF-side API 집합이며 여러 BPF program type에서 사용할 수 있습니다.

open-coded iterator는 BPF iterator program과 비슷한 기능을 제공하면서 다른 모든 BPF program type에 더 많은 flexibility와 control을 줍니다. BPF iterator program은 `seq_file` 기능을 기반으로, attach된 BPF iterator program이 내용을 생성하는 anonymous 또는 BPF FS-mounted special file을 구현하는 데 사용할 수 있습니다. 구체적인 필요에 따라 둘 다 유용합니다.

새 BPF iterator program을 추가할 때는 최대한 유연하게 쓸 수 있도록 같은 기능의 open-coded iterator도 추가해야 합니다. 두 iterator API surface가 iteration logic과 code를 가능한 한 많이 공유하고 재사용하는 것도 기대됩니다.

Open-coded iterator type과 kfunc 이름

open-coded BPF iterator는 긴밀히 결합된 kfunc 세 개, 즉 constructor, next element fetch, destructor와 stack 위 iterator state를 나타내는 iterator별 type으로 구현합니다. BPF verifier는 해당 constructor, destructor, next API 밖에서 이 state를 변경할 수 없도록 보장합니다.

각 open-coded iterator 종류에는 대응하는 `struct bpf_iter_<type>`이 있습니다. `<type>`은 구체적인 iterator type을 뜻합니다. `bpf_iter_<type>` state는 BPF program stack에 있어야 하므로 stack에 들어갈 만큼 작아야 합니다.

성능을 위해 iterator state의 dynamic memory allocation을 피하고 필요한 모든 항목이 들어가도록 state struct를 충분히 크게 만드는 편이 좋습니다. 필요하다면 dynamic allocation으로 BPF stack 한계를 우회할 수 있습니다. state struct size는 iterator의 user-visible API 일부이므로 이를 바꾸면 backwards compatibility가 깨집니다. 따라서 설계할 때 신중해야 합니다.

constructor, next, destructor kfunc는 각각 `bpf_iter_<type>_{new,next,destroy}()` 형식으로 일관되게 이름을 붙여야 합니다. iterator state type은 일치하는 `struct bpf_iter_<type>`이어야 하며 모든 iterator kfunc는 이 struct의 pointer를 첫 번째 argument로 받아야 합니다.

추가 규칙은 다음과 같습니다.

• constructor인 `bpf_iter_<type>_new()`는 임의 개수의 추가 argument를 받을 수 있고 return type도 제한하지 않습니다.
• next method인 `bpf_iter_<type>_next()`는 pointer type을 return해야 하며 argument는 정확히 하나, `struct bpf_iter_<type> *`여야 합니다. const, volatile, restrict와 typedef는 무시합니다.
• destructor인 `bpf_iter_<type>_destroy()`는 `void`를 return해야 하며 next method와 마찬가지로 argument가 정확히 하나여야 합니다.
• `struct bpf_iter_<type>` size는 양수이고 stack slot에 올바르게 맞도록 8 bytes의 배수여야 합니다.

이처럼 엄격하고 일관된 규칙 덕분에 중요한 boilerplate detail을 추상화한 generic helper를 만들어 open-coded iterator를 효과적이고 ergonomic하게 사용할 수 있습니다. 예를 들어 libbpf의 `bpf_for_each()` macro가 있습니다. kernel은 kfunc registration 시점에 이 규칙을 강제합니다.

Constructor·next·destructor 계약

constructor, next, destructor 구현 계약은 다음과 같습니다.

• constructor `bpf_iter_<type>_new()`는 stack의 iterator state를 항상 initialize합니다. input argument가 invalid해도 이후 `next()`가 `NULL`을 return하도록 state를 initialize해야 합니다. 즉 error가 나면 error를 return하면서 empty iterator를 construct합니다. constructor kfunc에는 `KF_ITER_NEW` flag를 표시합니다.
• next method `bpf_iter_<type>_next()`는 iterator state pointer를 받아 element를 생성하고 항상 pointer를 return해야 합니다. BPF verifier와의 계약에 따라 element를 모두 소진하면 결국 반드시 `NULL`을 return해야 하며, 한 번 `NULL`을 return한 뒤의 next call도 계속 `NULL`을 return해야 합니다. next method에는 `KF_ITER_NEXT`를 표시하고, `NULL`을 return하는 kfunc이므로 물론 `KF_RET_NULL`도 표시해야 합니다.
• destructor `bpf_iter_<type>_destroy()`는 constructor가 실패했거나 next가 아무것도 return하지 않았더라도 항상 한 번 호출됩니다. resource를 free하고 `struct bpf_iter_<type>`이 사용한 stack space를 다른 용도로 쓸 수 있게 표시합니다. destructor에는 `KF_ITER_DESTROY` flag를 표시합니다.

모든 open-coded BPF iterator 구현은 최소한 이 세 method를 구현해야 합니다. 각 iterator type에는 해당 type의 constructor, destructor, next만 호출할 수 있도록 강제됩니다. 예를 들어 verifier는 number iterator state를 cgroup iterator의 next method에 넘기지 못하게 합니다.

Verifier의 반복 종료성 검증

BPF verification을 높은 수준에서 보면 next method는 conditional jump를 검증할 때처럼 verification state가 갈라지는 지점입니다. verifier는 `call bpf_iter_<type>_next` instruction에서 branch를 만들고 `NULL`, 즉 iteration 종료와 non-`NULL`, 즉 새 element 반환이라는 두 결과를 simulate합니다.

먼저 `NULL` 결과를 simulate하며 loop 없이 exit에 도달해야 합니다. 그 뒤 non-`NULL` case를 검증합니다. 이 case는 실제 loop가 없는 간단한 예제라면 exit에 도달하거나, 이미 일부 검증된 state와 equivalent한 state로 또 다른 `call bpf_iter_<type>_next` instruction에 도달합니다.

그 지점의 state equivalency는 정해진 "state envelope" 밖으로 벗어나지 않은 채 기술적으로 영원히 loop할 수 있음을 뜻합니다. 이후 iteration이 verifier state에 새 knowledge나 constraint를 더하지 않으므로 1회, 2회, 10회, 100만 회 실행해도 차이가 없습니다.

하지만 iterator next method가 결국 `NULL`을 return해야 한다는 계약을 고려하면 loop body가 안전하고 마침내 종료된다고 결론 내릴 수 있습니다. verifier는 loop 바깥 logic인 `NULL` case를 검증했고 loop body도 안전하다고 확인했으므로 전체 program logic의 safety를 보장할 수 있습니다.

Kernel data 추출의 기존 한계

kernel data를 userspace로 dump하는 기존 방법은 몇 가지이며 가장 널리 쓰이는 것은 `/proc` system입니다. 예를 들어 `cat /proc/net/tcp6`는 system의 모든 tcp6 socket을, `cat /proc/net/netlink`는 모든 netlink socket을 dump합니다.

하지만 output format은 대체로 고정돼 있고 socket에 관한 정보를 더 원하면 kernel을 patch해야 합니다. upstream publish와 release에 시간이 걸릴 수 있습니다. `ss` 같은 도구도 추가 정보에 kernel patch가 필요하다는 점은 같습니다.

이 문제를 해결하려 kernel 변경 없이 data를 파고드는 `drgn` tool을 자주 사용합니다. 그러나 drgn은 kernel 안에서 pointer tracing을 할 수 없어 성능이 낮다는 큰 단점이 있습니다. pointer value를 validate할 수도 없어 pointer가 kernel 안에서 invalid해지면 잘못된 data를 읽을 수 있습니다.

BPF iterator는 각 kernel data object마다 BPF program을 호출해 task, `bpf_map` 등 수집할 data를 유연하게 선택함으로써 이 문제를 해결합니다.

BPF iterator program 동작 방식

BPF iterator는 특정 type의 kernel object를 user가 순회할 수 있게 하는 BPF program type입니다. 전통적인 BPF tracing program은 kernel execution의 특정 지점에서 callback을 호출하지만, BPF iterator는 여러 kernel data structure의 모든 entry마다 실행할 callback을 정의할 수 있습니다.

예를 들어 system의 모든 task를 순회하면서 각 task가 현재 사용한 총 CPU runtime을 dump할 수 있습니다. 다른 BPF task iterator는 각 task의 cgroup 정보를 dump할 수 있습니다. 이런 flexibility가 BPF iterator의 핵심 가치입니다.

BPF program은 항상 userspace process의 요청으로 kernel에 load됩니다. userspace process는 필요한 program skeleton을 open하고 initialize한 다음 syscall을 호출해 kernel이 BPF program을 verify하고 load하게 합니다.

전통적인 tracing program은 userspace가 `bpf_program__attach()`로 program의 `bpf_link`를 얻어 activate합니다. activate 뒤에는 main kernel에서 tracepoint가 trigger될 때마다 callback이 호출됩니다. BPF iterator program은 `bpf_link_create()`로 `bpf_link`를 얻으며, userspace에서 system call을 실행할 때 callback이 호출됩니다.

이제 iterator로 kernel object를 순회하고 data를 읽는 방법을 살펴봅니다.

Userspace에서 iterator load와 trigger

BPF selftest는 iterator 사용법을 보여 주는 좋은 자료입니다. 이 절에서는 BPF iterator program을 load하고 사용하는 BPF selftest를 살펴봅니다. userspace에서 BPF iterator를 load하고 trigger하는 방법은 `bpf_iter.c` 예제가 보여 주며, 뒤에서는 kernel space에서 실행하는 BPF program도 봅니다.

userspace에서 BPF iterator를 kernel에 load하는 일반 절차는 다음과 같습니다.

• BPF program을 `libbpf`를 통해 kernel에 load합니다. kernel이 program을 verify하고 load하면 file descriptor(fd)를 userspace에 반환합니다.
• kernel이 반환한 BPF program file descriptor를 지정해 `bpf_link_create()`를 호출하고 BPF program의 `link_fd`를 얻습니다.
• 2단계에서 받은 `bpf_link`를 지정해 `bpf_iter_create()`를 호출하고 BPF iterator file descriptor인 `bpf_iter_fd`를 얻습니다.
• 더 이상 data가 없을 때까지 `read(bpf_iter_fd)`를 호출해 iteration을 trigger합니다.
• `close(bpf_iter_fd)`로 iterator fd를 닫습니다.
• data를 다시 읽어야 하면 새 `bpf_iter_fd`를 얻어 read를 다시 수행합니다.

selftest BPF iterator program 예제는 다음과 같습니다.

• `bpf_iter_tcp4.c`: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/progs/bpf_iter_tcp4.c
• `bpf_iter_task_vmas.c`: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/progs/bpf_iter_task_vmas.c
• `bpf_iter_task_file.c`: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/progs/bpf_iter_task_file.c

task_file iterator context

kernel space에서 실행하는 `bpf_iter_task_file.c`를 살펴봅니다. 다음은 `vmlinux.h`에 있는 `bpf_iter__task_file` 정의입니다. `vmlinux.h`에서 `bpf_iter__<iter_name>` 형식인 struct name은 모두 BPF iterator를 나타내며 suffix `<iter_name>`은 iterator type입니다.

struct bpf_iter__task_file {
        union {
            struct bpf_iter_meta *meta;
        };
        union {
            struct task_struct *task;
        };
        u32 fd;
        union {
            struct file *file;
        };
};

위 code에서 `meta` field는 모든 BPF iterator program에 공통인 metadata입니다. 나머지 field는 iterator마다 다릅니다. `task_file` iterator의 경우 kernel layer가 `task`, `fd`, `file` 값을 제공합니다.

`task`와 `file`은 reference counted이므로 BPF program이 실행되는 동안 사라지지 않습니다.

task_file program과 output 전달

다음은 `bpf_iter_task_file.c` file의 일부입니다.

SEC("iter/task_file")
int dump_task_file(struct bpf_iter__task_file *ctx)
{
  struct seq_file *seq = ctx->meta->seq;
  struct task_struct *task = ctx->task;
  struct file *file = ctx->file;
  __u32 fd = ctx->fd;

  if (task == NULL || file == NULL)
    return 0;

  if (ctx->meta->seq_num == 0) {
    count = 0;
    BPF_SEQ_PRINTF(seq, "    tgid      gid       fd      file\n");
  }

  if (tgid == task->tgid && task->tgid != task->pid)
    count++;

  if (last_tgid != task->tgid) {
    last_tgid = task->tgid;
    unique_tgid_count++;
  }

  BPF_SEQ_PRINTF(seq, "%8d %8d %8d %lx\n", task->tgid, task->pid, fd,
          (long)file->f_op);
  return 0;
}

위 예제의 section name `SEC("iter/task_file")`은 모든 task의 모든 file을 순회하는 BPF iterator program임을 나타냅니다. program context는 `bpf_iter__task_file` struct입니다.

userspace program은 `read()` syscall을 실행해 kernel에서 동작하는 BPF iterator program을 호출합니다. 호출된 BPF program은 여러 BPF helper function으로 data를 userspace에 export할 수 있습니다.

formatted output이 필요하면 `bpf_seq_printf()`와 `BPF_SEQ_PRINTF` helper macro를, binary data가 필요하면 `bpf_seq_write()`를 사용할 수 있습니다. binary-encoded data는 userspace application이 필요에 맞게 처리할 수 있습니다.

formatted data는 BPF iterator를 bpffs mount에 pin한 뒤 `cat <path>`로 `/proc/net/netlink`와 비슷하게 출력할 수 있습니다. 나중에 `rm -f <path>`로 pinned iterator를 제거합니다.

다음 command는 `bpf_iter_ipv6_route.o` object file에서 BPF iterator를 만들고 `/sys/fs/bpf/my_route` path에 pin합니다.

$ bpftool iter pin ./bpf_iter_ipv6_route.o  /sys/fs/bpf/my_route

그 뒤 다음 command로 결과를 출력합니다.

$ cat /sys/fs/bpf/my_route

Kernel iterator type 등록

kernel에 BPF iterator를 구현하려면 developer가 `include/linux/bpf.h`의 핵심 data structure를 한 번 변경해야 합니다.

struct bpf_iter_reg {
          const char *target;
          bpf_iter_attach_target_t attach_target;
          bpf_iter_detach_target_t detach_target;
          bpf_iter_show_fdinfo_t show_fdinfo;
          bpf_iter_fill_link_info_t fill_link_info;
          bpf_iter_get_func_proto_t get_func_proto;
          u32 ctx_arg_info_size;
          u32 feature;
          struct bpf_ctx_arg_aux ctx_arg_info[BPF_ITER_CTX_ARG_MAX];
          const struct bpf_iter_seq_info *seq_info;
};

data structure field를 채운 뒤 `bpf_iter_reg_target()`을 호출해 iterator를 main BPF iterator subsystem에 등록합니다.

`struct bpf_iter_reg`의 각 field는 다음과 같습니다.

kernel의 `task_vma` BPF iterator 구현 예는 `https://lore.kernel.org/bpf/20210212183107.50963-2-songliubraving@fb.com/`에서 볼 수 있습니다.

Task iterator filtering 동기

기본적으로 BPF iterator는 system 전체에서 지정한 type의 모든 object, 즉 process, cgroup, map 등을 순회해 관련 kernel data를 읽습니다.

하지만 특정 process 안의 task만 순회하는 것처럼 전체보다 훨씬 작은 kernel object subset만 필요할 때가 많습니다. BPF iterator program은 attach 시 userspace가 program을 configure하게 해 iteration 대상 object를 filter할 수 있습니다.

BPF task_file iterator program

다음 BPF iterator program은 iterator의 `seq_file`을 통해 file과 task 정보를 출력합니다. iterator의 모든 file을 방문하는 표준 BPF iterator program이며 뒤의 예제에서 사용합니다.

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

char _license[] SEC("license") = "GPL";

SEC("iter/task_file")
int dump_task_file(struct bpf_iter__task_file *ctx)
{
      struct seq_file *seq = ctx->meta->seq;
      struct task_struct *task = ctx->task;
      struct file *file = ctx->file;
      __u32 fd = ctx->fd;
      if (task == NULL || file == NULL)
              return 0;
      if (ctx->meta->seq_num == 0) {
              BPF_SEQ_PRINTF(seq, "    tgid      pid       fd      file\n");
      }
      BPF_SEQ_PRINTF(seq, "%8d %8d %8d %lx\n", task->tgid, task->pid, fd,
                      (long)file->f_op);
      return 0;
}

PID·TID parameter로 file 제한

특정 process의 file만 포함하는 iterator를 만드는 방법을 살펴봅니다. 먼저 다음처럼 `bpf_iter_attach_opts` struct를 채웁니다.

LIBBPF_OPTS(bpf_iter_attach_opts, opts);
union bpf_iter_link_info linfo;
memset(&linfo, 0, sizeof(linfo));
linfo.task.pid = getpid();
opts.link_info = &linfo;
opts.link_info_len = sizeof(linfo);

`linfo.task.pid`가 0이 아니면 kernel은 지정한 `pid` process가 연 file만 포함하는 iterator를 만듭니다. 이 예에서는 자신의 process file만 순회합니다. `linfo.task.pid`가 0이면 모든 process가 연 모든 file을 방문합니다.

마찬가지로 `linfo.task.tid`는 process가 아닌 특정 thread가 연 file을 방문하는 iterator를 만들도록 지시합니다. thread가 별도 file descriptor table을 가질 때만 `linfo.task.tid`와 `linfo.task.pid`의 결과가 다릅니다. 대부분의 경우 process의 모든 thread가 하나의 file descriptor table을 공유합니다.

이제 userspace program에서 struct pointer를 `bpf_program__attach_iter()`에 넘깁니다.

link = bpf_program__attach_iter(prog, &opts);
iter_fd = bpf_iter_create(bpf_link__fd(link));

`tid`와 `pid`가 모두 0이면 이 `bpf_iter_attach_opts` struct로 만든 iterator는 system, 정확히는 해당 namespace의 모든 task가 연 모든 file을 포함합니다. 이는 `bpf_program__attach_iter()`의 두 번째 argument로 `NULL`을 넘긴 것과 같습니다.

Parameter iterator 전체 userspace 예제

전체 program은 다음과 같습니다.

#include <stdio.h>
#include <unistd.h>
#include <bpf/bpf.h>
#include <bpf/libbpf.h>
#include "bpf_iter_task_ex.skel.h"

static int do_read_opts(struct bpf_program *prog, struct bpf_iter_attach_opts *opts)
{
      struct bpf_link *link;
      char buf[16] = {};
      int iter_fd = -1, len;
      int ret = 0;

      link = bpf_program__attach_iter(prog, opts);
      if (!link) {
              fprintf(stderr, "bpf_program__attach_iter() fails\n");
              return -1;
      }
      iter_fd = bpf_iter_create(bpf_link__fd(link));
      if (iter_fd < 0) {
              fprintf(stderr, "bpf_iter_create() fails\n");
              ret = -1;
              goto free_link;
      }
      /* not check contents, but ensure read() ends without error */
      while ((len = read(iter_fd, buf, sizeof(buf) - 1)) > 0) {
              buf[len] = 0;
              printf("%s", buf);
      }
      printf("\n");
free_link:
      if (iter_fd >= 0)
              close(iter_fd);
      bpf_link__destroy(link);
      return 0;
}

static void test_task_file(void)
{
      LIBBPF_OPTS(bpf_iter_attach_opts, opts);
      struct bpf_iter_task_ex *skel;
      union bpf_iter_link_info linfo;
      skel = bpf_iter_task_ex__open_and_load();
      if (skel == NULL)
              return;
      memset(&linfo, 0, sizeof(linfo));
      linfo.task.pid = getpid();
      opts.link_info = &linfo;
      opts.link_info_len = sizeof(linfo);
      printf("PID %d\n", getpid());
      do_read_opts(skel->progs.dump_task_file, &opts);
      bpf_iter_task_ex__destroy(skel);
}

int main(int argc, const char * const * argv)
{
      test_task_file();
      return 0;
}

program output은 다음과 같습니다.

PID 1859

   tgid      pid       fd      file
   1859     1859        0 ffffffff82270aa0
   1859     1859        1 ffffffff82270aa0
   1859     1859        2 ffffffff82270aa0
   1859     1859        3 ffffffff82272980
   1859     1859        4 ffffffff8225e120
   1859     1859        5 ffffffff82255120
   1859     1859        6 ffffffff82254f00
   1859     1859        7 ffffffff82254d80
   1859     1859        8 ffffffff8225abe0

Parameter 없이 BPF program에서 filtering

parameter가 없는 BPF iterator가 system의 다른 process file을 건너뛰는 방법을 살펴봅니다. 이 경우 BPF program이 task의 `pid` 또는 `tid`를 직접 검사해야 하며, 그렇지 않으면 현재 `pid` namespace의 모든 열린 file을 받습니다. 보통 BPF program에 global variable을 추가해 `pid`를 전달합니다.

BPF program은 다음과 같은 형태입니다.

......
int target_pid = 0;

SEC("iter/task_file")
int dump_task_file(struct bpf_iter__task_file *ctx)
{
      ......
      if (task->tgid != target_pid) /* Check task->pid instead to check thread IDs */
              return 0;
      BPF_SEQ_PRINTF(seq, "%8d %8d %8d %lx\n", task->tgid, task->pid, fd,
                      (long)file->f_op);
      return 0;
}

userspace program은 다음과 같은 형태입니다.

......
static void test_task_file(void)
{
      ......
      skel = bpf_iter_task_ex__open_and_load();
      if (skel == NULL)
              return;
      skel->bss->target_pid = getpid(); /* process ID.  For thread id, use gettid() */
      memset(&linfo, 0, sizeof(linfo));
      linfo.task.pid = getpid();
      opts.link_info = &linfo;
      opts.link_info_len = sizeof(linfo);
      ......
}

`target_pid`는 BPF program의 global variable입니다. BPF program이 다른 process의 열린 file을 건너뛰도록 userspace program이 이 variable을 process ID로 initialize해야 합니다.

BPF iterator를 parameterize하면 iterator가 BPF program을 호출하는 횟수가 줄어 상당한 resource를 절약할 수 있습니다.

VMA iterator parameter

기본적으로 BPF VMA iterator는 모든 process의 모든 VMA를 포함합니다. 하지만 특정 process나 thread를 지정해 그 대상의 VMA만 포함할 수 있습니다.

file과 달리 Linux 2.6.0-test6 이후 thread는 별도 address space를 가질 수 없습니다. 따라서 여기서는 `tid`를 사용해도 `pid`를 사용하는 것과 차이가 없습니다.

Task iterator의 pid와 tid

`pid` parameter가 있는 BPF task iterator는 process의 모든 task, 즉 thread를 포함하며 BPF program은 이 task들을 차례로 받습니다.

`tid` parameter로 BPF task iterator를 지정하면 주어진 `tid`와 일치하는 task만 포함할 수 있습니다.