"warning: context imbalance" in kernel/bpf/hashtab.c

"warning: context imbalance" in kernel/bpf/hashtab.c

[Song Liu]

[-- Attachment #1: Type: text/plain, Size: 3384 bytes --]

Hi, 

We are trying to fix some sparse warning in kernel/bpf/hashtab.c (in bpf-next tree). 
The sparse I use was v0.6.3-76-gf680124b. 

These new warnings are introduced by [1]. Before [1], hashtab.c got

[...]
kernel/bpf/hashtab.c:2089:19: error: subtraction of functions? Share your drugs
kernel/bpf/hashtab.c:1421:9: warning: context imbalance in '__htab_map_lookup_and_delete_batch' - different lock contexts for basic block
kernel/bpf/hashtab.c: note: in included file (through include/linux/workqueue.h, include/linux/bpf.h):
./include/linux/rcupdate.h:693:9: warning: context imbalance in 'bpf_hash_map_seq_find_next' - unexpected unlock
./include/linux/rcupdate.h:693:9: warning: context imbalance in 'bpf_hash_map_seq_stop' - unexpected unlock

With [1], we got a few more warnings:

[...]
kernel/bpf/hashtab.c:2141:19: error: subtraction of functions? Share your drugs
kernel/bpf/hashtab.c:1292:27: warning: context imbalance in 'htab_map_delete_elem' - unexpected unlock
kernel/bpf/hashtab.c:1325:27: warning: context imbalance in 'htab_lru_map_delete_elem' - unexpected unlock
kernel/bpf/hashtab.c: note: in included file (through include/linux/workqueue.h, include/linux/bpf.h):
./include/linux/rcupdate.h:693:9: warning: context imbalance in '__htab_map_lookup_and_delete_batch' - unexpected unlock
./include/linux/rcupdate.h:693:9: warning: context imbalance in 'bpf_hash_map_seq_find_next' - unexpected unlock
./include/linux/rcupdate.h:693:9: warning: context imbalance in 'bpf_hash_map_seq_stop' - unexpected unlock

So htab_map_delete_elem() and htab_lru_map_delete_elem() got new warnings, and 
__htab_map_lookup_and_delete_batch() got a slightly different warning. 

After trying different annotations, including the attached foo.diff by Daniel,
we found the simplest fix was something like:

====================== 8< ========================== 
diff --git i/kernel/bpf/hashtab.c w/kernel/bpf/hashtab.c
index 23f73d4649c9c..faad2061f1167 100644
--- i/kernel/bpf/hashtab.c
+++ w/kernel/bpf/hashtab.c
@@ -1279,6 +1279,7 @@ static int htab_map_delete_elem(struct bpf_map *map, void *key)
        ret = htab_lock_bucket(htab, b, hash, &flags);
        if (ret)
                return ret;
+       ret = 0;

        l = lookup_elem_raw(head, hash, key, key_size);

@@ -1314,6 +1315,7 @@ static int htab_lru_map_delete_elem(struct bpf_map *map, void *key)
        ret = htab_lock_bucket(htab, b, hash, &flags);
        if (ret)
                return ret;
+       ret = 0;

        l = lookup_elem_raw(head, hash, key, key_size);

@@ -1476,6 +1478,7 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
                ret = htab_lock_bucket(htab, b, batch, &flags);
                if (ret)
                        goto next_batch;
+               ret = 0;
        }

        bucket_cnt = 0;

====================== 8< ========================== 

These three "ret = 0;" make the sparse warning back to before [1]. However, these
don't really make sense, as we know ret must be zero after the if clause. So it
looks like a bug in sparse. Please help us look into this issue. 

Also, there are a few similar warnings from hashtab.c. Please give us guidance on 
how to fix them properly. 

Thanks in advance,
Song

[1] commit 20b6cc34ea74 ("bpf: Avoid hashtab deadlock with map_locked")


