Wonhyuk Yang

2022년 1월 7일5분 분량

BPF 스터디 노트

최종 수정일: 2022년 1월 10일

BPF(Berkley packet filter)는 패킷 필터 기능만 하는 것이 아니라 genric하고 유연한 instruction set을 제공하여 단순한 필터 이상의 일들을 할 수 있습니다. 작성된 BPF 프로그램은 여러 hook point에서 안전하게 실행할 수 있습니다. 리눅스 커널의 많은 서브 시스템들은 BPF가 실행할 수 있는 hook point를 제공하며, 대표적으로 분야로 networking, tracing, security가 있습니다.

해당 글에서 사용하는 BPF 용어는 eBPF를 지칭합니다.

Instruction Set

BPF는 general purpose RISC instruction set입니다. 이 instruction set은 Subset of C로 작성한 코드를 clang을 통해 BPF instruction으로 컴파일됩니다. 그런 다음, modern 64bit processor에 맞춰 JIT된 native code를 매핑됩니다. 해당 instruction set은 이러한 오버헤드를 최소한으로 가지도록 설계되었습니다.

최근에는 GCC에서도 BPF 컴파일이 가능합니다. 해당 링크 참조

BPF는 RISC machine은 11개의 64bit register, pc, 512byte의 스택으로 구성된다. 레지스터들은 r0-r10과 같은 이름을 가집니다.

r10 레지스터는 read-only 레지스터이며, BPF stack frame ponter 주소를 저장하고 있습니다. 남은 r0-r9 레지스터는 general purpose이며 read/write 가능합니다. 범용 레지스터들의 사용처는 다음과 같습니다.

r0: BPF 프로그램 종료 시에 종료 코드를 저장한다.

r1-r5: scratch 레지스터이다. BPF 프로그램이 시작할 때, r1 레지스터에 context를 저장하고 있다.

BPF calling convention

BPF 프로그램은 미리 정의된 helper 함수들만 호출할 수 있습니다. BPF의 calling convention은 아래와 같습니다.

r0: helper 함수로부터의 리턴 값을 저장한다.
r1-r5: BPF 프로그램이 helper 함수를 호출할 때 필요한 인자들을 저장한다.
r6-r9: callee saved register

위와 같은 BPF의 calling convention으로 다른 아키텍처의 ABI에 쉽게 매핑할 수 있습니다. 예를 들어 만약 아래와 같은 C code가 있다고 하겠습니다.이를 BPF로 컴파일했을 때의 코드는 다음과 같습니다.

위의 C 코드를 BPF로 컴파일하면 아래와 puseudo code와 같습니다.

x86_64 아키텍처로 JIT를 한다면 아래의 instuction으로 변경됩니다.

위에서 살펴볼 수 있듯이, native code에서 함수를 호출하기 위해 추가적인 overhead가 없는 것을 확인할 수 있습니다.

하지만 위와 같은 구조로 6개보다 많은 인자를 요구하는 함수 호출은 불가능합니다(애초에 인자가 6개보다 많은 함수는 helper 함수로 등록도 불가능합니다).

더 자세한 내용은 해당 문서를 참고하면 됩니다.

BPF Architecture

BPF는 단순히 instruction set뿐만 아니라 아래와 같은 다양한 인프라가 존재합니다.

map
helper function
tail call(?)
security hardening primitives(?)
pseudo file system(?)
offload(?)

Verifiler

BPF는 안전하게 실행할 수 있는데, 이 말은 BPF 프로그램이 크래시를 유발하지 않고, 잘못된 주소의 메모리를 접근을 허용하지 않고, 종료된다는 것을 뜻합니다. BPF의 안전성을 보장하기 위해 verifier가 입력으로 들어온 BPF 프로그램을 검사합니다.

verifier은 BPF 프로그램이 DAG(directed acyclic graph)인지 확인합니다. 즉, BPF 프로그램에서는 instruction 흐름 상 뒤로 이동하는 부분(backward branch)이 없어야 합니다. verfier은 instuction 흐름 상 cycle이 존재하는지를 확인하고, 만약 cycle을 발견하였으면, verifiler은 해당 BPF 프로그램은 커널에 설치되는 것을 허용하지 않습니다. 이렇게 엄격하게 검사하는 이유로는 cycle이 존재하는 BPF 프로그램의 경우 최악의 경우에 BPF 내에서 무한 루프에 빠지기 때문입니다.

