* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions [not found] ` <201912301131.2C7C51E8C6@keescook> @ 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; 8+ 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] 8+ messages in thread
* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions 2019-12-30 23:38 ` [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions 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; 8+ 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] 8+ 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; 8+ 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] 8+ messages in thread
* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions 2019-12-30 23:38 ` [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions 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; 8+ 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] 8+ messages in thread
* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions 2019-12-30 23:38 ` [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions 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; 8+ 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] 8+ 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; 8+ 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] 8+ 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; 8+ 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] 8+ messages in thread
* Re: [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions [not found] ` <201912301131.2C7C51E8C6@keescook> 2019-12-30 23:38 ` [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions Luc Van Oostenryck @ 2020-01-06 15:26 ` Peter Zijlstra 1 sibling, 0 replies; 8+ 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] 8+ messages in thread
end of thread, other threads:[~2020-01-07 9:29 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <20191226152922.2034-1-ebiggers@kernel.org>
[not found] ` <20191228114918.GU2827@hirez.programming.kicks-ass.net>
[not found] ` <201912301042.FB806E1133@keescook>
[not found] ` <20191230191547.GA1501@zzz.localdomain>
[not found] ` <201912301131.2C7C51E8C6@keescook>
2019-12-30 23:38 ` [PATCH] locking/refcount: add sparse annotations to dec-and-lock functions 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).