BPF Graph Data Structures

BPF graph data structure 구현

`BPF Graph Data Structures` 문서는 새 방식의 "graph" data structure인 `linked_list`와 `rbtree`의 구현 세부 사항을 설명하며, 특히 이들 data structure에 고유한 semantics를 verifier가 어떻게 구현하는지에 초점을 맞춥니다.

특정 verifier code를 직접 지칭하지는 않지만, 독자가 BPF verifier 내부 구조, BPF map, BPF program 작성에 관한 일반 지식을 갖추었다고 가정합니다.

이 문서의 목적은 graph data structure의 현재 상태를 설명하는 것입니다. 여기에서 semantics나 API의 안정성을 보장하거나 암시하지 않습니다.

문서에는 depth 2의 local contents 목록이 포함됩니다.

Map API에서 graph API로

역사적으로 BPF map API는 BPF program 안에서 여러 종류의 data structure를 노출하는 주된 방법이었습니다. `HASH`와 `ARRAY` 같은 일부 data structure는 map API에 자연스럽게 들어맞지만, 그렇지 않은 것도 있습니다. 따라서 후자와 상호 작용하는 program은 BPF 경험이 없는 kernel programmer가 해석하기 어려울 수 있습니다.

다행히 BPF map semantics를 사용해야 했던 일부 제약은 더 이상 유효하지 않습니다. kfunc, kptr, any-context BPF allocator가 도입되면서 이제 kernel의 나머지 부분에 노출되는 API와 semantics에 더 가까운 BPF data structure를 구현할 수 있습니다.

그러한 data structure인 `linked_list`와 `rbtree`는 많은 verification 세부 사항을 공유합니다. 둘 다 "root"(`linked_list`에서는 "head")와 "node"를 가지므로 verifier code와 이 문서는 공통 기능을 `graph_api`, `graph_root`, `graph_node` 등으로 부릅니다.

달리 명시하지 않는 한 아래의 예제와 semantics는 두 graph data structure 모두에 적용됩니다.

안정성을 보장하지 않는 API

BPF map API로 구현한 data structure는 역사적으로 표준 map API helper인 `bpf_map_update_elem` 또는 map별 helper 같은 BPF helper function을 사용했습니다. 새 방식의 graph data structure는 그 대신 조작 helper를 kfunc로 정의합니다.

kfunc에는 안정성 보장이 없으므로 필요하다면 이 data structure의 API와 semantics를 하위 호환성을 깨뜨리는 방식으로 발전시킬 수 있습니다.

새 data structure의 root와 node type은 `uapi/linux/bpf.h` header에 opaque하게 정의되어 있습니다.

Intrusive node와 root별 spin lock

새 방식의 data structure는 intrusive 구조이며 일반 kernel counterpart와 비슷하게 정의합니다.

struct node_data {
  long key;
  long data;
  struct bpf_rb_node node;
};

struct bpf_spin_lock glock;
struct bpf_rb_root groot __contains(node_data, node);

`linked_list`와 `rbtree`의 "root" type은 `bpf_spin_lock`도 함께 들어 있는 map value 안에 위치해야 합니다. 위 예제에서는 두 global variable을 single-value array map 하나에 둡니다.

Verifier는 `bpf_spin_lock`과 `bpf_rb_root`가 같은 map value에 있다는 사실을 근거로 둘을 연결하고, tree를 조작하는 BPF program을 검증할 때 올바른 lock을 보유했는지 강제합니다. 이 lock 검사는 verification 시점에 수행되므로 runtime penalty가 없습니다.

Ownership을 획득하고 graph에 넘기는 과정

다음 BPF code를 살펴봅니다.

struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n); /* PASSED */

bpf_spin_unlock(&lock);

Verifier 관점에서 `bpf_obj_new`가 반환한 pointer `n`의 type은 `PTR_TO_BTF_ID | MEM_ALLOC`이고, `btf_id`는 `struct node_data`이며 `ref_obj_id`는 0이 아닙니다. Program이 `n`을 보유하므로 `n`이 가리키는 object의 lifetime ownership도 program에 있습니다.

BPF program은 종료하기 전에 ownership을 넘겨야 합니다. Object를 `free`하는 `bpf_obj_drop`에 넘기거나, `bpf_rbtree_add`로 `tree`에 추가할 수 있습니다.

