linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
@ 2019-12-26 15:29 Eric Biggers
  2019-12-28 11:49 ` Peter Zijlstra
  0 siblings, 1 reply; 14+ messages in thread
From: Eric Biggers @ 2019-12-26 15:29 UTC (permalink / raw)
  To: linux-kernel, Ingo Molnar, Peter Zijlstra, Will Deacon
  Cc: Elena Reshetova, Thomas Gleixner, Kees Cook, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior

From: Eric Biggers <ebiggers@google.com>

Wrap refcount_dec_and_lock() and refcount_dec_and_lock_irqsave() with
macros using __cond_lock() so that 'sparse' doesn't report warnings
about unbalanced locking when using them.

This is the same thing that's done for their atomic_t equivalents.

Don't annotate refcount_dec_and_mutex_lock(), because mutexes don't
currently have sparse annotations.

Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 include/linux/refcount.h | 45 ++++++++++++++++++++++++++++++++++++----
 lib/refcount.c           | 39 +++++-----------------------------
 2 files changed, 46 insertions(+), 38 deletions(-)

diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index 0ac50cf62d06..6bb5ab9e98ed 100644
--- a/include/linux/refcount.h
+++ b/include/linux/refcount.h
@@ -300,8 +300,45 @@ static inline void refcount_dec(refcount_t *r)
 extern __must_check bool refcount_dec_if_one(refcount_t *r);
 extern __must_check bool refcount_dec_not_one(refcount_t *r);
 extern __must_check bool refcount_dec_and_mutex_lock(refcount_t *r, struct mutex *lock);
-extern __must_check bool refcount_dec_and_lock(refcount_t *r, spinlock_t *lock);
-extern __must_check bool refcount_dec_and_lock_irqsave(refcount_t *r,
-						       spinlock_t *lock,
-						       unsigned long *flags);
+
+/**
+ * refcount_dec_and_lock - return holding spinlock if able to decrement
+ *                         refcount to 0
+ * @r: the refcount
+ * @lock: the spinlock to be locked
+ *
+ * Similar to atomic_dec_and_lock(), it will WARN on underflow and fail to
+ * decrement when saturated at REFCOUNT_SATURATED.
+ *
+ * Provides release memory ordering, such that prior loads and stores are done
+ * before, and provides a control dependency such that free() must come after.
+ * See the comment on top.
+ *
+ * Return: true and hold spinlock if able to decrement refcount to 0, false
+ *         otherwise
+ */
+extern __must_check bool _refcount_dec_and_lock(refcount_t *r,
+						spinlock_t *lock);
+#define refcount_dec_and_lock(r, lock) \
+	__cond_lock(lock, _refcount_dec_and_lock(r, lock))
+
+/**
+ * refcount_dec_and_lock_irqsave - return holding spinlock with disabled
+ *                                 interrupts if able to decrement refcount to 0
+ * @r: the refcount
+ * @lock: the spinlock to be locked
+ * @flags: saved IRQ-flags if the is acquired
+ *
+ * Same as refcount_dec_and_lock() above except that the spinlock is acquired
+ * with disabled interrupts.
+ *
+ * Return: true and hold spinlock if able to decrement refcount to 0, false
+ *         otherwise
+ */
+extern __must_check bool _refcount_dec_and_lock_irqsave(refcount_t *r,
+							spinlock_t *lock,
+							unsigned long *flags);
+#define refcount_dec_and_lock_irqsave(r, lock, flags) \
+	__cond_lock(lock, _refcount_dec_and_lock_irqsave(r, lock, flags))
+
 #endif /* _LINUX_REFCOUNT_H */
diff --git a/lib/refcount.c b/lib/refcount.c
index ebac8b7d15a7..f0eb996b28c0 100644
--- a/lib/refcount.c
+++ b/lib/refcount.c
@@ -125,23 +125,7 @@ bool refcount_dec_and_mutex_lock(refcount_t *r, struct mutex *lock)
 }
 EXPORT_SYMBOL(refcount_dec_and_mutex_lock);
 
-/**
- * refcount_dec_and_lock - return holding spinlock if able to decrement
- *                         refcount to 0
- * @r: the refcount
- * @lock: the spinlock to be locked
- *
- * Similar to atomic_dec_and_lock(), it will WARN on underflow and fail to
- * decrement when saturated at REFCOUNT_SATURATED.
- *
- * Provides release memory ordering, such that prior loads and stores are done
- * before, and provides a control dependency such that free() must come after.
- * See the comment on top.
- *
- * Return: true and hold spinlock if able to decrement refcount to 0, false
- *         otherwise
- */
-bool refcount_dec_and_lock(refcount_t *r, spinlock_t *lock)
+bool _refcount_dec_and_lock(refcount_t *r, spinlock_t *lock)
 {
 	if (refcount_dec_not_one(r))
 		return false;
@@ -154,23 +138,10 @@ bool refcount_dec_and_lock(refcount_t *r, spinlock_t *lock)
 
 	return true;
 }
-EXPORT_SYMBOL(refcount_dec_and_lock);
+EXPORT_SYMBOL(_refcount_dec_and_lock);
 
-/**
- * refcount_dec_and_lock_irqsave - return holding spinlock with disabled
- *                                 interrupts if able to decrement refcount to 0
- * @r: the refcount
- * @lock: the spinlock to be locked
- * @flags: saved IRQ-flags if the is acquired
- *
- * Same as refcount_dec_and_lock() above except that the spinlock is acquired
- * with disabled interupts.
- *
- * Return: true and hold spinlock if able to decrement refcount to 0, false
- *         otherwise
- */
-bool refcount_dec_and_lock_irqsave(refcount_t *r, spinlock_t *lock,
-				   unsigned long *flags)
+bool _refcount_dec_and_lock_irqsave(refcount_t *r, spinlock_t *lock,
+				    unsigned long *flags)
 {
 	if (refcount_dec_not_one(r))
 		return false;
@@ -183,4 +154,4 @@ bool refcount_dec_and_lock_irqsave(refcount_t *r, spinlock_t *lock,
 
 	return true;
 }
-EXPORT_SYMBOL(refcount_dec_and_lock_irqsave);
+EXPORT_SYMBOL(_refcount_dec_and_lock_irqsave);
-- 
2.24.1


^ permalink raw reply related	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-26 15:29 [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions Eric Biggers
@ 2019-12-28 11:49 ` Peter Zijlstra
  2019-12-28 20:15   ` Eric Biggers
  2019-12-30 18:43   ` Kees Cook
  0 siblings, 2 replies; 14+ messages in thread
