Lines Matching +full:2 +full:- +full:point

5 This document describes implementation details of new-style "graph" data
19     :depth: 2
22 ------------
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 ------------
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
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
81 Non-owning references
82 ---------------------
88 .. code-block:: c
102 The BPF program must pass off ownership before exiting - either via
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
153 The verifier considers such a reference a *non-owning reference*. The ref
172 *non-owning reference*
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,
188 ``free``'d, and reused via bpf_obj_new would point to an entirely different thing.
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
219         bpf_rbtree_add(&tree, n);        /* 2 */
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
267 invalidation point as well.