또한, verifiler는 프로그램이 실행 가능한 경로들을 시뮬레이션하며 스택과 레지스터의 변경 사항들을 관찰합니다. Verifier은 가상 머신의 레지스터들과 stack 슬롯에 타입을 부여하며, 타입의 변화 사항들을 추적합니다. 타입들은 아래의 헤더 파일에 정의되어 있습니다.

BPF 프로그램 시작 직후의 r1 레지스터는 context 주소를 저장하고 있기 때문에 상태는 PTR_TO_CONTEXT입니다. 다른 레지스터들은 어떤 값도 써지지 않은 상태이기 때문에 NOT_INIT과 같습니다. NOT_INIT 상태의 레지스터를 읽는 동작은 허용되지 않습니다.

다음과 같은 BPF 프로그램에서는 NOT_INIT 상태의 r2 레지스터를 접근했기 때문에 Verifiler을 통과하지 못합니다.

각 레지스터/스택의 상태는 instruction의 실행 결과로 업데이트됩니다. 다음과 같은 BPF 프로그램에서, 첫 번째 instruction을 실행하면 r0 레지스터의 상태는 NOT_INIT에서 PTR_TO_CONTEXT로 변경이 됩니다.

BPF calling convention에 따라, r1-r5 레지스터들은 함수 호출 직후의 상태는 NOT_INIT과 같습니다. r6-r9는 callee saved 레지스터이므로 함수 호출 이후에도 이전의 상태가 유지됩니다.

load/store도 마찬가지로 임의의 영역에 값을 쓰고 읽을 수 없고 유효한 타입에 대해서만 가능합니다. load/store이 가능한 유효한 타입으로는 PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK,.. 가 있습니다. 따라서 아래와 같은 BPF 프로그램은 SCALAR_VALUE에 대해 store을 시도하므로 verifiler을 통과하지 못합니다.

verifiler은 포인터 타입에 대해, 포인터가 가질 수 있는 range와 align도 저장하며 접근이 유효한지 확인합니다. 아래와 instruction이 있을 때,

r6 레지스터의 타입이 PTR_TO_CTX라면 verifier에서는 해당 context+8에서 4 byte 읽기가 가능한지 체크합니다.

만약, r6 레지스터의 타입이 PTR_TO_STACK일 경우 range와 align이 체크됩니다. 스택 포인터의 유효한 offset 범위는 [-MAX_BPF_STACK, 0)입니다. 따라서 +8은 이 범위를 벗어나기 때문에 유효한 접근이 아닙니다.

verifiler은 bpf 프로그램에서 map과 helper function을 접근할 수 있도록 BPF 코드를 수정(fixup)한다. 이 부분은 map과 helper 에서 다룹니다.

BPF load

컴파일한 bpf 프로그램을 커널에 주입하기 위해서는, bpf 시스템 콜을 사용해야 합니다. bpf 시스템 콜은 다음과 같은 정의되어 있습니다.

int bpf(int cmd, union bpf_attr *attr, unsigned int size);

위 시스템 콜은, 첫 번째 인자인, cmd에 따라 동작이 달라집니다. 그 중에서 BPF 프로그램을 load하기 위해서 사용되는 커맨드는 BPF_PROG_LOAD입니다. 이 외에 필요한 인자는 attr를 통해 전달한다. bpf를 load할 때의 attr의 구성은 아래와 같습니다.

bpf_attr은 union으로 커맨드에 따라 사용되는 struct가 다릅니다.

다양한 인자가 있지만 우선 살펴볼 인자는 prog_type입니다. prog_type 멤버는 BPF의 프로그램의 타입을 나타냅니다. 이러한 타입은 BPF 프로그램이 어떤 곳에서 사용될지(context)를 결정합니다. 만약 BPF_PROG_TYPE_SOCKET의 타입을 가진다면, 해당 BPF 프로그램은 socket에 부착될 것이고, BPF_PROG_TYPE_TRACING의 타입을 가지면 트레이싱 필터에 부착될 것입니다. 타입을 통해, 사용되는 data와 helper function이 결정됩니다.

타입을 결정하였다면 attr.insns에 컴파일한 바이트 코드의 주소를 저장하여 커널에 전달합니다.

BPF는 다른 서브 시스템과 긴밀하게 연결되어 있기 때문에 순수하게 BPF만 알아서는 사용하기가 힘든 것 같습니다.

bpf 시스템 콜을 호출하면 커널 내부에서는 verifier을 통해 안전한지 확인합니다. 통과한다면 bfp 시스템 콜은 파일 디스크립터를 반환합니다.