예제의 `ACQUIRED`와 `PASSED` comment는 각각 "ownership을 획득한" statement와 "ownership을 넘긴" statement를 나타냅니다.

Ownership 이전 뒤에도 유용한 접근

Ownership을 넘긴 뒤 verifier가 `n`을 어떻게 처리해야 하는지 생각해 볼 수 있습니다. `bpf_obj_drop`으로 object를 `free`했다면 답은 분명합니다. Object가 더 이상 유효하지 않으므로 `bpf_obj_drop` 뒤에 `n`에 접근하려는 program은 reject해야 합니다. Underlying memory가 다른 allocation에 재사용되거나 unmap되는 등 여러 일이 생길 수 있습니다.

`bpf_rbtree_add`를 통해 ownership을 `tree`에 넘긴 경우에는 답이 덜 분명합니다. Verifier가 `bpf_obj_drop`과 같은 semantics를 강제할 수도 있지만, 그러면 다음과 같이 유용하고 흔한 coding pattern을 사용하는 program이 reject됩니다.

int x;
struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n); /* PASSED */
x = n->data;
n->data = 42;

bpf_spin_unlock(&lock);

이 경우 `n->data`를 읽는 동작과 쓰는 동작이 모두 reject될 것입니다.

Lock과 pointer stability가 허용하는 안전한 접근

Verifier는 다음 두 가지 세부 사항을 활용해 더 나은 결과를 낼 수 있습니다.

• Graph data structure API는 graph root에 연결된 `bpf_spin_lock`을 보유하고 있을 때만 사용할 수 있습니다.
• 두 graph data structure 모두 pointer stability를 가집니다. Graph node는 `bpf_obj_new`로 allocate되고 root에 추가하거나 root에서 제거할 때 node struct의 `bpf_{list,rb}_node` field만 조작하므로, 두 operation 뒤에도 graph node의 address는 바뀌지 않습니다.

추가 또는 제거를 수행하는 program은 연결된 `bpf_spin_lock`을 반드시 보유해야 합니다. 따라서 그 lock이 경계를 이루는 critical section 안에서는 section이 끝날 때까지 다른 program이 node를 추가하거나 제거할 수 없다는 것을 압니다.

이 사실을 pointer stability와 결합하면 ownership을 넘기는 데 `n`을 사용한 뒤에도 critical section이 끝날 때까지 `n`을 통해 graph node에 안전하게 접근할 수 있습니다.

Verifier는 이러한 reference를 *non-owning reference*라고 합니다. 이에 따라 `bpf_obj_new`가 반환한 reference는 *owning reference*입니다. 현재 두 용어는 graph node와 graph API 맥락에서만 의미가 있습니다.

Owning reference의 속성

두 reference type의 속성을 열거하면 다음과 같습니다.

• Owning reference는 pointee의 lifetime을 제어합니다.
• Pointee의 ownership은 graph API kfunc에 넘기거나 pointee를 `free`하는 `bpf_obj_drop`을 통해 반드시 "release"해야 합니다. Program이 끝나기 전에 release하지 않으면 verifier는 program을 invalid로 판단합니다.
• Pointee memory에 접근해도 page fault가 발생하지 않습니다.

Non-owning reference의 속성

• Non-owning reference는 pointee를 소유하지 않습니다. 따라서 graph node를 graph root에 추가하는 데 사용할 수 없고 `bpf_obj_drop`으로 `free`할 수도 없습니다.
• Lifetime을 명시적으로 제어하지 않지만 non-owning reference가 존재한다는 사실을 바탕으로 유효한 lifetime을 추론할 수 있습니다.
• Pointee memory에 접근해도 page fault가 발생하지 않습니다.

Critical section에 한정된 유효 기간

Verifier 관점에서 non-owning reference는 `spin_lock`과 `spin_unlock` 사이에만 존재할 수 있습니다. `spin_unlock` 뒤에는 다른 program이 data structure에서 node를 제거하고 `bpf_obj_drop`으로 `free`하는 등 임의의 operation을 수행할 수 있기 때문입니다.