[-- Attachment #2: foo.diff --]
[-- Type: application/octet-stream, Size: 3884 bytes --]

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 23f73d4649c9..1ed2547863fc 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -158,11 +158,15 @@ static void htab_init_buckets(struct bpf_htab *htab)
 static inline int htab_lock_bucket(const struct bpf_htab *htab,
 				   struct bucket *b, u32 hash,
 				   unsigned long *pflags)
+	__acquires(&b->raw_lock) __acquires(&b->lock)
 {
 	unsigned long flags;
 
 	hash = hash & HASHTAB_MAP_LOCK_MASK;
 
+	__acquire(&b->raw_lock);
+	__acquire(&b->lock);
+
 	migrate_disable();
 	if (unlikely(__this_cpu_inc_return(*(htab->map_locked[hash])) != 1)) {
 		__this_cpu_dec(*(htab->map_locked[hash]));
@@ -182,8 +186,13 @@ static inline int htab_lock_bucket(const struct bpf_htab *htab,
 static inline void htab_unlock_bucket(const struct bpf_htab *htab,
 				      struct bucket *b, u32 hash,
 				      unsigned long flags)
+	__releases(&b->raw_lock) __releases(&b->lock)
 {
 	hash = hash & HASHTAB_MAP_LOCK_MASK;
+
+	__release(&b->raw_lock);
+	__release(&b->lock);
+
 	if (htab_use_raw_lock(htab))
 		raw_spin_unlock_irqrestore(&b->raw_lock, flags);
 	else
@@ -731,8 +740,11 @@ static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node)
 	head = &b->head;
 
 	ret = htab_lock_bucket(htab, b, tgt_l->hash, &flags);
-	if (ret)
+	if (ret) {
+		__release(&b->raw_lock);
+		__release(&b->lock);
 		return false;
+	}
 
 	hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
 		if (l == tgt_l) {
@@ -1013,8 +1025,11 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
 	}
 
 	ret = htab_lock_bucket(htab, b, hash, &flags);
-	if (ret)
+	if (ret) {
+		__release(&b->raw_lock);
+		__release(&b->lock);
 		return ret;
+	}
 
 	l_old = lookup_elem_raw(head, hash, key, key_size);
 
@@ -1094,8 +1109,11 @@ static int htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value,
 	memcpy(l_new->key + round_up(map->key_size, 8), value, map->value_size);
 
 	ret = htab_lock_bucket(htab, b, hash, &flags);
-	if (ret)
+	if (ret) {
+		__release(&b->raw_lock);
+		__release(&b->lock);
 		return ret;
+	}
 
 	l_old = lookup_elem_raw(head, hash, key, key_size);
 
@@ -1150,8 +1168,11 @@ static int __htab_percpu_map_update_elem(struct bpf_map *map, void *key,
 	head = &b->head;
 
 	ret = htab_lock_bucket(htab, b, hash, &flags);
-	if (ret)
+	if (ret) {
+		__release(&b->raw_lock);
+		__release(&b->lock);
 		return ret;
+	}
 
 	l_old = lookup_elem_raw(head, hash, key, key_size);
 
@@ -1215,8 +1236,11 @@ static int __htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key,
 	}
 
 	ret = htab_lock_bucket(htab, b, hash, &flags);
-	if (ret)
+	if (ret) {
+		__release(&b->raw_lock);
+		__release(&b->lock);
 		return ret;
+	}
 
 	l_old = lookup_elem_raw(head, hash, key, key_size);
 
@@ -1277,8 +1301,11 @@ static int htab_map_delete_elem(struct bpf_map *map, void *key)
 	head = &b->head;
 
 	ret = htab_lock_bucket(htab, b, hash, &flags);
-	if (ret)
+	if (ret) {
+		__release(&b->raw_lock);
+		__release(&b->lock);
 		return ret;
+	}
 
 	l = lookup_elem_raw(head, hash, key, key_size);
 
@@ -1312,8 +1339,11 @@ static int htab_lru_map_delete_elem(struct bpf_map *map, void *key)
 	head = &b->head;
 
 	ret = htab_lock_bucket(htab, b, hash, &flags);
-	if (ret)
+	if (ret) {
+		__release(&b->raw_lock);
+		__release(&b->lock);
 		return ret;
+	}
 
 	l = lookup_elem_raw(head, hash, key, key_size);
 
@@ -1474,8 +1504,11 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
 	/* do not grab the lock unless need it (bucket_cnt > 0). */
 	if (locked) {
 		ret = htab_lock_bucket(htab, b, batch, &flags);
-		if (ret)
+		if (ret) {
+			__release(&b->raw_lock);
+			__release(&b->lock);
 			goto next_batch;
+		}
 	}
 
 	bucket_cnt = 0;

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Luc Van Oostenryck]

On Thu, Nov 05, 2020 at 07:34:55PM +0000, Song Liu wrote:
> Hi, 
> 
> We are trying to fix some sparse warning in kernel/bpf/hashtab.c (in bpf-next tree). 
> The sparse I use was v0.6.3-76-gf680124b. 
> 
> These new warnings are introduced by [1]. Before [1], hashtab.c got
> 
> [...]
> kernel/bpf/hashtab.c:2089:19: error: subtraction of functions? Share your drugs
> kernel/bpf/hashtab.c:1421:9: warning: context imbalance in '__htab_map_lookup_and_delete_batch' - different lock contexts for basic block
> kernel/bpf/hashtab.c: note: in included file (through include/linux/workqueue.h, include/linux/bpf.h):
> ./include/linux/rcupdate.h:693:9: warning: context imbalance in 'bpf_hash_map_seq_find_next' - unexpected unlock
> ./include/linux/rcupdate.h:693:9: warning: context imbalance in 'bpf_hash_map_seq_stop' - unexpected unlock
> 
> With [1], we got a few more warnings:
> 
> [...]
> kernel/bpf/hashtab.c:2141:19: error: subtraction of functions? Share your drugs
> kernel/bpf/hashtab.c:1292:27: warning: context imbalance in 'htab_map_delete_elem' - unexpected unlock
> kernel/bpf/hashtab.c:1325:27: warning: context imbalance in 'htab_lru_map_delete_elem' - unexpected unlock
> kernel/bpf/hashtab.c: note: in included file (through include/linux/workqueue.h, include/linux/bpf.h):
> ./include/linux/rcupdate.h:693:9: warning: context imbalance in '__htab_map_lookup_and_delete_batch' - unexpected unlock
> ./include/linux/rcupdate.h:693:9: warning: context imbalance in 'bpf_hash_map_seq_find_next' - unexpected unlock
> ./include/linux/rcupdate.h:693:9: warning: context imbalance in 'bpf_hash_map_seq_stop' - unexpected unlock
> 
> So htab_map_delete_elem() and htab_lru_map_delete_elem() got new warnings, and 
> __htab_map_lookup_and_delete_batch() got a slightly different warning. 
> 
> After trying different annotations, including the attached foo.diff by Daniel,
> we found the simplest fix was something like:

Annotations can't fix anything here. The patch [1] changes htab_lock_bucket(),
into conditionally taking a lock while before it took it unconditionally.
So, each point where its value is tested now becomes the confluence of 2
distinct paths: one with the lock taken and one with the lock not taken.
This is what is meant by 'context imbalance'.

It should be noted that this 'context imbalance' doesn't mean things like
'this section of code can be executed without the lock held'. 

In the present case, if Sparse would be smarter (move around condition testing)
it would be able to see something like 'OK, there is an imbalance but this has
no impact on the lock being held when needed'. But, in the general case, it's
impossible to do and so Sparse doesn't even try.

-- Luc Van Oostenryck

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Linus Torvalds]

On Thu, Nov 5, 2020 at 1:13 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Annotations can't fix anything here. The patch [1] changes htab_lock_bucket(),
> into conditionally taking a lock while before it took it unconditionally.
> So, each point where its value is tested now becomes the confluence of 2
> distinct paths: one with the lock taken and one with the lock not taken.
> This is what is meant by 'context imbalance'.

I think the point Song makes is that if sparse did a few more
optimizations, it would see the context imbalance go away, because the
value it tests would become constant.

                 Linus

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Luc Van Oostenryck]

On Thu, Nov 05, 2020 at 01:18:02PM -0800, Linus Torvalds wrote:
> On Thu, Nov 5, 2020 at 1:13 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > Annotations can't fix anything here. The patch [1] changes htab_lock_bucket(),
> > into conditionally taking a lock while before it took it unconditionally.
> > So, each point where its value is tested now becomes the confluence of 2
> > distinct paths: one with the lock taken and one with the lock not taken.
> > This is what is meant by 'context imbalance'.
> 
> I think the point Song makes is that if sparse did a few more
> optimizations, it would see the context imbalance go away, because the
> value it tests would become constant.

It's not how I understood it, but yes, I agree. It's what I tried to
briefly explain the in the last paragraph.

From what I know from these situations, in most cases, simple
'expression' optimizations are not enough but simple forms of
code hoisting would often anything that's needed.

-- Luc

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Song Liu]