이 다음으로는 bpf 프로그램을 attach해야 합니다. bpf 프로그램을 attach하기 위한 방법은 hook point에 따라 다양합니다.

<예시 하나 조사>

Maps

map은 이름과 같이 key와 value로 구성된 자료 구조이며, kernel과 userspace에서 공유 가능한 generic한 저장소입니다. 각각의 map들은 다음과 같은 속성을 가지고 있습니다.

type
저장할 수 있는 최대 갯수
key의 사이즈
value의 사이즈

Maps in userspace

userspace에서 map을 접근하기 위해서는 bpf 시스템 콜을 사용해야 합니다. map을 접근하기 위한 커맨드들은 아래와 같습니다.

BPF_MAP_CREATE: map을 생성하는 커맨드이다. 생성된 map은 파일 디스크립터로 반환된다.
BPF_MAP_LOOKUP_ELEM: map에서 주어진 key를 통해 value를 찾는 커맨드이다.
BPF_MAP_UPDATE_ELEM: map에서 새로운 key/value를 추가하거나 업데이트하는 커맨드이다.
BPF_MAP_DELETE_ELEM: map에서 주어진 key/value를 삭제하는 커맨드이다.
BPF_MAP_GET_NEXT_KEY: map에서 주어진 키로 element를 찾고, 다음 element의 키를 반환하는 커맨드이다.

man 페이지에서는 bpf 시스템 콜을 래핑한 함수들을 통해 bpf 시스템 콜을 어떻게 사용하는지 보여주고 있습니다.

Maps in kernel

BPF 프로그램에서 map에 접근하기 커널에 위치하는 map의 주소를 알아야 합니다. 하지만 BPF 코드를 작성할 때 해당 주소를 알 수 없습니다. 따라서 map에 접근하기 위해서는 특별한 방식을 사용합니다.

앞서 보았듯이 prog_load의 커맨드로 bpf 시스템 콜을 호출할 때 attr도 같이 전달합니다. attr에는 fd_array가 존재하는데, map 파일 디스크립터들을 저장하는 배열입니다. BPF에서는 이 인덱스를 사용하여 특정 map에 접근하는 것을 표현합니다. 물론 이 값은 실제 주소는 아니기에 verifiler에서 instruction에 인코딩된 인덱스 값을 실제 타겟 map의 주소로 변환합니다.

fd_array는 2021에 도입된 " bpf: Introduce fd_idx" 패치로 도입되었습니다.

Helper Functions

Helper 함수는 커널 코어에 미리 정의된 함수로, BPF 프로그램에서 호출할 수 있습니다. BPF 프로그램의 type에 따라 사용 가능한 helper 함수들은 다릅니다.

helper 함수을 호출하기 위해서는 이전에 언급한 calling convention을 사용하고 커널 코어에서는 아래와 같이 helper 함수의 시그니처가 정의되어 있습니다.

함수의 유효한 인자 타입도 저장하기에, verifiler에서는 함수 호출이 안전한지 확인할 수 있습니다.

하지만 C로 BPF 프로그램을 작성할 때는, 커널에 위치한 helper 함수의 실제 주소를 알 수 없습니다. 그렇다면 BPF 프로그램을 링크할 때 사용하는 helper 함수들의 주소는 무엇일까요? libbpf 라이브러리에 존재하는 bpf_helper_defs.h 헤더 파일을 살펴보겠습니다.

위에서 볼 수 있듯이 bpf_map_look_elem 함수 포인터는 0x01 주소를 가집니다. 이와 같이 helper 함수들은 각자 고유한 id를 가집니다. verifier에서는 helper 함수를 호출하는 instruction을 감지하고, instruction에 인코딩된 id 값을 보고 커널에 위치한 헬퍼 함수의 주소를 알아내고 호출할 수 있도록 코드를 수정합니다.

BPF library

시스템 콜 수준에서 BPF 어플리케이션을 구현하는 것은 많은 노력을 요구합니다. 대신 llibbpf를 사용하면 수고를 덜 수 있습니다. 라이브러리를 활용한 예제는 (linux/sample/bpf/...)에서 찾아볼 수 있습니다. 예제는 *_user.c와 *_kernel.c 프로그램으로 구성됩니다. *_kernel.c 코드는 bpf 프로그램으로 별도의 섹션으로 분리하여 어느 hookpoint에 설치할지 명시합니다. *_user.c 코드는 userspace에서 실행되는 프로그램으로 map을 읽어 정보들을 처리하는 일을 수행합니다.