Staging/comedi: Fixes static analysis warning raised by sparse

PATCH Dan Carpenter 4 participants 10 messages Jun 11, 2014 – Jun 30, 2014 5 messages not in the archive Sparse checker

Share & tools

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 20140610054741.GE5500@mwanda

A message that is not in the archive (sent off-list or not yet received): DC148C5AA1CEBA4E87973D432B1C2D8825E9AE6A@P3PWEX4MB008.ex4.secureserver.net

A message that is not in the archive (sent off-list or not yet received): 20140611065612.GQ5015@mwanda

A message that is not in the archive (sent off-list or not yet received): DC148C5AA1CEBA4E87973D432B1C2D8825E9CBD6@P3PWEX4MB008.ex4.secureserver.net

Dan Carpenter

author

2014-06-11 21:24 UTC #5 lore raw

Let's forward this to the Sparse mailing list.

We're seeing a Sparse false positive testing
drivers/staging/comedi/drivers/ni_pcimio.c.

CHECK drivers/staging/comedi/drivers/ni_pcimio.c
drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int

I have created some test code to demonstrate the problem (attached).

The check_shift_count() warning is only supposed to be printed for number literals but because of the way inline functions are expanded it still complains even though channel is a variable.

regards,
dan carpenter

#include <stdio.h>
#include <limits.h>
#include <string.h>

static inline unsigned ni_stc_dma_channel_select_bitfield(unsigned channel)

{
	if (channel < 4)
		return 1 << channel;
	return 0;
}

static inline void filter(int channel)

{
	if (channel < 0)
		return;
	ni_stc_dma_channel_select_bitfield(channel);
}

int main(void)

{
	filter(-1);

	return 0;
}

[email protected]

2014-06-11 21:45 UTC #6 lore raw

Quoted 11 lines · Dan Carpenter

Let's forward this to the Sparse mailing list.
We're seeing a Sparse false positive testing
drivers/staging/comedi/drivers/ni_pcimio.c.
CHECK drivers/staging/comedi/drivers/ni_pcimio.c
drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int

Quoted 5 lines

I have created some test code to demonstrate the problem (attached).
The check_shift_count() warning is only supposed to be printed for number literals but because of the way inline functions are expanded it still complains even though channel is a variable.

Thanks for the test case; this definitely makes no sense. I don't think Sparse will suddenly develop enough range analysis or reachability analysis to handle this case; I think the right answer is to avoid giving such warnings for shifts with a non-constant RHS.

Quoted 24 lines

#include <stdio.h>
#include <limits.h>
#include <string.h>
static inline unsigned ni_stc_dma_channel_select_bitfield(unsigned channel)
{
	if (channel < 4)
		return 1 << channel;
	return 0;
}
static inline void filter(int channel)
{
	if (channel < 0)
		return;
	ni_stc_dma_channel_select_bitfield(channel);
}
int main(void)
{
	filter(-1);

	return 0;
}

Sam Ravnborg

2014-06-15 19:41 UTC #7 lore raw

Hi Josh.

Quoted 14 lines · On Wed, Jun 11, 2014 at 02:45:29PM -0700, [email protected] wrote:

Quoted 13 lines · Dan Carpenter
Let's forward this to the Sparse mailing list.
We're seeing a Sparse false positive testing
drivers/staging/comedi/drivers/ni_pcimio.c.
CHECK drivers/staging/comedi/drivers/ni_pcimio.c
drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int
I have created some test code to demonstrate the problem (attached).

Quoted 8 lines

Quoted 3 lines
The check_shift_count() warning is only supposed to be printed for number literals but because of the way inline functions are expanded it still complains even though channel is a variable.
Thanks for the test case; this definitely makes no sense. I don't think Sparse will suddenly develop enough range analysis or reachability analysis to handle this case; I think the right answer is to avoid giving such warnings for shifts with a non-constant RHS.

Something like the appended?

It seems to work for me - and it cured a lot of warnings in math-emu.c on sparc. If it looks OK I will do a proper patch submission.

Sam

expand.c +1 -1

