Lines Matching +full:lock +full:- +full:less
5 This document describes implementation details of new-style "graph" data
22 ------------
26 with the map API (HASH, ARRAY), others less so. Consequently, programs
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
77 the same map_value and will enforce that the correct lock is held when
78 verifying BPF programs that manipulate the tree. Since this lock checking
81 Non-owning references
82 ---------------------
88 .. code-block:: c
92 bpf_spin_lock(&lock);
96 bpf_spin_unlock(&lock);
102 The BPF program must pass off ownership before exiting - either via
115 When ownership is passed to ``tree`` via ``bpf_rbtree_add`` the answer is less
120 .. code-block:: c
125 bpf_spin_lock(&lock);
128 x = n->data;
129 n->data = 42;
131 bpf_spin_unlock(&lock);
133 Both the read from and write to ``n->data`` would be rejected. The verifier
147 or removing, if we're in the critical section bounded by that lock, we know
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,
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
217 bpf_spin_lock(&lock);
225 bpf_spin_unlock(&lock);
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