> On Nov 5, 2020, at 1:50 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote:
> 
> On Thu, Nov 05, 2020 at 01:18:02PM -0800, Linus Torvalds wrote:
>> On Thu, Nov 5, 2020 at 1:13 PM Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>> 
>>> Annotations can't fix anything here. The patch [1] changes htab_lock_bucket(),
>>> into conditionally taking a lock while before it took it unconditionally.
>>> So, each point where its value is tested now becomes the confluence of 2
>>> distinct paths: one with the lock taken and one with the lock not taken.
>>> This is what is meant by 'context imbalance'.
>> 
>> I think the point Song makes is that if sparse did a few more
>> optimizations, it would see the context imbalance go away, because the
>> value it tests would become constant.
> 
> It's not how I understood it, but yes, I agree. It's what I tried to
> briefly explain the in the last paragraph.
> 
> From what I know from these situations, in most cases, simple
> 'expression' optimizations are not enough but simple forms of
> code hoisting would often anything that's needed.


Hi Luc and Linus, 

Thanks for your comments!

I know very little about sparse internal. But I feel this is more
like a minor bug. 

Here is the simplified inlined code of htab_map_delete_elem()

	if (some_condition) {
		ret = -EBUSY;
	} else {
		spin_lock();
		ret = 0;
	}

	if (ret)
		return ret;
+	ret = 0;

	[...]

	if (some_other_condition)
		ret = -ENOENT;
	spin_unlock();
	return ret;

When we reach the point of "+ ret = 0;", we will do spin_unlock()
regardless of the value of ret. So whether we know ret is definitely 
equal to zero should not matter at all? 

It feels like sparse knows there are two paths before "if (ret)": 
   1) ret == 0, we did spin_lock()
   2) ret == -EBUSY, we didn't do spin_lock()

Then, after the "if (ret)", even without explicit "ret = 0;", it is 
possible to prune path 2), but I guess sparse is not doing it, which 
is unfortunate but not a bug. However, it seems explicit "ret = 0;" 
helps sparse prune path 2), which doesn't seem right. Explicit "ret = 0"
should only overwrite the value of ret, but not prune any path. 

Does this make sense?

Thanks,
Song

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Linus Torvalds]

On Fri, Nov 6, 2020 at 9:30 AM Song Liu <songliubraving@fb.com> wrote:
>
> I know very little about sparse internal. But I feel this is more
> like a minor bug.

It's not really a bug, and the pattern you show isn't actually all
that easy to see for a compiler.

> Here is the simplified inlined code of htab_map_delete_elem()
>
>         if (some_condition) {
>                 ret = -EBUSY;
>         } else {
>                 spin_lock();
>                 ret = 0;
>         }

So here the issue for the sparse optimizer is that while both "ret"
and "spin_lock" is tied to "some_condition", it's not really obvious.

A compiler would have to follow all the value analysis - and good
compilers do that, but sparse is not a "great" compiler, it's more of
a "solid and not horribly stupid" one.

>         if (ret)
>                 return ret;

So I'd really suggest you make the code more obvious - it will be more
obvious to humans too.

Write it as

        if (some_condition)
                return -EBUSY;
        spin_lock();

instead, and now sparse will see that obviously spin_lock() and
"some_condition" are mutually incompatible.

               Linus

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Song Liu]

> On Nov 6, 2020, at 9:45 AM, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> 
> On Fri, Nov 6, 2020 at 9:30 AM Song Liu <songliubraving@fb.com> wrote:
>> 
>> I know very little about sparse internal. But I feel this is more
>> like a minor bug.
> 
> It's not really a bug, and the pattern you show isn't actually all
> that easy to see for a compiler.
> 
>> Here is the simplified inlined code of htab_map_delete_elem()
>> 
>>        if (some_condition) {
>>                ret = -EBUSY;
>>        } else {
>>                spin_lock();
>>                ret = 0;
>>        }
> 
> So here the issue for the sparse optimizer is that while both "ret"
> and "spin_lock" is tied to "some_condition", it's not really obvious.
> 
> A compiler would have to follow all the value analysis - and good
> compilers do that, but sparse is not a "great" compiler, it's more of
> a "solid and not horribly stupid" one.
> 
>>        if (ret)
>>                return ret;
> 
> So I'd really suggest you make the code more obvious - it will be more
> obvious to humans too.
> 
> Write it as
> 
>        if (some_condition)
>                return -EBUSY;
>        spin_lock();
> 
> instead, and now sparse will see that obviously spin_lock() and
> "some_condition" are mutually incompatible.

