Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

[Alexei Starovoitov <alexei.starovoitov@gmail.com>]

On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> 
> Thanks for having kernel/locking people on Cc...
> 
> On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> 
> > Implementation details:
> > - on !SMP bpf_spin_lock() becomes nop
> 
> Because no BPF program is preemptible? I don't see any assertions or
> even a comment that says this code is non-preemptible.
> 
> AFAICT some of the BPF_RUN_PROG things are under rcu_read_lock() only,
> which is not sufficient.

nope. all bpf prog types disable preemption. That is must have for all
sorts of things to work properly.
If there is a prog type that doing rcu_read_lock only it's a serious bug.
About a year or so ago we audited everything specifically to make
sure everything disables preemption before calling bpf progs.
I'm pretty sure nothing crept in in the mean time.

> > - on architectures that don't support queued_spin_lock trivial lock is used.
> >   Note that arch_spin_lock cannot be used, since not all archs agree that
> >   zero == unlocked and sizeof(arch_spinlock_t) != sizeof(__u32).
> 
> I really don't much like direct usage of qspinlock; esp. not as a
> surprise.
> 
> Why does it matter if 0 means unlocked; that's what
> __ARCH_SPIN_LOCK_UNLOCKED is for.
> 
> I get the sizeof(__u32) thing, but why not key off of that?

what do you mean by 'key off of that' ?
to use arch_spinlock_t instead of qspinlock ?
That was my first attempt, but then I painfully found that
its size on parisc is 16 bytes and we're not going to penalize bpf
to waste that much space because of single architecture.
sizeof(arch_spinlock_t) can be 1 byte too (on sparc).
That would fit in __u32, but I figured it's cleaner to use qspinlock
on all archs that support it and dumb_spin_lock on archs that dont.

Another option is use to arch_spinlock_t when its sizeof==4
and use dumb_spin_lock otherwise.
It's doable, but imo still less clean than using qspinlock
due to zero init. Since zero init is a lot less map work
that zero inits all elements already.

If arch_spinlock_t is used than at map init time we would need to
walk all elements and do __ARCH_SPIN_LOCK_UNLOCKED assignment
(and maps can have millions of elements).
Not horrible, but 100% waste of cycles for x86/arm64 where qspinlock
is used. Such waste can be workaround further by doing ugly
#idef __ARCH_SPIN_LOCK_UNLOCKED == 0 -> don't do init loop.
And then add another #ifdef for archs with sizeof(arch_spinlock_t)!=4
to keep zero init for all map types that support bpf_spin_lock
via dumb_spin_lock.
Clearly at that point we're getting into ugliness everywhere.
Hence I've used qspinlock directly.

> > Next steps:
> > - allow bpf_spin_lock in other map types (like cgroup local storage)
> > - introduce BPF_F_LOCK flag for bpf_map_update() syscall and helper
> >   to request kernel to grab bpf_spin_lock before rewriting the value.
> >   That will serialize access to map elements.
> 
> So clearly this map stuff is shared between bpf proglets, otherwise
> there would not be a need for locking. But what happens if one is from
> task context and another from IRQ context?
> 
> I don't see a local_irq_save()/restore() anywhere. What avoids the
> trivial lock inversion?

> and from NMI ...

progs are not preemptable and map syscall accessors have bpf_prog_active counters.
So nmi/kprobe progs will not be running when syscall is running.
Hence dead lock is not possible and irq_save is not needed.

> > diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> > index a74972b07e74..2e98e4caf5aa 100644
> > --- a/kernel/bpf/helpers.c
> > +++ b/kernel/bpf/helpers.c
> > @@ -221,6 +221,63 @@ const struct bpf_func_proto bpf_get_current_comm_proto = {
> >  	.arg2_type	= ARG_CONST_SIZE,
> >  };
> >  
> > +#ifndef CONFIG_QUEUED_SPINLOCKS
> > +struct dumb_spin_lock {
> > +	atomic_t val;
> > +};
> > +#endif
> > +
> > +notrace BPF_CALL_1(bpf_spin_lock, struct bpf_spin_lock *, lock)
> > +{
> > +#if defined(CONFIG_SMP)
> > +#ifdef CONFIG_QUEUED_SPINLOCKS
> > +	struct qspinlock *qlock = (void *)lock;
> > +
> > +	BUILD_BUG_ON(sizeof(*qlock) != sizeof(*lock));
> > +	queued_spin_lock(qlock);
> > +#else
> > +	struct dumb_spin_lock *qlock = (void *)lock;
> > +
> > +	BUILD_BUG_ON(sizeof(*qlock) != sizeof(*lock));
> > +	do {
> > +		while (atomic_read(&qlock->val) != 0)
> > +			cpu_relax();
> > +	} while (atomic_cmpxchg(&qlock->val, 0, 1) != 0);
> > +#endif
> > +#endif
> > +	return 0;
> > +}
> > +
> > +const struct bpf_func_proto bpf_spin_lock_proto = {
> > +	.func		= bpf_spin_lock,
> > +	.gpl_only	= false,
> > +	.ret_type	= RET_VOID,
> > +	.arg1_type	= ARG_PTR_TO_SPIN_LOCK,
> > +};
> > +
> > +notrace BPF_CALL_1(bpf_spin_unlock, struct bpf_spin_lock *, lock)
> > +{
> > +#if defined(CONFIG_SMP)
> > +#ifdef CONFIG_QUEUED_SPINLOCKS
> > +	struct qspinlock *qlock = (void *)lock;
> > +
> > +	queued_spin_unlock(qlock);
> > +#else
> > +	struct dumb_spin_lock *qlock = (void *)lock;
> > +
> > +	atomic_set(&qlock->val, 0);
> 
> And this is broken... That should've been atomic_set_release() at the
> very least.

right. good catch.

> And this would again be the moment where I go pester you about the BPF
> memory model :-)

hehe :)
How do you propose to define it in a way that it applies to all archs
and yet doesn't penalize x86 ?
"Assume minimum execution ordering model" the way kernel does
unfortunately is not usable, since bpf doesn't have a luxury
of using nice #defines that convert into nops on x86.