[PATCH 0/3] catch non-sign-extended '~' brainos

[PATCH 0/3] catch non-sign-extended '~' brainos

[Phil Carmody]

Chris, fellow sparsers,

Bitwise-not is often used to create masks. Unfortunately implicit conversions
to longer types may leave the recipient with fewer set bit than he expected,
if he started with an unsigned type. It's nice to warn that such constructs
are dubious.

The guts for the fix are in patch 2. I'm not sure this is the right location
for the fix, but the prior logical-not checks are quite closely related, so
I bundled them in together.

As an aside - while sniffing around that file, I came across a lot of helpers
who could have their pointer parameters made const - is there any interest in
some const clean-up, or is that unwanted comma-fudging?

Cheers,
Phil

[PATCH 1/3] sparse: Just use simple ints for decision variables

[Phil Carmody]

The expressions are just ints, and const is pointess.

Signed-off-by: Phil Carmody <phil@dovecot.fi>
---
 evaluate.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/evaluate.c b/evaluate.c
index 6655615..9052962 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -917,10 +917,10 @@ static struct symbol *evaluate_binop(struct expression *expr)
 			rtype = integer_promotion(rtype);
 		} else {
 			// The rest do usual conversions
-			const unsigned left_not  = expr->left->type == EXPR_PREOP
-			                           && expr->left->op == '!';
-			const unsigned right_not = expr->right->type == EXPR_PREOP
-			                           && expr->right->op == '!';
+			int left_not  = expr->left->type == EXPR_PREOP
+					&& expr->left->op == '!';
+			int right_not = expr->right->type == EXPR_PREOP
+			                && expr->right->op == '!';
 			if ((op == '&' || op == '|') && (left_not || right_not))
 				warning(expr->pos, "dubious: %sx %c %sy",
 				        left_not ? "!" : "",
-- 
2.0.0

[PATCH 2/3] sparse: detect non-sign-extended masks created by '~'

[Phil Carmody]

Consider the operation of rounding up to the nearest multiple of a power of 2.
e.g.  #define ALLOC_SIZE(t) ((sizeof(t) + ASIZE - 1) & ~(ASIZE - 1))

If ASIZE is unfortunately defined as an unsigned type smaller than size_t,
then the ~ will not undergo sign-bit extension, and the incorrect mask will
be used. If used in a memory allocation context this could be fatal.

Warn about such dubious 'large op ~short' usage.

Signed-off-by: Phil Carmody <phil@dovecot.fi>
---
 evaluate.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/evaluate.c b/evaluate.c
index 9052962..c0f3c91 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -189,6 +189,14 @@ left:
 	return left;
 }
 
+static int is_bigger_int_type(struct symbol *left, struct symbol *right)
+{
+	left = integer_promotion(left);
+	right = integer_promotion(right);
+
+	return (left->bit_size > right->bit_size);
+}
+
 static int same_cast_type(struct symbol *orig, struct symbol *new)
 {
 	return orig->bit_size == new->bit_size &&
@@ -927,6 +935,19 @@ static struct symbol *evaluate_binop(struct expression *expr)
 					op,
 					right_not ? "!" : "");
 
+			left_not  = expr->left->type == EXPR_PREOP
+					&& expr->left->op == '~';
+			right_not = expr->right->type == EXPR_PREOP
+			                && expr->right->op == '~';
+			if ((left_not && is_bigger_int_type(rtype, ltype)
+			     && (ltype->ctype.modifiers & MOD_UNSIGNED)) ||
+			    (right_not && is_bigger_int_type(ltype, rtype)
+			     && (rtype->ctype.modifiers & MOD_UNSIGNED)))
+				warning(expr->pos, "dubious: %sx %c %sy",
+				        left_not ? "~" : "",
+					op,
+					right_not ? "~" : "");
+
 			ltype = usual_conversions(op, expr->left, expr->right,
 						  lclass, rclass, ltype, rtype);
 			ctype = rtype = ltype;
-- 
2.0.0

[PATCH 3/3] validation: dubious bitwise operations with nots

[Phil Carmody]

Add some bitwise not tests.

Signed-off-by: Phil Carmody <phil@dovecot.fi>
---
 validation/dubious-bitwise-with-not.c | 34 +++++++++++++++++++++++++++++++++-
 1 file changed, 33 insertions(+), 1 deletion(-)

diff --git a/validation/dubious-bitwise-with-not.c b/validation/dubious-bitwise-with-not.c
index c48bcae..1cfd5c5 100644
--- a/validation/dubious-bitwise-with-not.c
+++ b/validation/dubious-bitwise-with-not.c
@@ -10,8 +10,32 @@ static unsigned int ok5  = !1 && !2;
 static unsigned int bad5 = !1 &  !2;
 static unsigned int ok6  = !1 || !2;
 static unsigned int bad6 = !1 |  !2;
+static unsigned long long ok7a  = 0x100000001ull & ~1;
+static unsigned long long ok7b  = 0x100000001ull & ~1ull;
+static unsigned long long bad7  = 0x100000001ull & ~1u;
+static unsigned long long ok8a  = ~1    & 0x100000001ull;
+static unsigned long long ok8b  = ~1ull & 0x100000001ull;
+static unsigned long long bad8  = ~1u   & 0x100000001ull;
+static unsigned long long ok9a  = 0x100000001ull | ~1;
+static unsigned long long ok9b  = 0x100000001ull | ~1ull;
+static unsigned long long bad9  = 0x100000001ull | ~1u;
+static unsigned long long ok10a = ~1    | 0x100000001ull;
+static unsigned long long ok10b = ~1ull | 0x100000001ull;
+static unsigned long long bad10 = ~1u   | 0x100000001ull;
+static unsigned long long ok11a = 0x100000001ull + ~1;
+static unsigned long long ok11b = 0x100000001ull + ~1ull;
+static unsigned long long bad11 = 0x100000001ull + ~1u;
+static unsigned long long ok12a = ~1    + 0x100000001ull;
+static unsigned long long ok12b = ~1ull + 0x100000001ull;
+static unsigned long long bad12 = ~1u   + 0x100000001ull;
+static unsigned long long ok13a = 0x100000001ull - ~1;
+static unsigned long long ok13b = 0x100000001ull - ~1ull;
+static unsigned long long bad13 = 0x100000001ull - ~1u;
+static unsigned long long ok14a = ~1    - 0x100000001ull;
+static unsigned long long ok14b = ~1ull - 0x100000001ull;
+static unsigned long long bad14 = ~1u   - 0x100000001ull;
 /*
- * check-name: Dubious bitwise operation on !x
+ * check-name: Dubious bitwise operations with nots
  *
  * check-error-start
 dubious-bitwise-with-not.c:2:31: warning: dubious: !x & y
@@ -20,5 +44,13 @@ dubious-bitwise-with-not.c:6:31: warning: dubious: x & !y
 dubious-bitwise-with-not.c:8:31: warning: dubious: x | !y
 dubious-bitwise-with-not.c:10:31: warning: dubious: !x & !y
 dubious-bitwise-with-not.c:12:31: warning: dubious: !x | !y
+dubious-bitwise-with-not.c:15:50: warning: dubious: x & ~y
+dubious-bitwise-with-not.c:18:41: warning: dubious: ~x & y
+dubious-bitwise-with-not.c:21:50: warning: dubious: x | ~y
+dubious-bitwise-with-not.c:24:41: warning: dubious: ~x | y
+dubious-bitwise-with-not.c:27:50: warning: dubious: x + ~y
+dubious-bitwise-with-not.c:30:41: warning: dubious: ~x + y
+dubious-bitwise-with-not.c:33:50: warning: dubious: x - ~y
+dubious-bitwise-with-not.c:36:41: warning: dubious: ~x - y
  * check-error-end
  */
-- 
2.0.0

Re: [PATCH 3/3] validation: dubious bitwise operations with nots

[Josh Triplett]

On Mon, Jun 09, 2014 at 02:58:02PM +0300, Phil Carmody wrote:
> Add some bitwise not tests.
> 
> Signed-off-by: Phil Carmody <phil@dovecot.fi>
> ---
>  validation/dubious-bitwise-with-not.c | 34 +++++++++++++++++++++++++++++++++-
>  1 file changed, 33 insertions(+), 1 deletion(-)
> 
> diff --git a/validation/dubious-bitwise-with-not.c b/validation/dubious-bitwise-with-not.c
> index c48bcae..1cfd5c5 100644
> --- a/validation/dubious-bitwise-with-not.c
> +++ b/validation/dubious-bitwise-with-not.c
> @@ -10,8 +10,32 @@ static unsigned int ok5  = !1 && !2;
>  static unsigned int bad5 = !1 &  !2;
>  static unsigned int ok6  = !1 || !2;
>  static unsigned int bad6 = !1 |  !2;
> +static unsigned long long ok7a  = 0x100000001ull & ~1;
> +static unsigned long long ok7b  = 0x100000001ull & ~1ull;
> +static unsigned long long bad7  = 0x100000001ull & ~1u;
> +static unsigned long long ok8a  = ~1    & 0x100000001ull;
> +static unsigned long long ok8b  = ~1ull & 0x100000001ull;
> +static unsigned long long bad8  = ~1u   & 0x100000001ull;
> +static unsigned long long ok9a  = 0x100000001ull | ~1;
> +static unsigned long long ok9b  = 0x100000001ull | ~1ull;
> +static unsigned long long bad9  = 0x100000001ull | ~1u;
> +static unsigned long long ok10a = ~1    | 0x100000001ull;
> +static unsigned long long ok10b = ~1ull | 0x100000001ull;
> +static unsigned long long bad10 = ~1u   | 0x100000001ull;
> +static unsigned long long ok11a = 0x100000001ull + ~1;
> +static unsigned long long ok11b = 0x100000001ull + ~1ull;
> +static unsigned long long bad11 = 0x100000001ull + ~1u;
> +static unsigned long long ok12a = ~1    + 0x100000001ull;
> +static unsigned long long ok12b = ~1ull + 0x100000001ull;
> +static unsigned long long bad12 = ~1u   + 0x100000001ull;
> +static unsigned long long ok13a = 0x100000001ull - ~1;
> +static unsigned long long ok13b = 0x100000001ull - ~1ull;
> +static unsigned long long bad13 = 0x100000001ull - ~1u;
> +static unsigned long long ok14a = ~1    - 0x100000001ull;
> +static unsigned long long ok14b = ~1ull - 0x100000001ull;
> +static unsigned long long bad14 = ~1u   - 0x100000001ull;
>  /*
> - * check-name: Dubious bitwise operation on !x
> + * check-name: Dubious bitwise operations with nots

For clarity, I'd suggest writing this as "with !x or ~x".

>   *
>   * check-error-start
>  dubious-bitwise-with-not.c:2:31: warning: dubious: !x & y
> @@ -20,5 +44,13 @@ dubious-bitwise-with-not.c:6:31: warning: dubious: x & !y
>  dubious-bitwise-with-not.c:8:31: warning: dubious: x | !y
>  dubious-bitwise-with-not.c:10:31: warning: dubious: !x & !y
>  dubious-bitwise-with-not.c:12:31: warning: dubious: !x | !y
> +dubious-bitwise-with-not.c:15:50: warning: dubious: x & ~y
> +dubious-bitwise-with-not.c:18:41: warning: dubious: ~x & y
> +dubious-bitwise-with-not.c:21:50: warning: dubious: x | ~y
> +dubious-bitwise-with-not.c:24:41: warning: dubious: ~x | y
> +dubious-bitwise-with-not.c:27:50: warning: dubious: x + ~y
> +dubious-bitwise-with-not.c:30:41: warning: dubious: ~x + y
> +dubious-bitwise-with-not.c:33:50: warning: dubious: x - ~y
> +dubious-bitwise-with-not.c:36:41: warning: dubious: ~x - y
>   * check-error-end
>   */
> -- 
> 2.0.0
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 2/3] sparse: detect non-sign-extended masks created by '~'

