On Sat, Nov 07, 2020 at 02:20:03PM -0800, Linus Torvalds wrote:
> On Sat, Nov 7, 2020 at 1:23 PM Luc Van Oostenryck
> <luc.vanoostenryck@xxxxxxxxx> wrote:
> >
> > Yes, but the branch simplifications depend on the simplifications
> > that can be made on the condition. For the moment there is a focus
> > on select because it often happens when the condition is simple but
> > for these context imbalance the general case is something like:
> > stuff
> > if (arbitrary condition)
> > take lock
> > do other stuff
> > if (same arbitrary condition)
> > release lock
> >
> > and the problem is (at least) twofold (but partially related):
> > 1) recognize that the second condition is the same as the first one
> > 2) avoid that partial optimizations of the first condition 'leak'
> > into the common part because this often inhibits doing 1)
> > [Sorry, if this is not very clear. I need to find some small
> > examples to illustrate this].
> >
> > When the condition is very simple, it is converted into a select
> > but very often it's more complex, involves a memory access and/or
> > some function calls or some asm.
>
> Note that if the condition is complex and involves memory etc, it's
> generally actually a bug in the kernel.
>
> Because if it could possibly change between the lock taking and
> releasing, you are now broken.
>
> So I wouldn't want to accept code like that _anyway_. Any complex
> conditional needs to be written as
>
> lock = complex_conditional;
> if (lock)
> take lock
> do other stuff
> if (lock)
> release lock
>
> and if sparse handles _that_ case well, then all is ok.
>
> If sparse complains about the fragile "repeat complex conditional that
> couldn't be simplified to show that it was obviously identical", then
> that's actually a _good_ thing.
>
> Because we want to complain about stuff where it's not obviously clear
> that the conditional is 100% the same.
>
> Now, even in the above, if we'd want sparse to say that is ok, then
> we'd actually need to make the context tracking itself able to deal
> with "conditional on this pseudo", which it doesn't do right now.
>
> So right now it requires that much simpler case where you actually end
> up not ever having that shared case in the middle at all, and the
> simplification really ends up showing that the real path is really
>
> error = complex_conditional;
> if (error)
> return error;
> take lock
> do other stuff
> release lock
>
> which apparently sparse now - with your simplification - can see that
> the code actually ends up doing .
>
> Which is even better.
>
> I'd much rather have the lock context tracking show that locking is
> simple, and that we don't have any code that sometimes is called
> locked, and sometimes is not.
>
> Because even if you can prove - with some kind of conditional context
> tracking - that the context at least _nests_ correctly (ie you always
> properly unlock something you locked), that isn't actually the big
> problem. The big problem really is "why did that 'do-other-stuff'
> sometimes run without locking, and sometimes with locking?"
But isn't a lot of code written to explicitly support this, with an
argument or some other condition selecting between the locked mode
or the unlocked mode?
> So the lock context tracking is fairly inflexible on purpose. It's
> _meant_ to not just do "unlock matches a lock" matching. It's meant to
> also track "ok, there is no odd 'sometimes locked, sometimes not'
> code".
I agree with all this but I think the situation is not so clear cut.
I've made a few examples, oversimplified, totally made-up but
representative of the situations with the context tracking.
void take_lock(void) __attribute__((context(x, 0, 1)));
void drop_lock(void) __attribute__((context(x, 1, 0)));
void minor(void);
void major(void);
int complex_cond(void);
This one is fine for Sparse
static inline int cond_lock1(void)
{
if (complex_cond()) {
take_lock();
minor();
return 1;
}
return 0;
}
static void ok1(void)
{
int cond = cond_lock1();
if (cond) {
major();
drop_lock();
}
}
It produces the following:
ok1:
call.32 %r1 <- complex_cond
cbr %r1, .L1, .L5
.L1:
call take_lock
context 1
call minor
# call %r3 <- cond_lock1
call major
call drop_lock
context -1
br .L5
.L5:
ret
Good.
The next one corresponds to the situation Song Liu reported
static inline int cond_lock2(void)
{
if (!complex_cond())
return -1;
take_lock();
minor();
return 0;
}
static int okish(void)
{
int cond = cond_lock2();
if (cond)
return 0;
major();
drop_lock();
return 1;
}
Sparse currently produces the following:
okish:
call.32 %r6 <- complex_cond
select.32 %r8 <- %r6, $0, $0xffffffff
cbr %r6, .L8, .L9
.L8:
call take_lock
context 1
call minor
br .L9
.L9:
# call %r8 <- cond_lock2
seteq.32 %r11 <- %r8, $0
cbr %r6, .L11, .L12
.L11:
call major
call drop_lock
context -1
br .L12
.L12:
ret.32 %r11
Sparse complains about a context imbalance because of L8/L9.
The seteq is not merged with the select but something can be done
about it or on the conditional branch that depends on it.
I'll look at it right away.
[But from what I remember when I analyzed some of these, it's in
similar situations that things are messy, when cond_lock() is
slightly more complex and partial simplifications begins to mix
things from the surrounding blocks].
The one that really annoys me is this one. It's very simple and, as
far as I know, quite common in the kernel but kinda hopeless.
static void ko(int cond)
{
if (cond)
take_lock();
major();
if (cond)
drop_lock();
}
It produces the following:
ko:
cbr %arg1, .L14, .L15
.L14:
call take_lock
context 1
br .L15
.L15:
call major
cbr %arg1, .L16, .L17
.L16:
call drop_lock
context -1
br .L17
.L17:
ret
There is no select, no seteq/setne, no complex condition, nothing.
It's an idealization but I think that a lot of code involving
conditional locks boils down to this and as I said is quite common.
What do we want to do about this? I don't think there is nothing that
can be done except warning or duplicating .L15, making it as if the
code would have been written as:
static void ko(int cond)
{
if (cond) {
take_lock();
major();
drop_lock();
} else {
major();
}
}
It's doable of course but ... well, I don't think we want to do this.
-- Luc
