[PATCH 1/2] Fix cast instruction generation

[PATCH 1/2] Fix cast instruction generation

[Linus Torvalds]

From: Linus Torvalds <torvalds@woody.linux-foundation.org>
Date: Thu, 24 Apr 2008 14:45:43 -0700

Whether it's a sign-extending cast or not depends on the source
of the cast, not destination. The final size of the cast depends
on the destination, of course.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
In thread "[PATCH] RxRPC: Fix a regression in the RXKAD security module"

On Thu, 24 Apr 2008, Linus Torvalds wrote:
> 
> Ok, that looks stupid, and should even have had a warning (shifting a u16 
> right by 16 should warn about it being pointless, but doesn't, because the 
> compiler quietly expands it to "int" in the meantime).
> 
> Hmm. I could do something to sparse that warns about that too. 

Something along the lines of this?

Almost totally untested. This first patch is just preparatory to get the 
next patch working.

 linearize.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/linearize.c b/linearize.c
index 45bb168..ec48dac 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1097,10 +1097,10 @@ static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
  * case, since you can't access through it anyway without another
  * cast.
  */
-static struct instruction *alloc_cast_instruction(struct symbol *ctype)
+static struct instruction *alloc_cast_instruction(struct symbol *src, struct symbol *ctype)
 {
 	int opcode = OP_CAST;
-	struct symbol *base = ctype;
+	struct symbol *base = src;
 
 	if (base->ctype.modifiers & MOD_SIGNED)
 		opcode = OP_SCAST;
@@ -1127,7 +1127,7 @@ static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *
 		return VOID;
 	if (from->bit_size < 0 || to->bit_size < 0)
 		return VOID;
-	insn = alloc_cast_instruction(to);
+	insn = alloc_cast_instruction(from, to);
 	result = alloc_pseudo(insn);
 	insn->target = result;
 	insn->orig_type = from;
-- 
1.5.5.1.92.ga5bdc

[PATCH 2/2] Simplify (and warn about) right shifts that result in zero

[Linus Torvalds]

From: Linus Torvalds <torvalds@woody.linux-foundation.org>
Date: Thu, 24 Apr 2008 14:47:04 -0700

..due to limited source sizes.

Yeah, should do this for left shifts too.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Again, not a lot of testing, but it _looks_ fairly sane.

The constant value case of "operand_size()" is not actually ever used 
(because a totally constant right shift will be optimized in other 
places), but I wrote the code so that perhaps other cases could use this. 
Whatever. 

The "do the same for left shifts" could do a similar check, but based 
purely on the size of the operation, not the size of the operand value. 
Which makes it not very interesting.

 simplify.c |   57 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 56 insertions(+), 1 deletions(-)

diff --git a/simplify.c b/simplify.c
index 94e14d2..8200584 100644
--- a/simplify.c
+++ b/simplify.c
@@ -256,6 +256,59 @@ static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 	return REPEAT_CSE;
 }
 
+static unsigned int value_size(long long value)
+{
+	value >>= 8;
+	if (!value)
+		return 8;
+	value >>= 8;
+	if (!value)
+		return 16;
+	value >>= 16;
+	if (!value)
+		return 32;
+	return 64;
+}
+
+/*
+ * Try to determine the maximum size of bits in a pseudo.
+ *
+ * Right now this only follow casts and constant values, but we
+ * could look at things like logical 'and' instructions etc.
+ */
+static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
+{
+	unsigned int size = insn->size;
+
+	if (pseudo->type == PSEUDO_REG) {
+		struct instruction *src = pseudo->def;
+		if (src && src->opcode == OP_CAST && src->orig_type) {
+			unsigned int orig_size = src->orig_type->bit_size;
+			if (orig_size < size)
+				size = orig_size;
+		}
+	}
+	if (pseudo->type == PSEUDO_VAL) {
+		unsigned int orig_size = value_size(pseudo->value);
+		if (orig_size < size)
+			size = orig_size;
+	}
+	return size;
+}
+
+static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
+{
+	unsigned int size = operand_size(insn, pseudo);
+
+	if (value >= size) {
+		warning(insn->pos, "right shift by bigger than source value");
+		return replace_with_pseudo(insn, value_pseudo(0));
+	}
+	if (!value)
+		return replace_with_pseudo(insn, pseudo);
+	return 0;
+}
+
 static int simplify_constant_rightside(struct instruction *insn)
 {
 	long long value = insn->src2->value;
@@ -272,10 +325,12 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_OR: case OP_XOR:
 	case OP_OR_BOOL:
 	case OP_SHL:
-	case OP_LSR: case OP_ASR:
+	case OP_LSR:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src1);
 		return 0;
+	case OP_ASR:
+		return simplify_asr(insn, insn->src1, value);
 
 	case OP_MULU: case OP_MULS:
 	case OP_AND_BOOL:
-- 
1.5.5.1.92.ga5bdc

Re: [PATCH 2/2] Simplify (and warn about) right shifts that result in zero

[Pavel Roskin]

On Thu, 2008-04-24 at 14:54 -0700, Linus Torvalds wrote:
> +		warning(insn->pos, "right shift by bigger than source value");

The sparse warning for shifts exceeding the target width is:

"shift too big (%d) for type %d"

And the gcc 4.3 warning is

"right shift count >= width of type"

So I would suggest a similar warning is this case.  Maybe "right shift
too big (%u) for source type %s" (if the source type is readily
available) or "right shift count (%d) >= width of type (%d)"

