1========================= 2BPF Graph Data Structures 3========================= 4 5This document describes implementation details of new-style "graph" data 6structures (linked_list, rbtree), with particular focus on the verifier's 7implementation of semantics specific to those data structures. 8 9Although no specific verifier code is referred to in this document, the document 10assumes that the reader has general knowledge of BPF verifier internals, BPF 11maps, and BPF program writing. 12 13Note that the intent of this document is to describe the current state of 14these graph data structures. **No guarantees** of stability for either 15semantics or APIs are made or implied here. 16 17.. contents:: 18 :local: 19 :depth: 2 20 21Introduction 22------------ 23 24The BPF map API has historically been the main way to expose data structures 25of various types for use within BPF programs. Some data structures fit naturally 26with the map API (HASH, ARRAY), others less so. Consequently, programs 27interacting with the latter group of data structures can be hard to parse 28for kernel programmers without previous BPF experience. 29 30Luckily, some restrictions which necessitated the use of BPF map semantics are 31no longer relevant. With the introduction of kfuncs, kptrs, and the any-context 32BPF allocator, it is now possible to implement BPF data structures whose API 33and semantics more closely match those exposed to the rest of the kernel. 34 35Two such data structures - linked_list and rbtree - have many verification 36details in common. Because both have "root"s ("head" for linked_list) and 37"node"s, the verifier code and this document refer to common functionality 38as "graph_api", "graph_root", "graph_node", etc. 39 40Unless otherwise stated, examples and semantics below apply to both graph data 41structures. 42 43Unstable API 44------------ 45 46Data structures implemented using the BPF map API have historically used BPF 47helper functions - either standard map API helpers like ``bpf_map_update_elem`` 48or map-specific helpers. The new-style graph data structures instead use kfuncs 49to define their manipulation helpers. Because there are no stability guarantees 50for kfuncs, the API and semantics for these data structures can be evolved in 51a way that breaks backwards compatibility if necessary. 52 53Root and node types for the new data structures are opaquely defined in the 54``uapi/linux/bpf.h`` header. 55 56Locking 57------- 58 59The new-style data structures are intrusive and are defined similarly to their 60vanilla kernel counterparts: 61 62.. code-block:: c 63 64 struct node_data { 65 long key; 66 long data; 67 struct bpf_rb_node node; 68 }; 69 70 struct bpf_spin_lock glock; 71 struct bpf_rb_root groot __contains(node_data, node); 72 73The "root" type for both linked_list and rbtree expects to be in a map_value 74which also contains a ``bpf_spin_lock`` - in the above example both global 75variables are placed in a single-value arraymap. The verifier considers this 76spin_lock to be associated with the ``bpf_rb_root`` by virtue of both being in 77the same map_value and will enforce that the correct lock is held when 78verifying BPF programs that manipulate the tree. Since this lock checking 79happens at verification time, there is no runtime penalty. 80 81Non-owning references 82--------------------- 83 84**Motivation** 85 86Consider the following BPF code: 87 88.. code-block:: c 89 90 struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */ 91 92 bpf_spin_lock(&lock); 93 94 bpf_rbtree_add(&tree, n); /* PASSED */ 95 96 bpf_spin_unlock(&lock); 97 98From the verifier's perspective, the pointer ``n`` returned from ``bpf_obj_new`` 99has type ``PTR_TO_BTF_ID | MEM_ALLOC``, with a ``btf_id`` of 100``struct node_data`` and a nonzero ``ref_obj_id``. Because it holds ``n``, the 101program has ownership of the pointee's (object pointed to by ``n``) lifetime. 102The BPF program must pass off ownership before exiting - either via 103``bpf_obj_drop``, which ``free``'s the object, or by adding it to ``tree`` with 104``bpf_rbtree_add``. 105 106(``ACQUIRED`` and ``PASSED`` comments in the example denote statements where 107"ownership is acquired" and "ownership is passed", respectively) 108 109What should the verifier do with ``n`` after ownership is passed off? If the 110object was ``free``'d with ``bpf_obj_drop`` the answer is obvious: the verifier 111should reject programs which attempt to access ``n`` after ``bpf_obj_drop`` as 112the object is no longer valid. The underlying memory may have been reused for 113some other allocation, unmapped, etc. 114 115When ownership is passed to ``tree`` via ``bpf_rbtree_add`` the answer is less 116obvious. The verifier could enforce the same semantics as for ``bpf_obj_drop``, 117but that would result in programs with useful, common coding patterns being 118rejected, e.g.: 119 120.. code-block:: c 121 122 int x; 123 struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */ 124 125 bpf_spin_lock(&lock); 126 127 bpf_rbtree_add(&tree, n); /* PASSED */ 128 x = n->data; 129 n->data = 42; 130 131 bpf_spin_unlock(&lock); 132 133Both the read from and write to ``n->data`` would be rejected. The verifier 134can do better, though, by taking advantage of two details: 135 136 * Graph data structure APIs can only be used when the ``bpf_spin_lock`` 137 associated with the graph root is held 138 139 * Both graph data structures have pointer stability 140 141 * Because graph nodes are allocated with ``bpf_obj_new`` and 142 adding / removing from the root involves fiddling with the 143 ``bpf_{list,rb}_node`` field of the node struct, a graph node will 144 remain at the same address after either operation. 145 146Because the associated ``bpf_spin_lock`` must be held by any program adding 147or removing, if we're in the critical section bounded by that lock, we know 148that no other program can add or remove until the end of the critical section. 149This combined with pointer stability means that, until the critical section 150ends, we can safely access the graph node through ``n`` even after it was used 151to pass ownership. 152 153The verifier considers such a reference a *non-owning reference*. The ref 154returned by ``bpf_obj_new`` is accordingly considered an *owning reference*. 155Both terms currently only have meaning in the context of graph nodes and API. 156 157**Details** 158 159Let's enumerate the properties of both types of references. 160 161*owning reference* 162 163 * This reference controls the lifetime of the pointee 164 165 * Ownership of pointee must be 'released' by passing it to some graph API 166 kfunc, or via ``bpf_obj_drop``, which ``free``'s the pointee 167 168 * If not released before program ends, verifier considers program invalid 169 170 * Access to the pointee's memory will not page fault 171 172*non-owning reference* 173 174 * This reference does not own the pointee 175 176 * It cannot be used to add the graph node to a graph root, nor ``free``'d via 177 ``bpf_obj_drop`` 178 179 * No explicit control of lifetime, but can infer valid lifetime based on 180 non-owning ref existence (see explanation below) 181 182 * Access to the pointee's memory will not page fault 183 184From verifier's perspective non-owning references can only exist 185between spin_lock and spin_unlock. Why? After spin_unlock another program 186can do arbitrary operations on the data structure like removing and ``free``-ing 187via bpf_obj_drop. A non-owning ref to some chunk of memory that was remove'd, 188``free``'d, and reused via bpf_obj_new would point to an entirely different thing. 189Or the memory could go away. 190 191To prevent this logic violation all non-owning references are invalidated by the 192verifier after a critical section ends. This is necessary to ensure the "will 193not page fault" property of non-owning references. So if the verifier hasn't 194invalidated a non-owning ref, accessing it will not page fault. 195 196Currently ``bpf_obj_drop`` is not allowed in the critical section, so 197if there's a valid non-owning ref, we must be in a critical section, and can 198conclude that the ref's memory hasn't been dropped-and- ``free``'d or 199dropped-and-reused. 200 201Any reference to a node that is in an rbtree _must_ be non-owning, since 202the tree has control of the pointee's lifetime. Similarly, any ref to a node 203that isn't in rbtree _must_ be owning. This results in a nice property: 204graph API add / remove implementations don't need to check if a node 205has already been added (or already removed), as the ownership model 206allows the verifier to prevent such a state from being valid by simply checking 207types. 208 209However, pointer aliasing poses an issue for the above "nice property". 210Consider the following example: 211 212.. code-block:: c 213 214 struct node_data *n, *m, *o, *p; 215 n = bpf_obj_new(typeof(*n)); /* 1 */ 216 217 bpf_spin_lock(&lock); 218 219 bpf_rbtree_add(&tree, n); /* 2 */ 220 m = bpf_rbtree_first(&tree); /* 3 */ 221 222 o = bpf_rbtree_remove(&tree, n); /* 4 */ 223 p = bpf_rbtree_remove(&tree, m); /* 5 */ 224 225 bpf_spin_unlock(&lock); 226 227 bpf_obj_drop(o); 228 bpf_obj_drop(p); /* 6 */ 229 230Assume the tree is empty before this program runs. If we track verifier state 231changes here using numbers in above comments: 232 233 1) n is an owning reference 234 235 2) n is a non-owning reference, it's been added to the tree 236 237 3) n and m are non-owning references, they both point to the same node 238 239 4) o is an owning reference, n and m non-owning, all point to same node 240 241 5) o and p are owning, n and m non-owning, all point to the same node 242 243 6) a double-free has occurred, since o and p point to same node and o was 244 ``free``'d in previous statement 245 246States 4 and 5 violate our "nice property", as there are non-owning refs to 247a node which is not in an rbtree. Statement 5 will try to remove a node which 248has already been removed as a result of this violation. State 6 is a dangerous 249double-free. 250 251At a minimum we should prevent state 6 from being possible. If we can't also 252prevent state 5 then we must abandon our "nice property" and check whether a 253node has already been removed at runtime. 254 255We prevent both by generalizing the "invalidate non-owning references" behavior 256of ``bpf_spin_unlock`` and doing similar invalidation after 257``bpf_rbtree_remove``. The logic here being that any graph API kfunc which: 258 259 * takes an arbitrary node argument 260 261 * removes it from the data structure 262 263 * returns an owning reference to the removed node 264 265May result in a state where some other non-owning reference points to the same 266node. So ``remove``-type kfuncs must be considered a non-owning reference 267invalidation point as well. 268