Lines Matching +full:no +full:- +full:map

5 This document describes implementation details of new-style "graph" data
9 Although no specific verifier code is referred to in this document, the document
14 these graph data structures. **No guarantees** of stability for either
22 ------------
24 The BPF map API has historically been the main way to expose data structures
26 with the map API (HASH, ARRAY), others less so. Consequently, programs
30 Luckily, some restrictions which necessitated the use of BPF map semantics are
31 no longer relevant. With the introduction of kfuncs, kptrs, and the any-context
35 Two such data structures - linked_list and rbtree - have many verification
44 ------------
46 Data structures implemented using the BPF map API have historically used BPF
47 helper functions - either standard map API helpers like ``bpf_map_update_elem``
48 or map-specific helpers. The new-style graph data structures instead use kfuncs
49 to define their manipulation helpers. Because there are no stability guarantees
57 -------
59 The new-style data structures are intrusive and are defined similarly to their
62 .. code-block:: c
74 which also contains a ``bpf_spin_lock`` - in the above example both global
75 variables are placed in a single-value arraymap. The verifier considers this
79 happens at verification time, there is no runtime penalty.
81 Non-owning references
82 ---------------------
88 .. code-block:: c
102 The BPF program must pass off ownership before exiting - either via
112 the object is no longer valid. The underlying memory may have been reused for
120 .. code-block:: c
128         x = n->data;
129         n->data = 42;
133 Both the read from and write to ``n->data`` would be rejected. The verifier
148 that no other program can add or remove until the end of the critical section.
153 The verifier considers such a reference a *non-owning reference*. The ref
172 *non-owning reference*
179   * No explicit control of lifetime, but can infer valid lifetime based on
180     non-owning ref existence (see explanation below)
184 From verifier's perspective non-owning references can only exist
186 can do arbitrary operations on the data structure like removing and ``free``-ing
187 via bpf_obj_drop. A non-owning ref to some chunk of memory that was remove'd,
191 To prevent this logic violation all non-owning references are invalidated by the
193 not page fault" property of non-owning references. So if the verifier hasn't
194 invalidated a non-owning ref, accessing it will not page fault.
197 if there's a valid non-owning ref, we must be in a critical section, and can
198 conclude that the ref's memory hasn't been dropped-and- ``free``'d or
199 dropped-and-reused.
201 Any reference to a node that is in an rbtree _must_ be non-owning, since
212 .. code-block:: c
235   2) n is a non-owning reference, it's been added to the tree
237   3) n and m are non-owning references, they both point to the same node
239   4) o is an owning reference, n and m non-owning, all point to same node
241   5) o and p are owning, n and m non-owning, all point to the same node
243   6) a double-free has occurred, since o and p point to same node and o was
246 States 4 and 5 violate our "nice property", as there are non-owning refs to
249 double-free.
255 We prevent both by generalizing the "invalidate non-owning references" behavior
265 May result in a state where some other non-owning reference points to the same
266 node. So ``remove``-type kfuncs must be considered a non-owning reference