By the way, your patch has caught something interesting in
net/mac80211/tkip.c:

        iv32 = data[hdr_len + 4] +
                (data[hdr_len + 5] >> 8) +
                (data[hdr_len + 6] >> 16) +
                (data[hdr_len + 7] >> 24);

Wow!

-- 
Regards,
Pavel Roskin

Re: [PATCH 2/2] Simplify (and warn about) right shifts that result in zero

[Linus Torvalds]

On Thu, 24 Apr 2008, Pavel Roskin wrote:
> 
> So I would suggest a similar warning is this case.  Maybe "right shift
> too big (%u) for source type %s" (if the source type is readily
> available) or "right shift count (%d) >= width of type (%d)"

That's fine, except we shouldn't talk about "type", since we're really 
doing some really stupid value analysis (the *type* will generally have 
been cast to a bigger one by the implicit C type evaluation rules).

> By the way, your patch has caught something interesting in
> net/mac80211/tkip.c:
> 
>         iv32 = data[hdr_len + 4] +
>                 (data[hdr_len + 5] >> 8) +
>                 (data[hdr_len + 6] >> 16) +
>                 (data[hdr_len + 7] >> 24);
>
> Wow!

Heh. That does look like somebody is shifting the wrong way, and 
apparently the new warning was worth something ;)

		Linus

Re: [PATCH 2/2] Simplify (and warn about) right shifts that result in zero

[Pavel Roskin]

On Thu, 2008-04-24 at 17:03 -0700, Linus Torvalds wrote:

> Heh. That does look like somebody is shifting the wrong way, and 
> apparently the new warning was worth something ;)

Yes, definitely.  The patch is on the way to linux-wireless.  Losing 24
bits of entropy in the initialization vector is not good, to put it
mildly.

The only other "shift" warning in the kernel for my configuration
indicates dead code in drivers/serial/serial_core.c:

tmp.port_high = (long) port->iobase >> HIGH_BITS_OFFSET;

HIGH_BITS_OFFSET is 32 bit on 64-bit systems, and port->iobase is always
int.  On 32-bit systems, HIGH_BITS_OFFSET is 0 and the code would not be
executed.  The code predates the dawn of git.  The whole thing needs
some serious cleanup, but apart from that, the warning appears to be
harmless.

There are no more warnings mentioning "shift", and the only two warnings
are useful, or which one may be a serious bug.  That's a pretty good
result!

-- 
Regards,
Pavel Roskin

Re: [PATCH 2/2] Simplify (and warn about) right shifts that result in zero

[Josh Triplett]

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

Linus Torvalds wrote:
> On Thu, 24 Apr 2008, Pavel Roskin wrote:
>> So I would suggest a similar warning is this case.  Maybe "right shift
>> too big (%u) for source type %s" (if the source type is readily
>> available) or "right shift count (%d) >= width of type (%d)"
> 
> That's fine, except we shouldn't talk about "type", since we're really 
> doing some really stupid value analysis (the *type* will generally have 
> been cast to a bigger one by the implicit C type evaluation rules).

Pavel, it sounds like you agree with the semantic of the warning, and
just want an different wording.  Thus, I've applied and pushed the patch;
feel free to propose a change to the wording in a subsequent patch.

>> By the way, your patch has caught something interesting in
>> net/mac80211/tkip.c:
>>
>>         iv32 = data[hdr_len + 4] +
>>                 (data[hdr_len + 5] >> 8) +
>>                 (data[hdr_len + 6] >> 16) +
>>                 (data[hdr_len + 7] >> 24);
>>
>> Wow!
> 
> Heh. That does look like somebody is shifting the wrong way, and 
> apparently the new warning was worth something ;)

Nice.

- Josh Triplett



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: [PATCH 2/2] Simplify (and warn about) right shifts that result in zero

[Josh Triplett]

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

Linus Torvalds wrote:
> From: Linus Torvalds <torvalds@woody.linux-foundation.org>
> Date: Thu, 24 Apr 2008 14:47:04 -0700
> 
> ..due to limited source sizes.
> 
> Yeah, should do this for left shifts too.
> 
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> ---
> 
> Again, not a lot of testing, but it _looks_ fairly sane.
> 
> The constant value case of "operand_size()" is not actually ever used 
> (because a totally constant right shift will be optimized in other 
> places), but I wrote the code so that perhaps other cases could use this. 
> Whatever. 
> 
> The "do the same for left shifts" could do a similar check, but based 
> purely on the size of the operation, not the size of the operand value. 
> Which makes it not very interesting.

Applied and pushed.

- Josh Triplett



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: [PATCH 1/2] Fix cast instruction generation

[Josh Triplett]

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

Linus Torvalds wrote:
> From: Linus Torvalds <torvalds@woody.linux-foundation.org>
> Date: Thu, 24 Apr 2008 14:45:43 -0700
> 
> Whether it's a sign-extending cast or not depends on the source
> of the cast, not destination. The final size of the cast depends
> on the destination, of course.
> 
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> ---
> In thread "[PATCH] RxRPC: Fix a regression in the RXKAD security module"
> 
> On Thu, 24 Apr 2008, Linus Torvalds wrote:
>> Ok, that looks stupid, and should even have had a warning (shifting a u16 
>> right by 16 should warn about it being pointless, but doesn't, because the 
>> compiler quietly expands it to "int" in the meantime).
>>
>> Hmm. I could do something to sparse that warns about that too. 
> 
> Something along the lines of this?

Applied and pushed.

- Josh Triplett



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]