From: Peter Zijlstra @ 2019-12-28 11:49 UTC (permalink / raw)
  To: Eric Biggers
  Cc: linux-kernel, Ingo Molnar, Will Deacon, Elena Reshetova,
	Thomas Gleixner, Kees Cook, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior

On Thu, Dec 26, 2019 at 09:29:22AM -0600, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> Wrap refcount_dec_and_lock() and refcount_dec_and_lock_irqsave() with
> macros using __cond_lock() so that 'sparse' doesn't report warnings
> about unbalanced locking when using them.
> 
> This is the same thing that's done for their atomic_t equivalents.
> 
> Don't annotate refcount_dec_and_mutex_lock(), because mutexes don't
> currently have sparse annotations.

I so f'ing hate that __cond_lock() crap. Previously I've suggested
fixing sparse instead of making such an atrocious trainwreck of the
code.

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-28 11:49 ` Peter Zijlstra
@ 2019-12-28 20:15   ` Eric Biggers
  2019-12-30 18:43   ` Kees Cook
  1 sibling, 0 replies; 14+ messages in thread
From: Eric Biggers @ 2019-12-28 20:15 UTC (permalink / raw)
  To: Peter Zijlstra
  Cc: linux-kernel, Ingo Molnar, Will Deacon, Elena Reshetova,
	Thomas Gleixner, Kees Cook, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior

On Sat, Dec 28, 2019 at 12:49:18PM +0100, Peter Zijlstra wrote:
> On Thu, Dec 26, 2019 at 09:29:22AM -0600, Eric Biggers wrote:
> > From: Eric Biggers <ebiggers@google.com>
> > 
> > Wrap refcount_dec_and_lock() and refcount_dec_and_lock_irqsave() with
> > macros using __cond_lock() so that 'sparse' doesn't report warnings
> > about unbalanced locking when using them.
> > 
> > This is the same thing that's done for their atomic_t equivalents.
> > 
> > Don't annotate refcount_dec_and_mutex_lock(), because mutexes don't
> > currently have sparse annotations.
> 
> I so f'ing hate that __cond_lock() crap. Previously I've suggested
> fixing sparse instead of making such an atrocious trainwreck of the
> code.

What is your suggestion exactly?  There has to be an annotation for this,
because by design sparse only analyzes individual translation units; it's not a
full-blown static analyzer that operates on the AST for the whole kernel.

- Eric

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-28 11:49 ` Peter Zijlstra
  2019-12-28 20:15   ` Eric Biggers
@ 2019-12-30 18:43   ` Kees Cook
  2019-12-30 19:15     ` Eric Biggers
  1 sibling, 1 reply; 14+ messages in thread
From: Kees Cook @ 2019-12-30 18:43 UTC (permalink / raw)
  To: Peter Zijlstra
  Cc: Eric Biggers, linux-kernel, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior

On Sat, Dec 28, 2019 at 12:49:18PM +0100, Peter Zijlstra wrote:
> On Thu, Dec 26, 2019 at 09:29:22AM -0600, Eric Biggers wrote:
> > From: Eric Biggers <ebiggers@google.com>
> > 
> > Wrap refcount_dec_and_lock() and refcount_dec_and_lock_irqsave() with
> > macros using __cond_lock() so that 'sparse' doesn't report warnings
> > about unbalanced locking when using them.
> > 
> > This is the same thing that's done for their atomic_t equivalents.
> > 
> > Don't annotate refcount_dec_and_mutex_lock(), because mutexes don't
> > currently have sparse annotations.
> 
> I so f'ing hate that __cond_lock() crap. Previously I've suggested
> fixing sparse instead of making such an atrocious trainwreck of the
> code.

Ew, I never noticed these before. That is pretty ugly. Can't __acquire()
be used directly in the functions instead of building the nasty
wrappers?

-- 
Kees Cook

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-30 18:43   ` Kees Cook
@ 2019-12-30 19:15     ` Eric Biggers
  2019-12-30 19:32       ` Kees Cook
  0 siblings, 1 reply; 14+ messages in thread