[Josh Triplett]

On Mon, Jun 09, 2014 at 02:58:01PM +0300, Phil Carmody wrote:
> Consider the operation of rounding up to the nearest multiple of a power of 2.
> e.g.  #define ALLOC_SIZE(t) ((sizeof(t) + ASIZE - 1) & ~(ASIZE - 1))
> 
> If ASIZE is unfortunately defined as an unsigned type smaller than size_t,
> then the ~ will not undergo sign-bit extension, and the incorrect mask will
> be used. If used in a memory allocation context this could be fatal.
> 
> Warn about such dubious 'large op ~short' usage.
> 
> Signed-off-by: Phil Carmody <phil@dovecot.fi>
> ---
>  evaluate.c | 21 +++++++++++++++++++++
>  1 file changed, 21 insertions(+)
> 
> diff --git a/evaluate.c b/evaluate.c
> index 9052962..c0f3c91 100644
> --- a/evaluate.c
> +++ b/evaluate.c
> @@ -189,6 +189,14 @@ left:
>  	return left;
>  }
>  
> +static int is_bigger_int_type(struct symbol *left, struct symbol *right)
> +{
> +	left = integer_promotion(left);
> +	right = integer_promotion(right);
> +
> +	return (left->bit_size > right->bit_size);
> +}
> +
>  static int same_cast_type(struct symbol *orig, struct symbol *new)
>  {
>  	return orig->bit_size == new->bit_size &&
> @@ -927,6 +935,19 @@ static struct symbol *evaluate_binop(struct expression *expr)
>  					op,
>  					right_not ? "!" : "");
>  
> +			left_not  = expr->left->type == EXPR_PREOP
> +					&& expr->left->op == '~';
> +			right_not = expr->right->type == EXPR_PREOP
> +			                && expr->right->op == '~';

