locking/refcount: add sparse annotations to dec-and-lock functions
Subsystems (3)
PATCH 1/1 locking/refcount: add sparse annotations to dec-and-lock functions
From: Eric Biggers <[email protected]>
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.
--- include/linux/refcount.h | 45 ++++++++++++++++++++++++++++++++++++---- lib/refcount.c | 39 +++++----------------------------- 2 files changed, 46 insertions(+), 38 deletions(-)
include/linux/refcount.h +41 -4
@@ -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 */
lib/refcount.c +5 -34
@@ -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);
Signature · 1 line
2.24.1
Peter Zijlstra
maintainerQuoted 10 lines · Eric Biggers
From: Eric Biggers <[email protected]>
Wrap
refcount_dec_and_lock()andrefcount_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_tequivalents.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.
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Eric Biggers
From: Eric Biggers <[email protected]>
Wrap
refcount_dec_and_lock()andrefcount_dec_and_lock_irqsave()with macros using__cond_lock()so that 'sparse' doesn't report warnings about unbalanced locking when using them.
Quoted 8 lines
Quoted 4 lines
This is the same thing that's done for their
atomic_tequivalents.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
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Eric Biggers
From: Eric Biggers <[email protected]>
Wrap
refcount_dec_and_lock()andrefcount_dec_and_lock_irqsave()with macros using__cond_lock()so that 'sparse' doesn't report warnings about unbalanced locking when using them.
Quoted 8 lines
Quoted 4 lines
This is the same thing that's done for their
atomic_tequivalents.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?
Signature · 1 line
Kees Cook
Quoted 13 lines · Kees Cook
Quoted 12 lines · Peter Zijlstra
Quoted 10 lines · Eric Biggers
From: Eric Biggers <[email protected]>
Wrap
refcount_dec_and_lock()andrefcount_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_tequivalents.Don't annotate
refcount_dec_and_mutex_lock(), because mutexes don't currently have sparse annotations.
Quoted 7 lines
Quoted 3 lines
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
Quoted 22 lines · Eric Biggers
Quoted 13 lines · Kees Cook
Quoted 12 lines · Peter Zijlstra
Quoted 10 lines · Eric Biggers
From: Eric Biggers <[email protected]>
Wrap
refcount_dec_and_lock()andrefcount_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_tequivalents.Don't annotate
refcount_dec_and_mutex_lock(), because mutexes don't currently have sparse annotations.Quoted 7 lines
Quoted 3 lines
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?
Quoted 7 lines
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.
Signature · 1 line
Kees Cook
Quoted 10 lines · Kees Cook
Quoted 8 lines · Eric Biggers
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".
Quoted 5 lines
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
Quoted 11 lines · Luc Van Oostenryck
One of the simplest situation with these conditional locks is:
if (test) lock(); do_stuff(); if (test) unlock();
Quoted 4 lines
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 UNDEFbecasue 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
Quoted 23 lines · Linus Torvalds
Quoted 11 lines · Luc Van Oostenryck
One of the simplest situation with these conditional locks is:
if (test) lock(); do_stuff(); if (test) unlock();Quoted 4 lines
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.
Quoted 6 lines
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.
Quoted 55 lines
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 blockbecause "
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 UNDEFbecasue 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".
Quoted 4 lines
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
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
Peter Zijlstra
maintainerQuoted 1 line · Kees Cook
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
Quoted 3 lines
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.
Peter Zijlstra
maintainerQuoted 28 lines · Luc Van Oostenryck
Quoted 10 lines · Kees Cook
Quoted 8 lines · Eric Biggers
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".
Quoted 5 lines
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();
Quoted 4 lines
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.
Quoted 1 line · Peter Zijlstra
On Tue, Dec 31, 2019 at 12:38:14AM +0100, Luc Van Oostenryck wrote:
...
Quoted 21 lines
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 voidspin_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) #definespin_trylock(lock)__cond_lock(lock, _spin_lock)if (spin_trylock(lock)) { /* do crap */ spin_unlock(); }
Quoted 7 lines
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.
Quoted 3 lines
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
Peter Zijlstra
maintainerQuoted 7 lines · Luc Van Oostenryck
Quoted 1 line · Peter Zijlstra
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..
Quoted 30 lines
Quoted 3 lines
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()orreleases()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(); }
Quoted 1 line
Would something like this be satisfactory?
Very much so, Thanks!