어떤 memory chunk가 제거되고 `free`된 뒤 `bpf_obj_new`로 재사용되면 그곳을 가리키던 non-owning reference는 완전히 다른 대상을 가리키게 됩니다. Memory 자체가 사라질 수도 있습니다.

이 논리 위반을 막기 위해 verifier는 critical section이 끝난 뒤 모든 non-owning reference를 invalidate합니다. 이는 non-owning reference가 "page fault를 일으키지 않는다"는 속성을 보장하는 데 필요합니다. 따라서 verifier가 invalidate하지 않은 non-owning reference에는 page fault 없이 접근할 수 있습니다.

현재 critical section 안에서는 `bpf_obj_drop`이 허용되지 않습니다. 그러므로 유효한 non-owning reference가 있다면 critical section 안에 있는 것이고, reference의 memory가 drop 후 `free`되거나 drop 후 재사용되지 않았다고 결론 내릴 수 있습니다.

Reference type으로 강제하는 node 상태

Rbtree 안에 있는 node를 가리키는 모든 reference는 non-owning이어야 합니다. Tree가 pointee의 lifetime을 제어하기 때문입니다. 마찬가지로 rbtree에 들어 있지 않은 node의 reference는 모두 owning이어야 합니다.

이로써 유용한 속성이 생깁니다. Graph API의 add/remove 구현은 node가 이미 추가됐거나 이미 제거됐는지 확인할 필요가 없습니다. Verifier가 type만 확인해 그런 상태가 유효해지는 것을 ownership model 차원에서 막을 수 있기 때문입니다.

Pointer aliasing이 만드는 반례

그러나 pointer aliasing은 위의 유용한 속성에 문제를 일으킵니다. 다음 예제를 살펴봅니다.

struct node_data *n, *m, *o, *p;
n = bpf_obj_new(typeof(*n));     /* 1 */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n);        /* 2 */
m = bpf_rbtree_first(&tree);     /* 3 */

o = bpf_rbtree_remove(&tree, n); /* 4 */
p = bpf_rbtree_remove(&tree, m); /* 5 */

bpf_spin_unlock(&lock);

bpf_obj_drop(o);
bpf_obj_drop(p); /* 6 */

Aliased reference의 상태 변화

Program 실행 전에 tree가 비어 있다고 가정하고, 위 comment의 번호에 따라 verifier state 변화를 추적하면 다음과 같습니다.

• 1) `n`은 owning reference입니다.
• 2) `n`은 tree에 추가되었으므로 non-owning reference입니다.
• 3) `n`과 `m`은 non-owning reference이고 둘 다 같은 node를 가리킵니다.
• 4) `o`는 owning reference이고 `n`과 `m`은 non-owning reference이며, 셋 모두 같은 node를 가리킵니다.
• 5) `o`와 `p`는 owning이고 `n`과 `m`은 non-owning이며, 넷 모두 같은 node를 가리킵니다.
• 6) `o`와 `p`가 같은 node를 가리키고 이전 statement에서 `o`를 `free`했으므로 double-free가 발생했습니다.

Remove kfunc도 non-owning reference를 invalidate해야 하는 이유

상태 4와 5에는 rbtree 안에 있지 않은 node를 가리키는 non-owning reference가 있으므로 앞서 말한 유용한 속성을 위반합니다. 이 위반 때문에 statement 5는 이미 제거된 node를 다시 제거하려고 하고, 상태 6에서는 위험한 double-free가 발생합니다.

최소한 상태 6은 발생할 수 없도록 해야 합니다. 상태 5까지 막을 수 없다면 유용한 속성을 포기하고 node가 이미 제거됐는지 runtime에 확인해야 합니다.

두 상태 모두 막기 위해 `bpf_spin_unlock`의 "non-owning reference invalidate" 동작을 일반화하고 `bpf_rbtree_remove` 뒤에도 비슷한 invalidation을 수행합니다.

그 근거는 다음 조건을 모두 만족하는 graph API kfunc가

• 임의의 node argument를 받고,
• 그 node를 data structure에서 제거하며,
• 제거한 node의 owning reference를 반환하면,

같은 node를 가리키는 다른 non-owning reference가 남아 있는 상태를 만들 수 있다는 것입니다. 따라서 `remove` type kfunc도 non-owning reference invalidation point로 간주해야 합니다.