Re: [RFC PATCH bpf-next 05/11] bpf: Add bpf_spin_lock member to rbtree

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

On Tue, 2 Aug 2022 at 00:23, Alexei Starovoitov <ast@fb.com> wrote:
>
> On 7/22/22 11:34 AM, Dave Marchevsky wrote:
> > This patch adds a struct bpf_spin_lock *lock member to bpf_rbtree, as
> > well as a bpf_rbtree_get_lock helper which allows bpf programs to access
> > the lock.
> >
> > Ideally the bpf_spin_lock would be created independently oustide of the
> > tree and associated with it before the tree is used, either as part of
> > map definition or via some call like rbtree_init(&rbtree, &lock). Doing
> > this in an ergonomic way is proving harder than expected, so for now use
> > this workaround.
> >
> > Why is creating the bpf_spin_lock independently and associating it with
> > the tree preferable? Because we want to be able to transfer nodes
> > between trees atomically, and for this to work need same lock associated
> > with 2 trees.
>
> Right. We need one lock to protect multiple rbtrees.
> Since add/find/remove helpers will look into rbtree->lock
> the two different rbtree (== map) have to point to the same lock.
> Other than rbtree_init(&rbtree, &lock) what would be an alternative ?
>

Instead of dynamically associating locks with the rbtree map, why not
have lock embedded with the rbtree map, and construct a global locking
order among rbtree maps during prog load time that the verifier
maintains globally.

Prog A always takes rb_mapA.lock, then rb_mapB.lock,
If we see Prog B being loaded and it takes them in opposite order, we
reject the load because it can lead to ABBA deadlock. We also know the
map pointer statically so we ensure rb_mapA.lock cannot be called
recursively.

Everytime a prog is loaded, it validates against this single list of
lock orders amongst maps. Some of them may not have interdependencies
at all. There is a single total order, and any cycles lead to
verification failure. This might also work out for normal
bpf_spin_locks allowing us to take more than 1 at a time.

Then you can do moves atomically across two maps, by acquiring the
locks for both. Maybe we limit this to two locks for now only. There
could also be a C++ style std::lock{lock1, lock2} helper that takes
multiple locks to acquire in order, if you want to prevent anything
from happening between those two calls; just an idea.

Probably need to make rb_node add/find helpers notrace so that the bpf
program does not invoke lock again recursively when invoked from the
helper.

Then you can embed locked state statically in map pointer reg, and you
don't need to dynamically check whether map is locked. It will be
passed into the helpers, and from there a member offset can be fixed
which indicates whether the map is 'locked'.

If you have already explored this, then please share what the
problems/limitations were that you ran into, or if this is impossible.
It does sound too good to be true, so maybe I missed something
important here.

I was prototyping something similar for the pifomap in the XDP
queueing series, where we were exploring exposing the underlying
locking of the map to the user (to be able to batch insertions to the
map). The major concern was leaking too many implementation details to
the UAPI and locking (pun intended) ourselves out of improvements to
the map implementation later, so we held off on that for now (and also
wanted to evaluate other alternatives before doubling down on it).