Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

[Luc Van Oostenryck]

On Mon, Dec 30, 2019 at 11:32:31AM -0800, Kees Cook wrote:
> On Mon, Dec 30, 2019 at 01:15:47PM -0600, Eric Biggers wrote:
> > 
> > The annotation needs to go in the .h file, not the .c file, because sparse only
> > analyzes individual translation units.
> > 
> > It needs to be a wrapper macro because it needs to tie the acquisition of the
> > lock to the return value being true.  I.e. there's no annotation you can apply
> > directly to the function prototype that means "if this function returns true, it
> > acquires the lock that was passed in parameter N".
> 
> Gotcha. Well, I guess I leave it to Will and Peter to hash out...
> 
> Is there a meaningful proposal anywhere for sparse to DTRT here? If
> not, it seems best to use what you've proposed until sparse reaches the
> point of being able to do this on its own.

What "Right Thing" are you thinking about?
One of the simplest situation with these conditional locks is:

	if (test)
		lock();

	do_stuff();

	if (test)
		unlock();

No program can check that the second test gives the same result than
the first one, it's undecidable. I mean, it's undecidable even on
if single threaded and without interrupts. The best you can do is
to simulate the whole thing (and be sure your simulation will halt).

As far as I understand, it was the intention behind Sparse's design
regarding locking ("context in sparse's parlance) to discourage
such code and instead encourage to write things like:

	if (test) {
		do_stuff_unlocked();
	} else {
		lock();
		do_stuff_unlocked();
		unlock();
	}

where it is easy to check localy that the lock/unlock are balanced.

So, of course Sparse could be improved to prove that some of the
conditional locks are equivalent to unconditional ones like here
just above (it already does but only for very simple cases where
everything is inlined) but I don't thing there is a RT.

-- Luc Van Oostenryck

Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

[Linus Torvalds]

On Mon, Dec 30, 2019 at 3:38 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> One of the simplest situation with these conditional locks is:
>
>         if (test)
>                 lock();
>
>         do_stuff();
>
>         if (test)
>                 unlock();
>
> No program can check that the second test gives the same result than
> the first one, it's undecidable. I mean, it's undecidable even on
> if single threaded and without interrupts. The best you can do is
> to simulate the whole thing (and be sure your simulation will halt).

No, no.

It's undecidable in the general case, but it's usually actually
trivially decidable in most real-world kernel cases.

Because "test" tends to be an argument to the function (or one bit of
an argument), and after it has been turned into SSA form, it's
literally using the same exact register for the conditional thanks to
CSE and simplification.

Perhaps not every time, but I bet it would be most times.

So I guess sparse could in theory notice that certain basic blocks are
conditional on the same thing, so if one is done, then the other is
always done (assuming there is conditional branch out in between, of
course).

IOW, the context tracking *could* do check son a bigger state than
just one basic block. It doesn't, and it would probably be painful to
do, but it's certainly not impossible.

So to make a trivial example for sparse:

    extern int testfn(int);
    extern int do_something(void);

    int testfn(int flag)
    {
        if (flag & 1)
                __context__(1);
        do_something();
        if (flag & 1)
                __context__(-1);
    }

this causes a warning:

    c.c:4:5: warning: context imbalance in 'testfn' - different lock
contexts for basic block

because "do_something()" is called with different lock contexts. And
that's definitely a real issue. But if we were to want to extend the
"make sure we enter/exit with the same lock context", we _could_ do
it, because look at the linearization:

    testfn:
    .L0:
        <entry-point>
        and.32      %r2 <- %arg1, $1
        cbr         %r2, .L1, .L2
    .L1:
        context     1
        br          .L2
    .L2:
        call.32     %r4 <- do_something
        cbr         %r2, .L3, .L5
    .L3:
        context     -1
        br          .L5
    .L5:
        ret.32      UNDEF

becasue the conditional branch always uses "%r2" as the conditional.
Notice? Not at all undecideable, and it would not be *impossible* to
say that "we can see that all context changes are conditional on %r2
not being true".

So sparse has already done all the real work to know that the two "if
(test)" conditionals test the exact same thing. We _know_ that the
second test has the same result as the first test, we're using the
same SSA register for both of them!

              Linus

Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

[Luc Van Oostenryck]

On Thu, Jan 02, 2020 at 05:35:34PM -0800, Linus Torvalds wrote:
> On Mon, Dec 30, 2019 at 3:38 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > One of the simplest situation with these conditional locks is:
> >
> >         if (test)
> >                 lock();
> >
> >         do_stuff();
> >
> >         if (test)
> >                 unlock();
> >
> > No program can check that the second test gives the same result than
> > the first one, it's undecidable. I mean, it's undecidable even on
> > if single threaded and without interrupts. The best you can do is
> > to simulate the whole thing (and be sure your simulation will halt).
> 
> No, no.
> 
> It's undecidable in the general case, but it's usually actually
> trivially decidable in most real-world kernel cases.
> 
> Because "test" tends to be an argument to the function (or one bit of
> an argument), and after it has been turned into SSA form, it's
> literally using the same exact register for the conditional thanks to
> CSE and simplification.
> 
> Perhaps not every time, but I bet it would be most times.

Yes, sure. I was, in fact, speaking for for all the cases where
'test' is more complex than an argument or local var. When I looked
at these false warnings about context imbalance, maybe 18 months ago,
my vague impression was that in most cases the test contained a pointer
dereference or worse. But I didn't look much.

> So I guess sparse could in theory notice that certain basic blocks are
> conditional on the same thing, so if one is done, then the other is
> always done (assuming there is conditional branch out in between, of
> course).
> 
> IOW, the context tracking *could* do check son a bigger state than
> just one basic block. It doesn't, and it would probably be painful to
> do, but it's certainly not impossible.
> 
> So to make a trivial example for sparse:
> 
>     extern int testfn(int);
>     extern int do_something(void);
> 
>     int testfn(int flag)
>     {
>         if (flag & 1)
>                 __context__(1);
>         do_something();
>         if (flag & 1)
>                 __context__(-1);
>     }
> 
> this causes a warning:
> 
>     c.c:4:5: warning: context imbalance in 'testfn' - different lock
> contexts for basic block
> 
> because "do_something()" is called with different lock contexts. And
> that's definitely a real issue. But if we were to want to extend the
> "make sure we enter/exit with the same lock context", we _could_ do
> it, because look at the linearization:
> 
>     testfn:
>     .L0:
>         <entry-point>
>         and.32      %r2 <- %arg1, $1
>         cbr         %r2, .L1, .L2
>     .L1:
>         context     1
>         br          .L2
>     .L2:
>         call.32     %r4 <- do_something
>         cbr         %r2, .L3, .L5
>     .L3:
>         context     -1
>         br          .L5
>     .L5:
>         ret.32      UNDEF
> 
> becasue the conditional branch always uses "%r2" as the conditional.
> Notice? Not at all undecideable, and it would not be *impossible* to
> say that "we can see that all context changes are conditional on %r2
> not being true".
> 
> So sparse has already done all the real work to know that the two "if
> (test)" conditionals test the exact same thing. We _know_ that the
> second test has the same result as the first test, we're using the
> same SSA register for both of them!

Absolutely. I'm more than willing to look at this but I just fear
that in most cases the conditional is more complex. I'll make
some investigations.

-- Luc

Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

[Dan Carpenter]

I re-wrote Smatch's locking check last month to use the cross function
DB.  Now Smatch can parse refcount_dec_and_lock() directly without any
modifications or annotations.

regards,
dan carpenter

Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

[Peter Zijlstra]

On Tue, Dec 31, 2019 at 12:38:14AM +0100, Luc Van Oostenryck wrote:
> On Mon, Dec 30, 2019 at 11:32:31AM -0800, Kees Cook wrote:
> > On Mon, Dec 30, 2019 at 01:15:47PM -0600, Eric Biggers wrote:
> > > 
> > > The annotation needs to go in the .h file, not the .c file, because sparse only
> > > analyzes individual translation units.
> > > 
> > > It needs to be a wrapper macro because it needs to tie the acquisition of the
> > > lock to the return value being true.  I.e. there's no annotation you can apply
> > > directly to the function prototype that means "if this function returns true, it
> > > acquires the lock that was passed in parameter N".
> > 
> > Gotcha. Well, I guess I leave it to Will and Peter to hash out...
> > 
> > Is there a meaningful proposal anywhere for sparse to DTRT here? If
> > not, it seems best to use what you've proposed until sparse reaches the
> > point of being able to do this on its own.
> 
> What "Right Thing" are you thinking about?
> One of the simplest situation with these conditional locks is:
> 
> 	if (test)
> 		lock();
> 
> 	do_stuff();
> 
> 	if (test)
> 		unlock();
> 
> No program can check that the second test gives the same result than
> the first one, it's undecidable. I mean, it's undecidable even on
> if single threaded and without interrupts. The best you can do is
> to simulate the whole thing (and be sure your simulation will halt).

Not quite what we're talking about. Instead consider this:

The normal flow would be something like:

extern void spin_lock(spinlock_t *lock) __acquires(lock);
extern void spin_unlock(spinlock_t *lock) __releases(lock);

extern bool _spin_trylock(spinlock_t *lock) __acquires(lock);

#define __cond_lock(x, c) ((c) ? ({ __acquire(x); 1; }) : 0)
#define spin_trylock(lock) __cond_lock(lock, _spin_lock)


	if (spin_trylock(lock)) {

		/* do crap */

		spin_unlock();
	}


So the proposal here:

  https://markmail.org/message/4obybcgqscznnx63

would have us write:

extern bool spin_trylock(spinlock_t *lock) __attribute__((context(lock, 0, spin_trylock(lock));

Basically have sparse do a transform on its own expression tree and
inject the very same crud we now do manually. This avoids cluttering the
kernel tree with this nonsense.

Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

[Luc Van Oostenryck]

On Mon, Jan 06, 2020 at 04:41:19PM +0100, Peter Zijlstra wrote:
> On Tue, Dec 31, 2019 at 12:38:14AM +0100, Luc Van Oostenryck wrote:

...
 
> Not quite what we're talking about. Instead consider this:
> 
> The normal flow would be something like:
> 
> extern void spin_lock(spinlock_t *lock) __acquires(lock);
> extern void spin_unlock(spinlock_t *lock) __releases(lock);
> 
> extern bool _spin_trylock(spinlock_t *lock) __acquires(lock);
> 
> #define __cond_lock(x, c) ((c) ? ({ __acquire(x); 1; }) : 0)
> #define spin_trylock(lock) __cond_lock(lock, _spin_lock)
> 
> 
> 	if (spin_trylock(lock)) {
> 
> 		/* do crap */
> 
> 		spin_unlock();
> 	}
> 
> 
> So the proposal here:
> 
>   https://markmail.org/message/4obybcgqscznnx63
> 
> would have us write:
> 
> extern bool spin_trylock(spinlock_t *lock) __attribute__((context(lock, 0, spin_trylock(lock));

Well, allowing arbitrary conditions would be hard/impossible but you're
only asking to have the *return value* as condition, right? That looks
as reasonably feasible.

> Basically have sparse do a transform on its own expression tree and
> inject the very same crud we now do manually. This avoids cluttering the
> kernel tree with this nonsense.

So, a call of a function declared with __acquires() or releases() is
interpreted by Sparse as if the call is immediately followed by an
increase or a decrease of the context. It wouldn't be very hard to
add a new attribute (something like __cond_context) and let Sparse do
as if a call to a function with such attribute is directly followed
by a test of its return value and a corresponding change in the context.
It would boil down to:

	extern bool spin_trylock(lock) __cond_context(lock);

	if (spin_trylock(lock)) {
		/* do crap */
		spin_unlock();
	}

behaving like the following code currently would:

	extern bool spin_trylock(lock);

	if (spin_trylock(lock)) {
		__acquire(lock);
		/* do crap */
		spin_unlock();
	}


Would something like this be satisfactory?

-- Luc

Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

[Peter Zijlstra]

On Mon, Jan 06, 2020 at 06:54:59PM +0100, Luc Van Oostenryck wrote:
> On Mon, Jan 06, 2020 at 04:41:19PM +0100, Peter Zijlstra wrote:

> > extern bool spin_trylock(spinlock_t *lock) __attribute__((context(lock, 0, spin_trylock(lock));
> 
> Well, allowing arbitrary conditions would be hard/impossible but you're
> only asking to have the *return value* as condition, right? That looks
> as reasonably feasible.

Just the return value would cover all the known cases yes. At the time
I might have been somewhat over ambitious..

> > Basically have sparse do a transform on its own expression tree and
> > inject the very same crud we now do manually. This avoids cluttering the
> > kernel tree with this nonsense.
> 
> So, a call of a function declared with __acquires() or releases() is
> interpreted by Sparse as if the call is immediately followed by an
> increase or a decrease of the context. It wouldn't be very hard to
> add a new attribute (something like __cond_context) and let Sparse do
> as if a call to a function with such attribute is directly followed
> by a test of its return value and a corresponding change in the context.
> It would boil down to:
> 
> 	extern bool spin_trylock(lock) __cond_context(lock);
> 
> 	if (spin_trylock(lock)) {
> 		/* do crap */
> 		spin_unlock();
> 	}
> 
> behaving like the following code currently would:
> 
> 	extern bool spin_trylock(lock);
> 
> 	if (spin_trylock(lock)) {
> 		__acquire(lock);
> 		/* do crap */
> 		spin_unlock();
> 	}
> 
> 
> Would something like this be satisfactory?

Very much so, Thanks!

Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions

[Peter Zijlstra]

On Mon, Dec 30, 2019 at 11:32:31AM -0800, Kees Cook wrote:

> Is there a meaningful proposal anywhere for sparse to DTRT here?

These are what I found going through my Sent folder and Google'ing the
resulting subjects:

  https://markmail.org/message/4obybcgqscznnx63
  https://markmail.org/message/pp4ofksgactvgjbd?q=inverted_lock

> If
> not, it seems best to use what you've proposed until sparse reaches the
> point of being able to do this on its own.

Or just leave the silly sparse warning, they're easy to ignore.