index 0f6720c..4a96de4 100644
@@ -187,7 +187,7 @@ static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
 		return 0;
 	r = right->value;
 	if (expr->op == SPECIAL_LEFTSHIFT || expr->op == SPECIAL_RIGHTSHIFT) {
-		if (r >= ctype->bit_size) {
+		if (expr->flags & Int_const_expr && r >= ctype->bit_size) {
 			if (conservative)
 				return 0;
 			r = check_shift_count(expr, ctype, r);

Dan Carpenter

author

2014-06-16 07:40 UTC #8 lore raw

expand.c static int simplify_int_binop(struct expression *expr, struct symbol *ctype) · line 190

Quoted 10 lines · Sam Ravnborg

expand.c +1 -1

index 0f6720c..4a96de4 100644
@@ -187,7 +187,7 @@ static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
 		return 0;
 	r = right->value;
 	if (expr->op == SPECIAL_LEFTSHIFT || expr->op == SPECIAL_RIGHTSHIFT) {
-		if (r >= ctype->bit_size) {
+		if (expr->flags & Int_const_expr && r >= ctype->bit_size) {

Thanks! I had no idea how to start writing a fix for this, but the test should be:

		if (expr->right->flags & Int_const_expr

Otherwise both sides of the shift have to be const.

expand.c static int simplify_int_binop(struct expression *expr, struct symbol *ctype) · line 193

Quoted 4 lines

expand.c +0 -0

 			if (conservative)
 				return 0;
 			r = check_shift_count(expr, ctype, r);

regards,
dan carpenter

Sam Ravnborg

2014-06-16 08:06 UTC #9 lore raw

Quoted 14 lines · Dan Carpenter

expand.c static int simplify_int_binop(struct expression *expr, struct symbol *ctype) · line 190
Quoted 10 lines · Sam Ravnborg
expand.c +1 -1
index 0f6720c..4a96de4 100644
@@ -187,7 +187,7 @@ static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
 		return 0;
 	r = right->value;
 	if (expr->op == SPECIAL_LEFTSHIFT || expr->op == SPECIAL_RIGHTSHIFT) {
-		if (r >= ctype->bit_size) {
+		if (expr->flags & Int_const_expr && r >= ctype->bit_size) {
Thanks! I had no idea how to start writing a fix for this, but the test should be:

Quoted 3 lines

		if (expr->right->flags & Int_const_expr
Otherwise both sides of the shift have to be const.

Thanks - will fix.

I will update the test case to check for this, and then send a proper patch.

Sam

Christopher Li

maintainer

2014-06-28 18:07 UTC #10 lore raw

In reply to [email protected]

Sorry for the late reply.

Quoted 4 lines · On Wed, Jun 11, 2014 at 2:45 PM, <[email protected]> wrote:

Quoted 3 lines · Dan Carpenter
Let's forward this to the Sparse mailing list.
We're seeing a Sparse false positive testing

No, this is a valid complain. See my point follows.

Quoted 10 lines

Quoted 10 lines
drivers/staging/comedi/drivers/ni_pcimio.c.
CHECK drivers/staging/comedi/drivers/ni_pcimio.c
drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int
I have created some test code to demonstrate the problem (attached).

Quoted 8 lines

Quoted 3 lines
The check_shift_count() warning is only supposed to be printed for number literals but because of the way inline functions are expanded it still complains even though channel is a variable.
Thanks for the test case; this definitely makes no sense. I don't think Sparse will suddenly develop enough range analysis or reachability analysis to handle this case; I think the right answer is to avoid giving such warnings for shifts with a non-constant RHS.

Sparse can handle inline function expand and some constant propagate. In this case, sparse seems doing the right thing. Sparse actually sees the channel value being 4294967295 (-1).

Quoted 1 line

Quoted 1 line
static inline unsigned ni_stc_dma_channel_select_bitfield(unsigned channel)

This is the bug. See this channel is *unsigned*. When -1 pass into channel, it become a really large number 4294967295.
The code does request C compiler to perform left shift 4294967295 bits. Which did not make sense.

Quoted 11 lines

{
      if (channel < 4)
              return 1 << channel;
      return 0;
}

static inline void filter(int channel)

{
      if (channel < 0)
              return;
      ni_stc_dma_channel_select_bitfield(channel);

See this channel is *signed*, with -1 convert to 4294967295. This is a bug in the kernel source not sparse.

Chris

Josh Triplett

2014-06-28 19:20 UTC #11 lore raw

Quoted 44 lines · Christopher Li

Quoted 4 lines · On Wed, Jun 11, 2014 at 2:45 PM, <[email protected]> wrote:
Quoted 3 lines · Dan Carpenter
Let's forward this to the Sparse mailing list.
We're seeing a Sparse false positive testing
No, this is a valid complain. See my point follows.
Quoted 10 lines
Quoted 10 lines
drivers/staging/comedi/drivers/ni_pcimio.c.
CHECK drivers/staging/comedi/drivers/ni_pcimio.c
drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int drivers/staging/comedi/drivers/ni_stc.h:720:26: warning: shift too big (4294967295) for type int
I have created some test code to demonstrate the problem (attached).
Quoted 8 lines
Quoted 3 lines
The check_shift_count() warning is only supposed to be printed for number literals but because of the way inline functions are expanded it still complains even though channel is a variable.
Thanks for the test case; this definitely makes no sense. I don't think Sparse will suddenly develop enough range analysis or reachability analysis to handle this case; I think the right answer is to avoid giving such warnings for shifts with a non-constant RHS.
Sparse can handle inline function expand and some constant propagate. In this case, sparse seems doing the right thing. Sparse actually sees the channel value being 4294967295 (-1).
Quoted 1 line
Quoted 1 line
static inline unsigned ni_stc_dma_channel_select_bitfield(unsigned channel)
This is the bug. See this channel is *unsigned*. When -1 pass into channel, it become a really large number 4294967295.
The code does request C compiler to perform left shift 4294967295 bits. Which did not make sense.
Quoted 6 lines
Quoted 6 lines
{
      if (channel < 4)
              return 1 << channel;
      return 0;
}

Quoted 8 lines

Quoted 5 lines
Quoted 5 lines
static inline void filter(int channel)
{
      if (channel < 0)
              return;
      ni_stc_dma_channel_select_bitfield(channel);
See this channel is *signed*, with -1 convert to 4294967295. This is a bug in the kernel source not sparse.

Except that "filter" has an "int channel" (signed), so it can successfully test "channel < 0" and return early; it'll never call ni_stc_dma_channel_select_bitfield(channel) with a negative number.

I do agree that this code should sort out the signedness of its types, but in this case I don't think the bad shift can actually happen, making this a false positive.

- Josh Triplett

Christopher Li

maintainer

2014-06-29 03:09 UTC #12 lore raw

Quoted 7 lines · Josh Triplett

Except that "filter" has an "int channel" (signed), so it can successfully test "channel < 0" and return early; it'll never call ni_stc_dma_channel_select_bitfield(channel) with a negative number.
I do agree that this code should sort out the signedness of its types, but in this case I don't think the bad shift can actually happen, making this a false positive.

Ah, I see. I agree that the warning happen on the dead code.

However, the root cause for the warning is not because sparse can not figure out the value of "channel". Sparse actually correctly does the inline and figure out "channel" is 4294967295. The root cause of your complain against sparse is that it happen on the dead code.

I don' think the patch is the right fix for this problem though. This patch try to silence a warning purely because it can happen on dead code, otherwise perfectly valid warning.

My point is that, it can happen on dead code is not a valid reason to weaken the warning. Sparse can give any possible warning on dead code. e.g. On the dead code path, you can construct an address space warning. Do we weakling the address space warning purely because it can happen on the dead code as well? Of course not. The same apply to any other sparse warnings.

So if there is a bug, It is sparse did not know exactly which part of the code is dead on AST level. If you enable the "#if 0" inside expand_if_statement(), sparse can actually correctly expand "if (channel < 0)" into "return". Of course, it still can't handle jump into dead code situation, which is the reason that piece of code is not enabled in the first place. It needs more work. I think that is a better approach than just random weakening some warnings on dead code path.

Chris

Christopher Li

maintainer

2014-06-30 17:49 UTC #13 lore raw

Quoted 2 lines · Christopher Li

So if there is a bug, It is sparse did not know exactly which part of the code is dead on AST level. If you enable the "#if 0" inside

I am thinking about how to fix the dead code issue. Try to do more than trivial dead code analyses is really not the right place for AST.

Actually, there is a simple way out. We can just move the warning to the linearize instruction level.

 $ ./test-linearize /tmp/test_shift.c
/tmp/test_shift.c:8:26: warning: shift too big (4294967295) for type int
main:
.L0x7f8f490e5010:
    <entry-point>
    # call      %r1 <- filter, $0xffffffff
    ret.32      $0

You see, once drop into the instruction level, sparse already know that code is dead.

Since the sparse is already linearizing instruction to perform the context check. We just need to move the warning from AST to instruction level.

The warning should be trivial in instruction level. We are looking for an instruction has larger than type size constant shift value.

Comments and feed backs, even patches?

Chris

Christopher Li

maintainer

2014-06-30 18:32 UTC #14 lore raw

Quoted 3 lines · Christopher Li

The warning should be trivial in instruction level. We are looking for an instruction has larger than type size constant shift value.

Actually, just try it. Not as trivial as I thought.

The problem is that, in the instruction level, sparse will optimize away the shift instruction when it see a larger than type size shift. The finial instruction level don't see the big constant shift any way. Need to catch it before the instruction get optimized away.

That is unfortunate. If we check it too early, we can't tell it is in the dead code. If we check it too late, the instruction itself get optimized away.

Chris