Ah, now I see why you wanted these to not use "const".  Fair enough.
"bool" still seems like the right type, though.

> +			if ((left_not && is_bigger_int_type(rtype, ltype)
> +			     && (ltype->ctype.modifiers & MOD_UNSIGNED)) ||
> +			    (right_not && is_bigger_int_type(ltype, rtype)
> +			     && (rtype->ctype.modifiers & MOD_UNSIGNED)))

You might consider wrapping the common expression here, along with the
corresponding previous _not expression, into a function, and then
calling it twice, flipping the arguments around for the second call.

> +				warning(expr->pos, "dubious: %sx %c %sy",
> +				        left_not ? "~" : "",
> +					op,
> +					right_not ? "~" : "");

What happens here if left_not && right_not?  Should this warning still
occur?  I *think* it still makes sense for it to, but the warning
message might prove less informative.

> +
>  			ltype = usual_conversions(op, expr->left, expr->right,
>  						  lclass, rclass, ltype, rtype);
>  			ctype = rtype = ltype;

Re: [PATCH 2/3] sparse: detect non-sign-extended masks created by '~'

[Phil Carmody]

On Mon, Jun 09, 2014 at 06:34:24AM -0700, Josh Triplett wrote:

Thanks for the  quick response.

> On Mon, Jun 09, 2014 at 02:58:01PM +0300, Phil Carmody wrote:
> > Consider the operation of rounding up to the nearest multiple of a power of 2.
> > e.g.  #define ALLOC_SIZE(t) ((sizeof(t) + ASIZE - 1) & ~(ASIZE - 1))
> > 
> > If ASIZE is unfortunately defined as an unsigned type smaller than size_t,
> > then the ~ will not undergo sign-bit extension, and the incorrect mask will
> > be used. If used in a memory allocation context this could be fatal.
> > 
> > Warn about such dubious 'large op ~short' usage.
> > 
> > Signed-off-by: Phil Carmody <phil@dovecot.fi>
> > ---
> >  evaluate.c | 21 +++++++++++++++++++++
> >  1 file changed, 21 insertions(+)
> > 
> > diff --git a/evaluate.c b/evaluate.c
> > index 9052962..c0f3c91 100644
> > --- a/evaluate.c
> > +++ b/evaluate.c
> > @@ -189,6 +189,14 @@ left:
> >  	return left;
> >  }
> >  
> > +static int is_bigger_int_type(struct symbol *left, struct symbol *right)
> > +{
> > +	left = integer_promotion(left);
> > +	right = integer_promotion(right);
> > +
> > +	return (left->bit_size > right->bit_size);
> > +}
> > +
> >  static int same_cast_type(struct symbol *orig, struct symbol *new)
> >  {
> >  	return orig->bit_size == new->bit_size &&
> > @@ -927,6 +935,19 @@ static struct symbol *evaluate_binop(struct expression *expr)
> >  					op,
> >  					right_not ? "!" : "");
> >  
> > +			left_not  = expr->left->type == EXPR_PREOP
> > +					&& expr->left->op == '~';
> > +			right_not = expr->right->type == EXPR_PREOP
> > +			                && expr->right->op == '~';
> 
> Ah, now I see why you wanted these to not use "const".  Fair enough.
> "bool" still seems like the right type, though.