Thanks for your suggestion! This pattern didn't trigger the warning. 
We still need some work to apply this to actual code, because the lock
part is in an helper:

inline int htab_lock_bucket()
{
	if (some_condition) 
		return -EBUSY;	
	spin_lock();
	return 0;
}

int htab_map_delete_elem()
{
	ret = htab_lock_bucket();
	if (ret)
		return ret;
	[...]
}

We can probably split htab_lock_bucket() into two helpers, like

int htab_map_delete_elem()
{
	ret = htab_lock_is_busy();  // check some_condition
	if (ret)
		return ret;

	htab_do_lock();    // calls spin_lock()

	[...]
}

I will do more experiments with this. 

Thanks again!
Song

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Linus Torvalds]

On Fri, Nov 6, 2020 at 11:05 AM Song Liu <songliubraving@fb.com> wrote:
>
> Thanks for your suggestion! This pattern didn't trigger the warning.
> We still need some work to apply this to actual code, because the lock
> part is in an helper:
>
> inline int htab_lock_bucket()
> {
>         if (some_condition)
>                 return -EBUSY;
>         spin_lock();
>         return 0;
> }

So inlining does end up being important, because then sparse can see
the pattern in the caller.

But yes, as-is you end up with the same issue that sparse then may not
be able to see the "return value goes together with the spinlock".

That said, in the form you have it now in, it might be easier for
sparse to see that, by just adding a branch following phase.

Branch following is much simpler than value analysis, but "much
simpler" is still not the same as "entirely trivial".

Here's a test-case for this behavior for sparse, in the hope that Luc
goes "that's easy enough to do":

    extern void spin_lock(void);
    extern void spin_unlock(void);

    static inline int errno(int arg)
    {
        if (arg)
                return -1;
        spin_lock();
        return 0;
    }


    int cmp(int i)
    {
        if (errno(i))
                return -1;
        spin_unlock();
        return 0;
    }

and right now sparse linearizes this to

    cmp:
    .L0:
        <entry-point>
        select.32   %r4 <- %arg1, $0xffffffff, $0
        cbr         %arg1, .L5, .L4

    .L4:
        call        spin_lock
        br          .L5

    .L5:
        # call      %r4 <- errno, %r1
        select.32   %r6 <- %r4, $0xffffffff, $0
        cbr         %arg1, .L6, .L2

    .L2:
        call        spin_unlock
        br          .L6

    .L6:
        ret.32      %r6

because sparse isn't smart enough to do a couple of simple optimizations:

 (a) the conditional following for the return value:

        select.32   %r4 <- %arg1, $0xffffffff, $0
        select.32   %r6 <- %r4, $0xffffffff, $0

Note how it doesn't trigger CSE, because it's not the same instruction
(%arg1 vs %r4), but sparse *could* see that a select that depends on a
previous select that has constant arguments can be simplified to be
conditional on the original select value instead, so it *could* be
CSE'd into one single thing.

So the second "select" could be optimized away by realizing that it
really gets the same value as the first one. That *should* be trivial
to do in sparse by just having a simple pattern for select
simplification.

And once that optimization is in place, the second optimization would be

 (b) trivial branch following: "conditional branch to conditional
branch with the same condition".

ie we'd have the pattern of

        cbr         %arg1, .L5, .L4
        ...
    .L5:
        cbr         %arg1, .L6, .L2

and now a trivial branch following optimization would see "oh, the
first target of the first cbr is to another cbr that has the same
condition, so we can rewrite the first cbr as

        cbr         %arg1, .L6, .L4

instead.

And once you've done that trivial branch following, the .L5 target has
only that fallthrough source from .L4, and the code becomes

    cmp:
    .L0:
        <entry-point>
        select.32   %r4 <- %arg1, $0xffffffff, $0
        cbr         %arg1, .L6, .L4

    .L4:
        call        spin_lock
        cbr         %arg1, .L6, .L2

    .L2:
        call        spin_unlock
        br          .L6

    .L6:
        ret.32      %r4

which still isn't good enough, because it still has that conditional
branch that is now pointless.

Removing the second conditional branch entirely would require having a
"look, it's now dominated by a previous conditional branch on the same
condition, so it can't trigger".

That's the only remaining optimization that isn't purely local.
Dominance analysis is always painful. sparse does do it (for memory
accesses), but it's a *lot* more complex than just some local
single-instruction pattern that looks at the source or the target of
that single instruction.

Anyway - this is all doable, but it's the end of the week so my pull
requests for the kernel are starting to pile up and I already spent
more time than I should have at looking at sparse.

Maybe this gives Luc some ideas, though.

Or maybe Luc will point out that even my "simple" optimizations are
slightly more painful than I think they are for some reason that I
haven't looked at.

              Linus

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Luc Van Oostenryck]

On Fri, Nov 06, 2020 at 11:44:00AM -0800, Linus Torvalds wrote:
> On Fri, Nov 6, 2020 at 11:05 AM Song Liu <songliubraving@fb.com> wrote:
>  (a) the conditional following for the return value:
> 
>         select.32   %r4 <- %arg1, $0xffffffff, $0
>         select.32   %r6 <- %r4, $0xffffffff, $0
> 
> Note how it doesn't trigger CSE, because it's not the same instruction
> (%arg1 vs %r4), but sparse *could* see that a select that depends on a
> previous select that has constant arguments can be simplified to be
> conditional on the original select value instead, so it *could* be
> CSE'd into one single thing.
> 
> So the second "select" could be optimized away by realizing that it
> really gets the same value as the first one. That *should* be trivial
> to do in sparse by just having a simple pattern for select
> simplification.
> 
> And once that optimization is in place, the second optimization would be

I think I may even have already this in an half-polished form.
 