From: Eric Biggers @ 2019-12-30 19:15 UTC (permalink / raw)
  To: Kees Cook
  Cc: Peter Zijlstra, linux-kernel, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior

On Mon, Dec 30, 2019 at 10:43:20AM -0800, Kees Cook wrote:
> On Sat, Dec 28, 2019 at 12:49:18PM +0100, Peter Zijlstra wrote:
> > On Thu, Dec 26, 2019 at 09:29:22AM -0600, Eric Biggers wrote:
> > > From: Eric Biggers <ebiggers@google.com>
> > > 
> > > Wrap refcount_dec_and_lock() and refcount_dec_and_lock_irqsave() with
> > > macros using __cond_lock() so that 'sparse' doesn't report warnings
> > > about unbalanced locking when using them.
> > > 
> > > This is the same thing that's done for their atomic_t equivalents.
> > > 
> > > Don't annotate refcount_dec_and_mutex_lock(), because mutexes don't
> > > currently have sparse annotations.
> > 
> > I so f'ing hate that __cond_lock() crap. Previously I've suggested
> > fixing sparse instead of making such an atrocious trainwreck of the
> > code.
> 
> Ew, I never noticed these before. That is pretty ugly. Can't __acquire()
> be used directly in the functions instead of building the nasty
> wrappers?

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".

- Eric

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-30 19:15     ` Eric Biggers
@ 2019-12-30 19:32       ` Kees Cook
  2019-12-30 23:38         ` Luc Van Oostenryck
  2020-01-06 15:26         ` Peter Zijlstra
  0 siblings, 2 replies; 14+ messages in thread
From: Kees Cook @ 2019-12-30 19:32 UTC (permalink / raw)
  To: Eric Biggers
  Cc: Peter Zijlstra, linux-kernel, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior

On Mon, Dec 30, 2019 at 01:15:47PM -0600, Eric Biggers wrote:
> On Mon, Dec 30, 2019 at 10:43:20AM -0800, Kees Cook wrote:
> > On Sat, Dec 28, 2019 at 12:49:18PM +0100, Peter Zijlstra wrote:
> > > On Thu, Dec 26, 2019 at 09:29:22AM -0600, Eric Biggers wrote:
> > > > From: Eric Biggers <ebiggers@google.com>
> > > > 
> > > > Wrap refcount_dec_and_lock() and refcount_dec_and_lock_irqsave() with
> > > > macros using __cond_lock() so that 'sparse' doesn't report warnings
> > > > about unbalanced locking when using them.
> > > > 
> > > > This is the same thing that's done for their atomic_t equivalents.
> > > > 
> > > > Don't annotate refcount_dec_and_mutex_lock(), because mutexes don't
> > > > currently have sparse annotations.
> > > 
> > > I so f'ing hate that __cond_lock() crap. Previously I've suggested
> > > fixing sparse instead of making such an atrocious trainwreck of the
> > > code.
> > 
> > Ew, I never noticed these before. That is pretty ugly. Can't __acquire()
> > be used directly in the functions instead of building the nasty
> > wrappers?
> 
> 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.

-- 
Kees Cook

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-30 19:32       ` Kees Cook
@ 2019-12-30 23:38         ` Luc Van Oostenryck
  2020-01-03  1:35           ` Linus Torvalds
                             ` (2 more replies)
  2020-01-06 15:26         ` Peter Zijlstra
  1 sibling, 3 replies; 14+ messages in thread
From: Luc Van Oostenryck @ 2019-12-30 23:38 UTC (permalink / raw)
  To: Kees Cook
  Cc: Eric Biggers, Peter Zijlstra, linux-kernel, Ingo Molnar,
	Will Deacon, Elena Reshetova, Thomas Gleixner,
	Anna-Maria Gleixner, Sebastian Andrzej Siewior, linux-sparse

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

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-30 23:38         ` Luc Van Oostenryck
@ 2020-01-03  1:35           ` Linus Torvalds
  2020-01-03  2:18             ` Luc Van Oostenryck
  2020-01-03 12:55           ` Dan Carpenter
  2020-01-06 15:41           ` Peter Zijlstra
  2 siblings, 1 reply; 14+ messages in thread