There did seem to be general bool-avoidance in the code, it would have been
my preference too.
 
> > +			if ((left_not && is_bigger_int_type(rtype, ltype)
> > +			     && (ltype->ctype.modifiers & MOD_UNSIGNED)) ||
> > +			    (right_not && is_bigger_int_type(ltype, rtype)
> > +			     && (rtype->ctype.modifiers & MOD_UNSIGNED)))
> 
> You might consider wrapping the common expression here, along with the
> corresponding previous _not expression, into a function, and then
> calling it twice, flipping the arguments around for the second call.

Yes, that makes sense.
 
> > +				warning(expr->pos, "dubious: %sx %c %sy",
> > +				        left_not ? "~" : "",
> > +					op,
> > +					right_not ? "~" : "");
> 
> What happens here if left_not && right_not?  Should this warning still
> occur?  I *think* it still makes sense for it to, but the warning
> message might prove less informative.

You're right, the message wouldn't identify which was the operand that
was not being sign extended. I can pull the warning itself into the helper
function I create for the test.

> > +
> >  			ltype = usual_conversions(op, expr->left, expr->right,
> >  						  lclass, rclass, ltype, rtype);
> >  			ctype = rtype = ltype;

Thanks for your comments. A v2 will be forthcoming...

Cheers,
Phil

Re: [PATCH 1/3] sparse: Just use simple ints for decision variables

[Josh Triplett]

On Mon, Jun 09, 2014 at 02:58:00PM +0300, Phil Carmody wrote:
> The expressions are just ints, and const is pointess.

"bool" actually seems more appropriate here.  As for the const, it
does in fact hold true, as neither changes afte rdeclaration; why not
keep it?