>  (b) trivial branch following: "conditional branch to conditional
> branch with the same condition".
> 
> ie we'd have the pattern of
> 
>         cbr         %arg1, .L5, .L4
>         ...
>     .L5:
>         cbr         %arg1, .L6, .L2
> 
> and now a trivial branch following optimization would see "oh, the
> first target of the first cbr is to another cbr that has the same
> condition, so we can rewrite the first cbr as
> 
>         cbr         %arg1, .L6, .L4
> 
> instead.

This, should already be done (by yourself, many years ago).

> And once you've done that trivial branch following, the .L5 target has
> only that fallthrough source from .L4, and the code becomes
> 
>     cmp:
>     .L0:
>         <entry-point>
>         select.32   %r4 <- %arg1, $0xffffffff, $0
>         cbr         %arg1, .L6, .L4
> 
>     .L4:
>         call        spin_lock
>         cbr         %arg1, .L6, .L2
> 
>     .L2:
>         call        spin_unlock
>         br          .L6
> 
>     .L6:
>         ret.32      %r4
> 
> which still isn't good enough, because it still has that conditional
> branch that is now pointless.
> 
> Removing the second conditional branch entirely would require having a
> "look, it's now dominated by a previous conditional branch on the same
> condition, so it can't trigger".
> 
> That's the only remaining optimization that isn't purely local.

Yes.

> Dominance analysis is always painful. sparse does do it (for memory
> accesses), but it's a *lot* more complex than just some local
> single-instruction pattern that looks at the source or the target of
> that single instruction.

This shouldn't be a big problem since we already have the dominance
tree (but it's not yet updated when there is changes n the CFG).
OTOH, the memops simplification creates invalid phi-nodes which
indirectly creates all sort of problems. I've several fixes for this
but none I'm really happy with.

> Maybe this gives Luc some ideas, though.
> 
> Or maybe Luc will point out that even my "simple" optimizations are
> slightly more painful than I think they are for some reason that I
> haven't looked at.

No no, it's certainly more than a few hours of work but it's also not
an immense task. Of course, the devil is always in the details.

There is also the option of explicitly handling conditional contexts.
I did maybe 6 months ago, in 2 or 3 different ways. It worked well,
and would probably solve the problem here but:
* it needs new annotations
* it's OK when the condition is simple ( = 0 or != 0), it could be
  adapted for some others (like, for example, >= 0) but more general
  condition would become hard to handle (the annotations needs to know
  about the condition).
* the benefits were disappointing because, in most cases I saw, it
  displaced the problem to somewhere else where a 'real' optimization
  was needed. This is why I stopped to look at it.

But so, yes, what you propose here makes a lot of sense and would be
very valuable. I'll take a look at it soon (but my stack is already so
full that I'm quite reluctant to begin anything new (I currently have
208 topic branches with 120 of them being valid, interesting seriess
waiting some polishing, validation and patch description :( ).

-- Luc

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 2149 bytes --]

On Fri, Nov 6, 2020 at 2:19 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> On Fri, Nov 06, 2020 at 11:44:00AM -0800, Linus Torvalds wrote:
> > On Fri, Nov 6, 2020 at 11:05 AM Song Liu <songliubraving@fb.com> wrote:
> >  (a) the conditional following for the return value:
> >
> >         select.32   %r4 <- %arg1, $0xffffffff, $0
> >         select.32   %r6 <- %r4, $0xffffffff, $0
> >
> > Note how it doesn't trigger CSE, because it's not the same instruction
> > (%arg1 vs %r4), but sparse *could* see that a select that depends on a
> > previous select that has constant arguments can be simplified to be
> > conditional on the original select value instead, so it *could* be
> > CSE'd into one single thing.
> >
> > So the second "select" could be optimized away by realizing that it
> > really gets the same value as the first one. That *should* be trivial
> > to do in sparse by just having a simple pattern for select
> > simplification.
> >
> > And once that optimization is in place, the second optimization would be
>
> I think I may even have already this in an half-polished form.

Ugh. I tried to see what I can do, and it does simplify, but not the
way I expected.

The attached patch looks superficially sane (but probably is broken),
and results in one less "select" statement:


    .L0:
        <entry-point>
        cbr         %arg1, .L5, .L4

    .L4:
        call        spin_lock
        br          .L5

    .L5:
        # call      %r4 <- errno, %r1
        select.32   %r6 <- %arg1, $0xffffffff, $0
        cbr         %arg1, .L6, .L2

    .L2:
        call        spin_unlock
        br          .L6

    .L6:
        ret.32      %r6

but note how it removed not the select statement I expected, so you
don't actually end up with a branch to a branch anyway.

Oh well. It's close. That "select" could be anywhere, so the branch
following could know that.

And my patch may be garbage too. I just decided to take a look at how
easy the "combine select conditional" might be.

(In fact, my patch *IS* garbage, because it should do the same for
"OP_SET_NE" as an def to the select too)

                Linus

