Documentation/bpf/graph_ds_impl.rst

Source file repositories/reference/linux-study-clean/Documentation/bpf/graph_ds_impl.rst

File Facts

System
Linux kernel
Corpus path
Documentation/bpf/graph_ds_impl.rst
Extension
.rst
Size
10467 bytes
Lines
268
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

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);

The "root" type for both linked_list and rbtree expects to be in a map_value
which also contains a ``bpf_spin_lock`` - in the above example both global
variables are placed in a single-value arraymap. The verifier considers this
spin_lock to be associated with the ``bpf_rb_root`` by virtue of both being in
the same map_value and will enforce that the correct lock is held when
verifying BPF programs that manipulate the tree. Since this lock checking
happens at verification time, there is no runtime penalty.

Non-owning references
---------------------

**Motivation**

Consider the following BPF code:

.. code-block:: c

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

        bpf_spin_lock(&lock);

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

        bpf_spin_unlock(&lock);

From the verifier's perspective, the pointer ``n`` returned from ``bpf_obj_new``
has type ``PTR_TO_BTF_ID | MEM_ALLOC``, with a ``btf_id`` of
``struct node_data`` and a nonzero ``ref_obj_id``. Because it holds ``n``, the
program has ownership of the pointee's (object pointed to by ``n``) lifetime.
The BPF program must pass off ownership before exiting - either via
``bpf_obj_drop``, which ``free``'s the object, or by adding it to ``tree`` with
``bpf_rbtree_add``.

(``ACQUIRED`` and ``PASSED`` comments in the example denote statements where
"ownership is acquired" and "ownership is passed", respectively)

What should the verifier do with ``n`` after ownership is passed off? If the
object was ``free``'d with ``bpf_obj_drop`` the answer is obvious: the verifier
should reject programs which attempt to access ``n`` after ``bpf_obj_drop`` as
the object is no longer valid. The underlying memory may have been reused for
some other allocation, unmapped, etc.

When ownership is passed to ``tree`` via ``bpf_rbtree_add`` the answer is less
obvious. The verifier could enforce the same semantics as for ``bpf_obj_drop``,
but that would result in programs with useful, common coding patterns being
rejected, e.g.:

.. code-block:: c

        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);

Both the read from and write to ``n->data`` would be rejected. The verifier

Annotation

Implementation Notes