> Signed-off-by: Phil Carmody <phil@dovecot.fi>
> ---
>  evaluate.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
> 
> diff --git a/evaluate.c b/evaluate.c
> index 6655615..9052962 100644
> --- a/evaluate.c
> +++ b/evaluate.c
> @@ -917,10 +917,10 @@ static struct symbol *evaluate_binop(struct expression *expr)
>  			rtype = integer_promotion(rtype);
>  		} else {
>  			// The rest do usual conversions
> -			const unsigned left_not  = expr->left->type == EXPR_PREOP
> -			                           && expr->left->op == '!';
> -			const unsigned right_not = expr->right->type == EXPR_PREOP
> -			                           && expr->right->op == '!';
> +			int left_not  = expr->left->type == EXPR_PREOP
> +					&& expr->left->op == '!';
> +			int right_not = expr->right->type == EXPR_PREOP
> +			                && expr->right->op == '!';
>  			if ((op == '&' || op == '|') && (left_not || right_not))
>  				warning(expr->pos, "dubious: %sx %c %sy",
>  				        left_not ? "!" : "",
> -- 
> 2.0.0
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCHv2 0/3] catch non-sign-extended '~' brainos

[Phil Carmody]

Bitwise-not is often used to create masks. Unfortunately implicit conversions
to longer types may leave the recipient with fewer set bit than he expected,
if he started with an unsigned type. It's nice to warn that such constructs
are dubious.

v2: cleaned up as per recommendations from Josh Triplett.

[PATCHv2 1/3] sparse: Just use simple ints for decision variables

[Phil Carmody]

The expressions are just ints, and const is pointess.

Signed-off-by: Phil Carmody <phil@dovecot.fi>
---
 evaluate.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/evaluate.c b/evaluate.c
index 6655615..9052962 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -917,10 +917,10 @@ static struct symbol *evaluate_binop(struct expression *expr)
 			rtype = integer_promotion(rtype);
 		} else {
 			// The rest do usual conversions
-			const unsigned left_not  = expr->left->type == EXPR_PREOP
-			                           && expr->left->op == '!';
-			const unsigned right_not = expr->right->type == EXPR_PREOP
-			                           && expr->right->op == '!';
+			int left_not  = expr->left->type == EXPR_PREOP
+					&& expr->left->op == '!';
+			int right_not = expr->right->type == EXPR_PREOP
+			                && expr->right->op == '!';
 			if ((op == '&' || op == '|') && (left_not || right_not))
 				warning(expr->pos, "dubious: %sx %c %sy",
 				        left_not ? "!" : "",
-- 
2.0.0

[PATCHv2 2/3] sparse: detect non-sign-extended masks created by '~'

[Phil Carmody]

Consider the operation of rounding up to the nearest multiple of a power of 2.
e.g.  #define ALLOC_SIZE(t) ((sizeof(t) + ASIZE - 1) & ~(ASIZE - 1))

If ASIZE is unfortunately defined as an unsigned type smaller than size_t,
then the ~ will not undergo sign-bit extension, and an incorrect mask will
be used. If used in a memory allocation context this could be fatal.

Warn about such dubious 'large op ~short' usage.

v2: pulled noisy repeated parts into a helper

Signed-off-by: Phil Carmody <phil@dovecot.fi>
---
 evaluate.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/evaluate.c b/evaluate.c
index 9052962..a16aa45 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -886,6 +886,25 @@ static struct symbol *evaluate_logical(struct expression *expr)
 	return &int_ctype;
 }
 
+static int int_size_cmp(struct symbol *left, struct symbol *right)
+{
+	left = integer_promotion(left);
+	right = integer_promotion(right);
+
+	return (left->bit_size > right->bit_size) ? 1 :
+		(right->bit_size > left->bit_size) ? -1 : 0;
+}
+
+static void check_masking(struct expression *expr, int op, int is_l,
+			  struct expression *sexpr, struct symbol *stype)
+{
+	if ((sexpr->type == EXPR_PREOP)
+	    && (sexpr->op == '~')
+	    && (stype->ctype.modifiers & MOD_UNSIGNED))
+		warning(expr->pos, "dubious zero-extended '~': %sx %c %sy",
+			"~"+!is_l, op, "~"+!!is_l);
+}
+
 static struct symbol *evaluate_binop(struct expression *expr)
 {
 	struct symbol *ltype, *rtype, *ctype;
@@ -917,6 +936,7 @@ static struct symbol *evaluate_binop(struct expression *expr)
 			rtype = integer_promotion(rtype);
 		} else {
 			// The rest do usual conversions
+			int size_cmp;
 			int left_not  = expr->left->type == EXPR_PREOP
 					&& expr->left->op == '!';
 			int right_not = expr->right->type == EXPR_PREOP
@@ -927,6 +947,12 @@ static struct symbol *evaluate_binop(struct expression *expr)
 					op,
 					right_not ? "!" : "");
 
+			size_cmp = int_size_cmp(ltype, rtype);
+			if (size_cmp > 0)
+				check_masking(expr, op, 0, expr->right, rtype);
+			else if (size_cmp < 0)
+				check_masking(expr, op, 1, expr->left, ltype);
+
 			ltype = usual_conversions(op, expr->left, expr->right,
 						  lclass, rclass, ltype, rtype);
 			ctype = rtype = ltype;
-- 
2.0.0

[PATCHv2 3/3] validation: dubious bitwise operations with bitwise nots

[Phil Carmody]

Add some bitwise not tests.

v2: add the double-twiddle case, and made less cryptic.

Signed-off-by: Phil Carmody <phil@dovecot.fi>
---
 validation/dubious-bitwise-with-not.c | 38 ++++++++++++++++++++++++++++++++++-
 1 file changed, 37 insertions(+), 1 deletion(-)

diff --git a/validation/dubious-bitwise-with-not.c b/validation/dubious-bitwise-with-not.c
index c48bcae..5e232b8 100644
--- a/validation/dubious-bitwise-with-not.c
+++ b/validation/dubious-bitwise-with-not.c
@@ -10,8 +10,34 @@ static unsigned int ok5  = !1 && !2;
 static unsigned int bad5 = !1 &  !2;
 static unsigned int ok6  = !1 || !2;
 static unsigned int bad6 = !1 |  !2;
+static unsigned long long ok7a  = 0x100000001ull & ~1;
+static unsigned long long ok7b  = 0x100000001ull & ~1ull;
+static unsigned long long bad7  = 0x100000001ull & ~1u;
+static unsigned long long ok8a  = ~1    & 0x100000001ull;
+static unsigned long long ok8b  = ~1ull & 0x100000001ull;
+static unsigned long long bad8  = ~1u   & 0x100000001ull;
+static unsigned long long ok9a  = 0x100000001ull | ~1;
+static unsigned long long ok9b  = 0x100000001ull | ~1ull;
+static unsigned long long bad9  = 0x100000001ull | ~1u;
+static unsigned long long ok10a = ~1    | 0x100000001ull;
+static unsigned long long ok10b = ~1ull | 0x100000001ull;
+static unsigned long long bad10 = ~1u   | 0x100000001ull;
+static unsigned long long ok11a = 0x100000001ull + ~1;
+static unsigned long long ok11b = 0x100000001ull + ~1ull;
+static unsigned long long bad11 = 0x100000001ull + ~1u;
+static unsigned long long ok12a = ~1    + 0x100000001ull;
+static unsigned long long ok12b = ~1ull + 0x100000001ull;
+static unsigned long long bad12 = ~1u   + 0x100000001ull;
+static unsigned long long ok13a = 0x100000001ull - ~1;
+static unsigned long long ok13b = 0x100000001ull - ~1ull;
+static unsigned long long bad13 = 0x100000001ull - ~1u;
+static unsigned long long ok14a = ~1    - 0x100000001ull;
+static unsigned long long ok14b = ~1ull - 0x100000001ull;
+static unsigned long long bad14 = ~1u   - 0x100000001ull;
+static unsigned long long bad15 = ~0x100000001ull ^ ~1u;
+static unsigned long long bad16 = ~1u   ^ ~0x100000001ull;
 /*
- * check-name: Dubious bitwise operation on !x
+ * check-name: Dubious bitwise operations with !x or ~x
  *
  * check-error-start
 dubious-bitwise-with-not.c:2:31: warning: dubious: !x & y
@@ -20,5 +46,15 @@ dubious-bitwise-with-not.c:6:31: warning: dubious: x & !y
 dubious-bitwise-with-not.c:8:31: warning: dubious: x | !y
 dubious-bitwise-with-not.c:10:31: warning: dubious: !x & !y
 dubious-bitwise-with-not.c:12:31: warning: dubious: !x | !y
+dubious-bitwise-with-not.c:15:50: warning: dubious zero-extended '~': x & ~y
+dubious-bitwise-with-not.c:18:41: warning: dubious zero-extended '~': ~x & y
+dubious-bitwise-with-not.c:21:50: warning: dubious zero-extended '~': x | ~y
+dubious-bitwise-with-not.c:24:41: warning: dubious zero-extended '~': ~x | y
+dubious-bitwise-with-not.c:27:50: warning: dubious zero-extended '~': x + ~y
+dubious-bitwise-with-not.c:30:41: warning: dubious zero-extended '~': ~x + y
+dubious-bitwise-with-not.c:33:50: warning: dubious zero-extended '~': x - ~y
+dubious-bitwise-with-not.c:36:41: warning: dubious zero-extended '~': ~x - y
+dubious-bitwise-with-not.c:37:51: warning: dubious zero-extended '~': x ^ ~y
+dubious-bitwise-with-not.c:38:41: warning: dubious zero-extended '~': ~x ^ y
  * check-error-end
  */
-- 
2.0.0

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Phil Carmody]