[-- Attachment #2: patch --]
[-- Type: application/octet-stream, Size: 1046 bytes --]

 simplify.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/simplify.c b/simplify.c
index f2aaa52d..b56eb2b9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1748,6 +1748,7 @@ static int simplify_cast(struct instruction *insn)
 static int simplify_select(struct instruction *insn)
 {
 	pseudo_t cond, src1, src2;
+	struct instruction *def;
 
 	cond = insn->src1;
 	src1 = insn->src2;
@@ -1760,6 +1761,19 @@ static int simplify_select(struct instruction *insn)
 		kill_use(kill);
 		return replace_with_pseudo(insn, take);
 	}
+
+	// Is the def of the conditional another select?
+	// And if that one results in a "zero or not", use thr
+	// original conditional instead.
+	def = cond->def;
+	if (def->opcode == OP_SEL && constant(def->src2) && constant(def->src3)) {
+		if (def->src2->value && !def->src3->value) {
+			kill_use(&insn->src1);
+			use_pseudo(insn, def->src1, &insn->src1);
+			return REPEAT_CSE;
+		}
+	}
+
 	if (constant(src1) && constant(src2)) {
 		long long val1 = src1->value;
 		long long val2 = src2->value;

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Luc Van Oostenryck]

On Fri, Nov 06, 2020 at 02:46:55PM -0800, Linus Torvalds wrote:
> On Fri, Nov 6, 2020 at 2:19 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > On Fri, Nov 06, 2020 at 11:44:00AM -0800, Linus Torvalds wrote:
> > > On Fri, Nov 6, 2020 at 11:05 AM Song Liu <songliubraving@fb.com> wrote:
> > >  (a) the conditional following for the return value:
> > >
> > >         select.32   %r4 <- %arg1, $0xffffffff, $0
> > >         select.32   %r6 <- %r4, $0xffffffff, $0
> > >
> > > Note how it doesn't trigger CSE, because it's not the same instruction
> > > (%arg1 vs %r4), but sparse *could* see that a select that depends on a
> > > previous select that has constant arguments can be simplified to be
> > > conditional on the original select value instead, so it *could* be
> > > CSE'd into one single thing.
> > >
> > > So the second "select" could be optimized away by realizing that it
> > > really gets the same value as the first one. That *should* be trivial
> > > to do in sparse by just having a simple pattern for select
> > > simplification.
> > >
> > > And once that optimization is in place, the second optimization would be
> >
> > I think I may even have already this in an half-polished form.
> 
> Ugh. I tried to see what I can do, and it does simplify, but not the
> way I expected.
> 
> The attached patch looks superficially sane (but probably is broken),
> and results in one less "select" statement:
> 
> 
>     .L0:
>         <entry-point>
>         cbr         %arg1, .L5, .L4
> 
>     .L4:
>         call        spin_lock
>         br          .L5
> 
>     .L5:
>         # call      %r4 <- errno, %r1
>         select.32   %r6 <- %arg1, $0xffffffff, $0
>         cbr         %arg1, .L6, .L2
> 
>     .L2:
>         call        spin_unlock
>         br          .L6
> 
>     .L6:
>         ret.32      %r6
> 
> but note how it removed not the select statement I expected, so you
> don't actually end up with a branch to a branch anyway.
> 
> Oh well. It's close. That "select" could be anywhere, so the branch
> following could know that.

Yes, the core of the problem is to move things up.
Here is a patch that kinda do this, a bit too much even but the idea
is there. With is it gives the following:
	cmp:
	.L0:
		<entry-point>
		select.32   %r4 <- %arg1, $0xffffffff, $0
		select.32   %r6 <- %r4, $0xffffffff, $0
		cbr         %arg1, .L6, .L4
	
	.L4:
		call        spin_lock
		# call      %r4 <- errno, %r1
		call        spin_unlock
		br          .L6
	
	.L6:
		ret.32      %r6


The patch move *all* selects the highest possible using the dominance
tree. It complements the select simplification. The only part really
interesting is the very last one, the remaining is just infrastructure.

So, I think that the next questions are:
* which selects should be moved up?
* up to where should them be moved?

I'll think a bit all this this WE.

-- Luc


From 7c0d5a759756989919eb2799e7e50d36941d47b3 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sat, 7 Nov 2020 02:23:21 +0100
Subject: [PATCH] EXP: move up all selects at most as possible

---
 linearize.c | 21 +++++++++++++++++++++
 linearize.h |  1 +
 simplify.c  | 34 ++++++++++++++++++++++++++++++++++
 3 files changed, 56 insertions(+)

diff --git a/linearize.c b/linearize.c
index c1e3455adb67..005d90b3fb45 100644
--- a/linearize.c
+++ b/linearize.c
@@ -737,6 +737,27 @@ void insert_select(struct basic_block *bb, struct instruction *br, struct instru
 	add_instruction(&bb->insns, br);
 }
 
+void copy_select(struct basic_block *bb, struct instruction *insn)
+{
+	struct instruction *br;
+	pseudo_t target;
+	struct instruction *select;
+
+	/* Remove the 'br' */
+	br = delete_last_instruction(&bb->insns);
+
+	select = alloc_typed_instruction(OP_SEL, insn->type);
+	select->bb = bb;
+
+	use_pseudo(select, insn->src1, &select->src1);
+	use_pseudo(select, insn->src2, &select->src2);
+	use_pseudo(select, insn->src3, &select->src3);
+	select->target = insn->target;
+
+	add_instruction(&bb->insns, select);
+	add_instruction(&bb->insns, br);
+}
+
 static inline int bb_empty(struct basic_block *bb)
 {
 	return !bb->insns;
diff --git a/linearize.h b/linearize.h
index 77ae7c9ac976..cc38fe07c974 100644
--- a/linearize.h
+++ b/linearize.h
@@ -311,6 +311,7 @@ struct entrypoint {
 };
 
 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
+extern void copy_select(struct basic_block *bb, struct instruction *br);
 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
 
 struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
diff --git a/simplify.c b/simplify.c
index f2aaa52de84b..633ebc6fad2c 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1745,8 +1745,24 @@ static int simplify_cast(struct instruction *insn)
 	return 0;
 }
 
+#include "flowgraph.h"
+static int is_defined_at(pseudo_t src, struct basic_block *bb)
+{
+	if (src->type != PSEUDO_REG)
+		return 1;
+	return domtree_dominates(bb, src->def->bb);
+}
+
+static int move_select_to(struct instruction *insn, struct basic_block *bb)
+{
+	copy_select(bb, insn);
+	kill_instruction(insn);
+	return REPEAT_CSE;
+}
+
 static int simplify_select(struct instruction *insn)
 {
+	struct basic_block *bb;
 	pseudo_t cond, src1, src2;
 
 	cond = insn->src1;
@@ -1782,6 +1798,24 @@ static int simplify_select(struct instruction *insn)
 		kill_use(&insn->src3);
 		return replace_with_value(insn, 0);
 	}
+
+	// Try to move this select 'up'.
+	bb = insn->bb;
+	while (bb->idom) {
+		bb = bb->idom;
+		if (bb == insn->bb)
+			goto out;
+		if (!is_defined_at(cond, bb))
+			goto out;
+		if (!is_defined_at(src1, bb))
+			goto out;
+		if (!is_defined_at(src2, bb))
+			goto out;
+	}
+	if (bb != insn->bb)
+		return move_select_to(insn, bb);
+
+out:
 	return 0;
 }
 
