Re: [PATCH RFC bpf-next v1 16/32] bpf: Introduce BPF memory object model

From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
To: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Cc: bpf@vger.kernel.org, Alexei Starovoitov <ast@kernel.org>,
	Andrii Nakryiko <andrii@kernel.org>,
	Daniel Borkmann <daniel@iogearbox.net>,
	Dave Marchevsky <davemarchevsky@fb.com>,
	Delyan Kratunov <delyank@fb.com>
Subject: Re: [PATCH RFC bpf-next v1 16/32] bpf: Introduce BPF memory object model
Date: Wed, 7 Sep 2022 17:34:29 -0700	[thread overview]
Message-ID: <20220908003429.wsucvsdcxnkipcja@macbook-pro-4.dhcp.thefacebook.com> (raw)
In-Reply-To: <20220904204145.3089-17-memxor@gmail.com>

On Sun, Sep 04, 2022 at 10:41:29PM +0200, Kumar Kartikeya Dwivedi wrote:
> Add the concept of a memory object model to BPF verifier.
> 
> What this means is that there are now some types that are not just plain
> old data, but require explicit action when they are allocated on a
> storage, before their lifetime is considered as started and before it is
> allowed for them to escape the program. The verifier will track state of
> such fields during the various phases of the object lifetime, where it
> can be sure about certain invariants.
> 
> Some inspiration is taken from existing memory object and lifetime
> models in C and C++ which have stood the test of time. See [0], [1], [2]
> for more information, to find some similarities. In the future, the
> separation of storage and object lifetime may be made more stark by
> allowing to change effective type of storage allocated for a local kptr.
> For now, that has been left out. It is only possible when verifier
> understands when the program has exclusive access to storage, and when
> the object it is hosting is no longer accessible to other CPUs.
> 
> This can be useful to maintain size-class based freelists inside BPF
> programs and reuse storage of same size for different types. This would
> only be safe to allow if verifier can ensure that while storage lifetime
> has not ended, object lifetime for the current type has. This
> necessiates separating the two and accomodating a simple model to track
> object lifetime (composed recursively of more objects whose lifetime
> is individually tracked).
> 
> Everytime a BPF program allocates such non-trivial types, it must call a
> set of constructors on the object to fully begin its lifetime before it
> can make use of the pointer to this type. If the program does not do so,
> the verifier will complain and lead to failure in loading of the
> program.
> 
> Similarly, when ending the lifetime of such types, it is required to
> fully destruct the object using a series of destructors for each
> non-trivial member, before finally freeing the storage the object is
> making use of.
> 
> During both the construction and destruction phase, there can be only
> one program that can own and access such an object, hence their is no
> need of any explicit synchronization. The single ownership of such
> objects makes it easy for the verifier to enforce the safety around the
> beginning and end of the lifetime without resorting to dynamic checks.
> 
> When there are multiple fields needing construction or destruction, the
> program must call their constructors in ascending order of the offset of
> the field.
> 
> For example, consider the following type (support for such fields will
> be added in subsequent patches):
> 
> struct data {
> 	struct bpf_spin_lock lock;
> 	struct bpf_list_head list __contains(struct, foo, node);
> 	int data;
> };
> 
> struct data *d = bpf_kptr_alloc(...);
> if (!d) { ... }
> 
> Now, the type of d would be PTR_TO_BTF_ID | MEM_TYPE_LOCAL |
> OBJ_CONSTRUCTING, as it needs two constructor calls (for lock and head),
> before it can be considered fully initialized and alive.
> 
> Hence, we must do (in order of field offsets):
> 
> bpf_spin_lock_init(&d->lock);
> bpf_list_head_init(&d->list);

All sounds great in theory, but I think it's unnecessary complex at this point.
There is still a need to __bpf_list_head_init_zeroed as seen in later patches.
So all this verifier enforced constructors we don't need _today_.
Zero init of everything works.
It's the case for list_head, list_node, spin_lock, rb_root, rb_node.
Pretty much all new data structures will work with zero init
and all of them need async dtors.
The verifier cannot help during destruction.
dtors have to be specified declaratively in a bpf prog for new types
and as known kfuncs for list_head/node, rb_root/node.
There will be unfreed link lists in maps and the later patches handle that
without OBJ_DESTRUCTING.
So let's postpone this patch.