On Tue, Jun 10, 2014 at 10:54:04AM +0300, Phil Carmody wrote:
> Bitwise-not is often used to create masks. Unfortunately implicit conversions
> to longer types may leave the recipient with fewer set bit than he expected,
> if he started with an unsigned type. It's nice to warn that such constructs
> are dubious.
> 
> v2: cleaned up as per recommendations from Josh Triplett.

Any comments on these? 

Cheers,
Phil 

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Christopher Li]

On Fri, Jun 27, 2014 at 4:19 AM, Phil Carmody <phil@dovecot.fi> wrote:
>
> Any comments on these?
>

Sorry I am falling behind the patches, again.

I have been thinking about your patch for a few days.

It is very common to implicit cast up, do some binary operation
then cast back down.  e.g.


static unsigned long long val;
static unsigned int ok10  = val | ~1u;
static unsigned char a;
static unsigned char ok11  = val | ~a;


Your patch will give false positive warning about those.

Do you known how many new warning does it give on the new
kernel build after apply your patch? I suspect there is a lot of
false positive. I want to do that but haven't get around to it yet.
Hint hint...

To reduce the false positive, we can check the zero extended bits
survived to the final expression. e.g. the finial expression did
down cast again and lost those bits. I also want an option to
turn this warning off because the possible false positive.

Also, if you only care about warning against up cast "~" of
unsigned type, you can do the checking at cast_to().
It will be simpler. I have a sort patch like this, given that I
did not check for the "unsigned int" type, nor do I check for
binary op. You can still get the idea.

In this way, you don't need to predict the up cast will happen
or not. You can call when the implicit up cast actually happens.

It does not solve the problem of checking down cast  after up cast
of finial expression though.

Chris