-- 
2.29.2

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Linus Torvalds]

On Fri, Nov 6, 2020 at 5:33 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> So, I think that the next questions are:
> * which selects should be moved up?
> * up to where should them be moved?

Honestly, it's not even clear they should be moved up. It could be
moved down too, particularly in this kind of case where there is only
one user of the result (ie move it down to just before the use).

Moving down to the use is in many ways is much easier than moving up,
because then you don't need to worry about whether the sources to the
select have been calculated yet. No need for any dominance analysis or
anything like that for that case.

But my personal guess is that by default we shouldn't try to
excessively move instructions unless we have an actual reason to do
so.

So I don't think your patch a good simplification in general.
Particularly the "move up" part, when you might just end up doing an
entirely unnecessary select that would normally have been done only in
some unusual conditional case.

Now, instead, I think the proper select simplification is to tie it
together with the conditional branch. Look at what I had after the
other select simplifications:

    .L0:
        <entry-point>
        cbr         %arg1, .L5, .L4

    .L4:
        call        spin_lock
        br          .L5

    .L5:
        # call      %r4 <- errno, %r1
        select.32   %r6 <- %arg1, $0xffffffff, $0
        cbr         %arg1, .L6, .L2

    .L2:
        call        spin_unlock
        br          .L6

    .L6:
        ret.32      %r6

and notice that

        cbr         %arg1, .L5, .L4
    .L5:
        select.32   %r6 <- %arg1, $0xffffffff, $0

sequence. In particular, notice how we have a conditional branch to a
"select" that has the *same* conditional as the branch!

So I think the *proper* fix is to not think of this case as "move the
select", but as a special case of branch following: the same way that
a conditional branch to another conditional branch can be simplified
if the condition is the same, you can simplify the case of
"conditional branch to select with the same condition".

That said, that "proper fix" looks a bit painful. My gut feel is that
we shouldn't have generated that "select" in the first place at all.
We should have kept it as a conditional branch, then done branch
following, and done the whole "turn a branch-over into a select" at a
later stage.

Have we done that if_convert_phi() simplification too early?

I didn't really follow the whole chain of how we got to this point.

              Linus

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Luc Van Oostenryck]

On Sat, Nov 07, 2020 at 11:39:42AM -0800, Linus Torvalds wrote:
> On Fri, Nov 6, 2020 at 5:33 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > So, I think that the next questions are:
> > * which selects should be moved up?
> > * up to where should them be moved?
> 
> Honestly, it's not even clear they should be moved up. It could be
> moved down too, particularly in this kind of case where there is only
> one user of the result (ie move it down to just before the use).
> 
> Moving down to the use is in many ways is much easier than moving up,
> because then you don't need to worry about whether the sources to the
> select have been calculated yet. No need for any dominance analysis or
> anything like that for that case.

It's just that in my experience, in these situation with context
imbalance, very often 'something' had to move up, just before the
'if' where the imbalance is created.

> But my personal guess is that by default we shouldn't try to
> excessively move instructions unless we have an actual reason to do
> so.
> 
> So I don't think your patch a good simplification in general.
> Particularly the "move up" part, when you might just end up doing an
> entirely unnecessary select that would normally have been done only in
> some unusual conditional case.

I totally agree with this.
 
> Now, instead, I think the proper select simplification is to tie it
> together with the conditional branch. Look at what I had after the
> other select simplifications:
> 
>     .L0:
>         <entry-point>
>         cbr         %arg1, .L5, .L4
> 
>     .L4:
>         call        spin_lock
>         br          .L5
> 
>     .L5:
>         # call      %r4 <- errno, %r1
>         select.32   %r6 <- %arg1, $0xffffffff, $0
>         cbr         %arg1, .L6, .L2
> 
>     .L2:
>         call        spin_unlock
>         br          .L6
> 
>     .L6:
>         ret.32      %r6
> 
> and notice that
> 
>         cbr         %arg1, .L5, .L4
>     .L5:
>         select.32   %r6 <- %arg1, $0xffffffff, $0
> 
> sequence. In particular, notice how we have a conditional branch to a
> "select" that has the *same* conditional as the branch!

Yes, once the SEL(SEL(x,C,0),C,0) is handled this all simplify to
	.L0:
		 <entry-point>
		 select.32   %r6 <- %arg1, $0xffffffff, $0
		 cbr         %arg1, .L6, .L4
	.L4:
		 call        spin_lock
		 # call      %r4 <- errno, %r1
		 call        spin_unlock
		 br          .L6
	.L6:
		 ret.32      %r6

but to me, this seems a very very special case, so not much interesting.
 
> So I think the *proper* fix is to not think of this case as "move the
> select", but as a special case of branch following: the same way that
> a conditional branch to another conditional branch can be simplified
> if the condition is the same, you can simplify the case of
> "conditional branch to select with the same condition".
> 
> That said, that "proper fix" looks a bit painful. My gut feel is that
> we shouldn't have generated that "select" in the first place at all.
> We should have kept it as a conditional branch, then done branch
> following, and done the whole "turn a branch-over into a select" at a
> later stage.
> 
> Have we done that if_convert_phi() simplification too early?