From: Linus Torvalds @ 2020-01-03  1:35 UTC (permalink / raw)
  To: Luc Van Oostenryck
  Cc: Kees Cook, Eric Biggers, Peter Zijlstra,
	Linux Kernel Mailing List, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior, Sparse Mailing-list

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

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2020-01-03  1:35           ` Linus Torvalds
@ 2020-01-03  2:18             ` Luc Van Oostenryck
  0 siblings, 0 replies; 14+ messages in thread
From: Luc Van Oostenryck @ 2020-01-03  2:18 UTC (permalink / raw)
  To: Linus Torvalds
  Cc: Kees Cook, Eric Biggers, Peter Zijlstra,
	Linux Kernel Mailing List, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior, Sparse Mailing-list

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

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-30 23:38         ` Luc Van Oostenryck
  2020-01-03  1:35           ` Linus Torvalds
@ 2020-01-03 12:55           ` Dan Carpenter
  2020-01-06 15:41           ` Peter Zijlstra
  2 siblings, 0 replies; 14+ messages in thread
From: Dan Carpenter @ 2020-01-03 12:55 UTC (permalink / raw)
  To: Luc Van Oostenryck
  Cc: Kees Cook, Eric Biggers, Peter Zijlstra, linux-kernel,
	Ingo Molnar, Will Deacon, Elena Reshetova, Thomas Gleixner,
	Anna-Maria Gleixner, Sebastian Andrzej Siewior, linux-sparse

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


^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-30 19:32       ` Kees Cook
  2019-12-30 23:38         ` Luc Van Oostenryck
@ 2020-01-06 15:26         ` Peter Zijlstra
  1 sibling, 0 replies; 14+ messages in thread
From: Peter Zijlstra @ 2020-01-06 15:26 UTC (permalink / raw)
  To: Kees Cook
  Cc: Eric Biggers, linux-kernel, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior, Luc Van Oostenryck, linux-sparse

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.

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2019-12-30 23:38         ` Luc Van Oostenryck
  2020-01-03  1:35           ` Linus Torvalds
  2020-01-03 12:55           ` Dan Carpenter
@ 2020-01-06 15:41           ` Peter Zijlstra
  2020-01-06 17:54             ` Luc Van Oostenryck
  2 siblings, 1 reply; 14+ messages in thread
From: Peter Zijlstra @ 2020-01-06 15:41 UTC (permalink / raw)
  To: Luc Van Oostenryck
  Cc: Kees Cook, Eric Biggers, linux-kernel, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior, linux-sparse

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.

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2020-01-06 15:41           ` Peter Zijlstra
@ 2020-01-06 17:54             ` Luc Van Oostenryck
  2020-01-07  9:29               ` Peter Zijlstra
  0 siblings, 1 reply; 14+ messages in thread
From: Luc Van Oostenryck @ 2020-01-06 17:54 UTC (permalink / raw)
  To: Peter Zijlstra
  Cc: Kees Cook, Eric Biggers, linux-kernel, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior, linux-sparse

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

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions
  2020-01-06 17:54             ` Luc Van Oostenryck
@ 2020-01-07  9:29               ` Peter Zijlstra
  0 siblings, 0 replies; 14+ messages in thread
From: Peter Zijlstra @ 2020-01-07  9:29 UTC (permalink / raw)
  To: Luc Van Oostenryck
  Cc: Kees Cook, Eric Biggers, linux-kernel, Ingo Molnar, Will Deacon,
	Elena Reshetova, Thomas Gleixner, Anna-Maria Gleixner,
	Sebastian Andrzej Siewior, linux-sparse

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!

^ permalink raw reply	[flat|nested] 14+ messages in thread

end of thread, other threads:[~2020-01-07  9:29 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-12-26 15:29 [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions Eric Biggers
2019-12-28 11:49 ` Peter Zijlstra
2019-12-28 20:15   ` Eric Biggers
2019-12-30 18:43   ` Kees Cook
2019-12-30 19:15     ` Eric Biggers
2019-12-30 19:32       ` Kees Cook
2019-12-30 23:38         ` Luc Van Oostenryck
2020-01-03  1:35           ` Linus Torvalds
2020-01-03  2:18             ` Luc Van Oostenryck
2020-01-03 12:55           ` Dan Carpenter
2020-01-06 15:41           ` Peter Zijlstra
2020-01-06 17:54             ` Luc Van Oostenryck
2020-01-07  9:29               ` Peter Zijlstra
2020-01-06 15:26         ` Peter Zijlstra

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).