diff --git a/evaluate.c b/evaluate.c
index 7ce8c55..47e660e 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -294,8 +294,11 @@ static struct expression * cast_to(struct
expression *old, struct symbol *type)
         */
        switch (old->type) {
        case EXPR_PREOP:
-               if (old->ctype->bit_size < type->bit_size)
+               if (old->ctype->bit_size < type->bit_size) {
+                       if (old->op == '~')
+                               warning(old->pos, "dubious zero-extended '~'");
                        break;
+               }
                if (old->op == '~') {
                        old->ctype = type;
                        old->unop = cast_to(old->unop, type);

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Phil Carmody]

On Fri, Jun 27, 2014 at 10:16:23AM -0700, Christopher Li wrote:
> On Fri, Jun 27, 2014 at 4:19 AM, Phil Carmody <phil@dovecot.fi> wrote:
> >
> > Any comments on these?
> >
> 
> Sorry I am falling behind the patches, again.
> 
> I have been thinking about your patch for a few days.
> 
> It is very common to implicit cast up, do some binary operation
> then cast back down.  e.g.
> 
> 
> static unsigned long long val;
> static unsigned int ok10  = val | ~1u;
> static unsigned char a;
> static unsigned char ok11  = val | ~a;
> 
> 
> Your patch will give false positive warning about those.

Good call.

> Do you known how many new warning does it give on the new
> kernel build after apply your patch? I suspect there is a lot of
> false positive. I want to do that but haven't get around to it yet.
> Hint hint...

It found some things that I had intended to patch. My memory's hazy
though, and there's no point in making wild guesses. I'll do a couple
of builds again, with my patch and with your patch, and compare the
output. My builds will be powerpc ones, so if anyone wants to do an
x86 build it wouldn't be wasted effort.

> To reduce the false positive, we can check the zero extended bits
> survived to the final expression. e.g. the finial expression did
> down cast again and lost those bits. I also want an option to
> turn this warning off because the possible false positive.

The latter would make sense, yes. It's not clear how to achieve the
former though. Either some context needs to be passed down, or a flag
needs to be passed back up. Either could be a bit invasive.

> Also, if you only care about warning against up cast "~" of
> unsigned type, you can do the checking at cast_to().
> It will be simpler. I have a sort patch like this, given that I
> did not check for the "unsigned int" type, nor do I check for
> binary op. You can still get the idea.

It needs to check for unsigned-ness in order to trap zero-extension, though.

> In this way, you don't need to predict the up cast will happen
> or not. You can call when the implicit up cast actually happens.

That probably makes more sense. I was just mimicking the previous 
dubious check.

Will report back in the next day or so what the kernel builds say.

Cheers,
Phil

> It does not solve the problem of checking down cast  after up cast
> of finial expression though.
> 
> Chris
> 
> diff --git a/evaluate.c b/evaluate.c
> index 7ce8c55..47e660e 100644
> --- a/evaluate.c
> +++ b/evaluate.c
> @@ -294,8 +294,11 @@ static struct expression * cast_to(struct
> expression *old, struct symbol *type)
>          */
>         switch (old->type) {
>         case EXPR_PREOP:
> -               if (old->ctype->bit_size < type->bit_size)
> +               if (old->ctype->bit_size < type->bit_size) {
> +                       if (old->op == '~')
> +                               warning(old->pos, "dubious zero-extended '~'");
>                         break;
> +               }
>                 if (old->op == '~') {
>                         old->ctype = type;
>                         old->unop = cast_to(old->unop, type);

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Christopher Li]

On Mon, Jun 30, 2014 at 9:44 AM, Christopher Li <sparse@chrisli.org> wrote:
> That give me 565 new warning. I attach the file here.
>
> I sample some, all the one I saw are false positive.

The real interesting question is, how many real kernel bug in that
565 warnings? It take some human effort to determine the warning
is false positive or not. If most of the warning are false positive, then
the warning is not usable.

Chris

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Phil Carmody]

On Mon, Jun 30, 2014 at 09:44:35AM -0700, Christopher Li wrote:
> On Mon, Jun 30, 2014 at 1:56 AM, Phil Carmody <phil@dovecot.fi> wrote:
> >> Also, if you only care about warning against up cast "~" of
> >> unsigned type, you can do the checking at cast_to().
> >> It will be simpler. I have a sort patch like this, given that I
> >> did not check for the "unsigned int" type, nor do I check for
> >> binary op. You can still get the idea.
> >
> > It needs to check for unsigned-ness in order to trap zero-extension, though.
> 
> That is right, it is not a complete patch. Just to show you some ideas.

With unsigned, it becomes a lot quieter, but still much noiser than my
original. (I have a v3 which excludes an idiom using '/'.)

> > Will report back in the next day or so what the kernel builds say.
> 
> I did some test against your patch.
> BTW, I just submit a patch for the kernel to save sparse warnings.
> Subject line starts with: [PATCH] sparse: Add CLOG ....
> 
> With that patch in kernel. Here is what I did in the testing:
> 
> $ make allmodconfig
> $ make -j8 C=2 CLOG=std
> 
> # apply your patch and make sparse
> 
> $ make -j8 C=2 CLOG=std-exp
> $ find -name ".*.std.sparse" | while read -r file; do diff -du $file
> ${file/std.sparse/std-exp.sparse} ; done > /tmp/signed-diff
> 
> $ grep "dubious zero" /tmp/signed-diff | wc -l
> 
> That give me 565 new warning. I attach the file here.
> 
> I sample some, all the one I saw are false positive.
> e.g.
> 
> static inline int nlmsg_msg_size(int payload)
> {
>     return NLMSG_HDRLEN + payload; <--------warn here
> }
> 
> /**
>  * nlmsg_total_size - length of netlink message including padding
>  * @payload: length of message payload
>  */
> static inline int nlmsg_total_size(int payload)
> {
>     return NLMSG_ALIGN(nlmsg_msg_size(payload));
> }
> 
> #define NLMSG_ALIGNTO    4U

I consider that, pedantically, to be worth fixing. alignments are defined
by the C standard to be of type size_t. It should either be ((size_t)4)
if you care about the precise type, or 4 if you don't, but not 4U. The 
'U' adds nothing apart from a way to create an incorrect mask.

Fixing that line removes ~110 out of the ~120 warnings in my powerpc build.

> #define NLMSG_ALIGN(len) ( ((len)+NLMSG_ALIGNTO-1) & ~(NLMSG_ALIGNTO-1) )
> #define NLMSG_HDRLEN     ((int) NLMSG_ALIGN(sizeof(struct nlmsghdr)))
> <------------ sizeof cast up the type
> #define NLMSG_LENGTH(len) ((len) + NLMSG_HDRLEN)

However, that's a good example of where the casting back down should shut
the warning up.

Thanks for the time you've put into this, Chris. I'll do a bit more 
head-scratching. I get the feeling that the zero-extend should taint the
expression, and that down-casts should clear that taint. The problem with
that is that you need to trap absolutely everywhere whate taint might
escape.

Phil

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Christopher Li]

On Tue, Jul 1, 2014 at 4:30 AM, Phil Carmody <phil@dovecot.fi> wrote:
>
> With unsigned, it becomes a lot quieter, but still much noiser than my
> original. (I have a v3 which excludes an idiom using '/'.)
>

Yes, because it cover more than just binary operations.
If you consider zero extend the unsigned type introducing error,
the binary operation just how you use the error bits.

>> #define NLMSG_ALIGNTO    4U
>
> I consider that, pedantically, to be worth fixing. alignments are defined
> by the C standard to be of type size_t. It should either be ((size_t)4)

((size_t)4) is hell ugly.


> if you care about the precise type, or 4 if you don't, but not 4U. The
> 'U' adds nothing apart from a way to create an incorrect mask.

That is debatable. Enforcing 4U vs 4 is annoying and buy you nothing
most of the case.

I don't consider alignment  being 4U as wrong by itself.  The key question
is how you use it.

if we introduce:

#define ALIGNMASK(align)   (size_t)(~((align) -1))

And we always use the macro to create mask from alignment value.
Then there is no need to enforce signedness of the var passed into the
macro. Hey, it might even read better.


Chris

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Phil Carmody]

On Tue, Jul 01, 2014 at 12:42:51PM -0700, Christopher Li wrote:
> On Tue, Jul 1, 2014 at 4:30 AM, Phil Carmody <phil@dovecot.fi> wrote:
> > With unsigned, it becomes a lot quieter, but still much noiser than my
> > original. (I have a v3 which excludes an idiom using '/'.)
> 
> Yes, because it cover more than just binary operations.
> If you consider zero extend the unsigned type introducing error,
> the binary operation just how you use the error bits.
> 
> >> #define NLMSG_ALIGNTO    4U
> >
> > I consider that, pedantically, to be worth fixing. alignments are defined
> > by the C standard to be of type size_t. It should either be ((size_t)4)
> 
> ((size_t)4) is hell ugly.