Absolutely. I've often observed that it inhibits other simplifications
related to conditionals. And, even when it doesn't, I think that many
select simplifications would already be handled at SETxx + CBR level
(like your previous SEL(x,x,0)).

So, yes, the if-conversion is a very valuable simplification but I also
think it's done too early. And there are some other simplifications that
are valuable but only if not done too early (sorry, I've no concrete
examples at hand). It slowly begins time to organize the optimizations
in several phases.

-- Luc

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Linus Torvalds]

On Sat, Nov 7, 2020 at 12:09 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Yes, once the SEL(SEL(x,C,0),C,0) is handled this all simplify to
>         .L0:
>                  <entry-point>
>                  select.32   %r6 <- %arg1, $0xffffffff, $0
>                  cbr         %arg1, .L6, .L4
>         .L4:
>                  call        spin_lock
>                  # call      %r4 <- errno, %r1
>                  call        spin_unlock
>                  br          .L6
>         .L6:
>                  ret.32      %r6
>
> but to me, this seems a very very special case, so not much interesting.

Oh, ok, so just fixing the missing simplification does actually fix it.

And I'm not sure how special-case this is. Because I think we _do_
actually generally doing the if-conversion "later", even if it's not a
separate phase, simply because we end up doing it at the "OP_PHI"
instruction, which should always end up linearizing after the branches
that should have been simplified.

So sometimes the ordering can be simply due to the order we see and
react to instructions.

> > Have we done that if_convert_phi() simplification too early?
>
> Absolutely. I've often observed that it inhibits other simplifications
> related to conditionals. And, even when it doesn't, I think that many
> select simplifications would already be handled at SETxx + CBR level
> (like your previous SEL(x,x,0)).

Yeah, the problem with doing multiple passes, though, is that you
inevitably end up wanting to repeat them, because a later phase will
cause you to be able to then do earlier phases again.

So there's never any one "correct" order to do things in, and I think
you always end up with those "oh, unlucky, we did that one
simplification that then made another one harder" regardless of what
you do.

Although we do already have "passes" with some things clearly done
before others (like turning symbols into pseudos before doing any
other optimizations). But those tend to be very clear "convert the
tree into the proper format for the next stage", not this kind of "one
optimization then causes/hinders others".

            Linus

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Luc Van Oostenryck]

On Sat, Nov 07, 2020 at 12:33:52PM -0800, Linus Torvalds wrote:
> On Sat, Nov 7, 2020 at 12:09 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > Yes, once the SEL(SEL(x,C,0),C,0) is handled this all simplify to
> >         .L0:
> >                  <entry-point>
> >                  select.32   %r6 <- %arg1, $0xffffffff, $0
> >                  cbr         %arg1, .L6, .L4
> >         .L4:
> >                  call        spin_lock
> >                  # call      %r4 <- errno, %r1
> >                  call        spin_unlock
> >                  br          .L6
> >         .L6:
> >                  ret.32      %r6
> >
> > but to me, this seems a very very special case, so not much interesting.
> 
> Oh, ok, so just fixing the missing simplification does actually fix it.

This case, yes. And I suppose will solves the problem Song had.
But, for example, none of the select simplifications I posted
yesterday (not the 'move-everything-up', of course) have any effect
on v5.10-rc1. I mean, I'm sure it they have some effect on the
generated code but not on the context imbalance warnings (or any
other warning).

> And I'm not sure how special-case this is. Because I think we _do_
> actually generally doing the if-conversion "later", even if it's not a
> separate phase, simply because we end up doing it at the "OP_PHI"
> instruction, which should always end up linearizing after the branches
> that should have been simplified.

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.

 
> So sometimes the ordering can be simply due to the order we see and
> react to instructions.
> 
> > > Have we done that if_convert_phi() simplification too early?
> >
> > Absolutely. I've often observed that it inhibits other simplifications
> > related to conditionals. And, even when it doesn't, I think that many
> > select simplifications would already be handled at SETxx + CBR level
> > (like your previous SEL(x,x,0)).
> 
> Yeah, the problem with doing multiple passes, though, is that you
> inevitably end up wanting to repeat them, because a later phase will
> cause you to be able to then do earlier phases again.
> 
> So there's never any one "correct" order to do things in, and I think
> you always end up with those "oh, unlucky, we did that one
> simplification that then made another one harder" regardless of what
> you do.

Yes, sure, I think it's in general inevitable. But I think that for the
if-conversion here it wouldn't be much of a problem because, in itself,
it doesn't create other 'functional'/value-related simplifications.
It only may create an empty BB that can then be simplified away with
some branch simplifications. Maybe I'm just an optimist.

But sure, it's hard to predict exactly the effect. I should experiment
a bit to see the impact on quality, complexity and time.

-- Luc

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Linus Torvalds]

On Sat, Nov 7, 2020 at 1:23 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> 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?"

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

             Linus

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Luc Van Oostenryck]

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@gmail.com> 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

Re: "warning: context imbalance" in kernel/bpf/hashtab.c

[Linus Torvalds]

On Sat, Nov 7, 2020 at 4:42 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> 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?

A lot? No. I've actively discouraged it.

It does exist - don't get me wrong - but it shouldn't be the normal pattern.

> 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();
>                 }
>         }

That _is_ a somewhat common case, and it's basically the "first helper
tells the caller that it took the lock".

The _really_ basic version of that is the various "trylock()" things,
which has that "__cond_lock()" macro in the kernel for it, so that
sparse can catch that very special case.

That said, it's still not the _common_ case, which is just that the
code is straightforward

    take_lock();
    do something under the lock
    drop_lock();

> 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;
>         }

Yeah, this is a more complex version of the same.

Clearly sparse doesn't grok it today, but the fact that your patches
make sparse able to track it is a good improvement.

> 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();
>         }

This really is invalid code. "major()" is done in two different lock contexts.

Sparse _should_ complain.

             Linus