Do you care about the precise type of the value?
If you do, then it may be ugly, but it's pretty much obligatory.
And if you don't care about the precise type...

> > if you care about the precise type, or 4 if you don't, but not 4U. The
> > 'U' adds nothing apart from a way to create an incorrect mask.
> 
> That is debatable. Enforcing 4U vs 4 is annoying and buy you nothing
> most of the case.

What do you mean by "enforcing"? I consider persuading people to write
simpler, less breakable code to be a good thing.

> I don't consider alignment being 4U as wrong by itself. The key question
> is how you use it.

Absolutely. And doing a ~ and then an up-cast is using it dangerously.
Isn't that what sparse is supposed to be checking for?

> if we introduce:
> 
> #define ALIGNMASK(align)   (size_t)(~((align) -1))
> 
> And we always use the macro to create mask from alignment value.
> Then there is no need to enforce signedness of the var passed into the
> macro. Hey, it might even read better.

Put 4U in that, and it still has the flaw of creating a truncated mask.
Put 4 in and it doesn't.

Do you still want to defend 4U?

Phil

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Christopher Li]

On Wed, Jul 2, 2014 at 12:43 AM, Phil Carmody <phil@dovecot.fi> wrote:
>
> Do you care about the precise type of the value?
> If you do, then it may be ugly, but it's pretty much obligatory.
> And if you don't care about the precise type...

Yes, I make a mistake on my macro. But alignment can be
precise being unsigned. In a 32 bit system, what if I want to make
a 2G align memory? Your signed alignment will force to be a
negative value. Which is not precise.

>> I don't consider alignment being 4U as wrong by itself. The key question
>> is how you use it.
>
> Absolutely. And doing a ~ and then an up-cast is using it dangerously.
> Isn't that what sparse is supposed to be checking for?

Well, you still need to get the false positive rate down. Currently then
signal to noise ratio is too low. I would not recommend turning it on
by default. Did you find some real bug in that 500 error report? Real
bug I mean it produce actually bug on the object code it generated.

>
>> if we introduce:
>>
>> #define ALIGNMASK(align)   (size_t)(~((align) -1))
>>
>> And we always use the macro to create mask from alignment value.
>> Then there is no need to enforce signedness of the var passed into the
>> macro. Hey, it might even read better.
>
> Put 4U in that, and it still has the flaw of creating a truncated mask.
> Put 4 in and it doesn't.

Right, I make a mistake on that macro. Good catch.  How about

#define ALIGNMASK(align)   (~((size_t)((align) -1)))

Will you be happy if I use 4U with that macro?

My point is, with the right macro, you can still use 4U to create
alignment. We don't have to fight over 4U vs 4.

Chris

Re: [PATCHv2 0/3] catch non-sign-extended '~' brainos

[Phil Carmody]

On Wed, Jul 02, 2014 at 01:51:25AM -0700, Christopher Li wrote:
> On Wed, Jul 2, 2014 at 12:43 AM, Phil Carmody <phil@dovecot.fi> wrote:
> >
> > Do you care about the precise type of the value?
> > If you do, then it may be ugly, but it's pretty much obligatory.
> > And if you don't care about the precise type...
> 
> Yes, I make a mistake on my macro. But alignment can be
> precise being unsigned. In a 32 bit system, what if I want to make
> a 2G align memory? Your signed alignment will force to be a
> negative value. Which is not precise.

You always have the option of an explicit size_t in that case.

> >> I don't consider alignment being 4U as wrong by itself. The key question
> >> is how you use it.
> >
> > Absolutely. And doing a ~ and then an up-cast is using it dangerously.
> > Isn't that what sparse is supposed to be checking for?
> 
> Well, you still need to get the false positive rate down. Currently then
> signal to noise ratio is too low. I would not recommend turning it on
> by default. Did you find some real bug in that 500 error report? Real
> bug I mean it produce actually bug on the object code it generated.

I'd like to say I found a real bug in an different open source package
with that check enabled. However, that's not true; I wrote that check
because I was perturbed that sparse hadn't found the bug which I'd just 
had to debug manually. So yes, it can catch real world issues.

It's much more likely to find issues in userspace programs, where there's
more likelyhood of wanting to allocate blocks of memory larger than 4G,
of course.

> >> if we introduce:
> >>
> >> #define ALIGNMASK(align)   (size_t)(~((align) -1))
> >>
> >> And we always use the macro to create mask from alignment value.
> >> Then there is no need to enforce signedness of the var passed into the
> >> macro. Hey, it might even read better.
> >
> > Put 4U in that, and it still has the flaw of creating a truncated mask.
> > Put 4 in and it doesn't.
> 
> Right, I make a mistake on that macro. Good catch.  How about
> 
> #define ALIGNMASK(align)   (~((size_t)((align) -1)))
> 
> Will you be happy if I use 4U with that macro?

Indeed. However, if the only use of the 4U is when it is expanded
into the expression (size_t)((4U) -1), then what was the 'U' again?
It still seems like a cargo cult artefact.

> My point is, with the right macro, you can still use 4U to create
> alignment. We don't have to fight over 4U vs 4.

Agreed. And how do you know if you've got the right macro?
It's on that question that I'd like sparse to step in and help.

Phil