| Message ID | 20190302121605.23372-1-thomas@t-8ch.de (mailing list archive) |
|---|---|
| State | Mainlined, archived |
| Headers | show |
| Series | Simplify shift operations on constants | expand |
On Sat, Mar 2, 2019 at 4:16 AM Thomas Weißschuh <thomas@t-8ch.de> wrote: > > The result of a shift operation on a constants by a constant value is > also constant. Yes it is, and sparse used to get this right. This was actually broken by commit 0b73dee0 ("big-shift: move the check into check_shift_count()") which clearly _intended_ to do no harm, but which was completely broken. The if (conservative) return 0; test makes no sense at all. Your patch "fixed" it by limiting it to a non-constant value, but that doesn't actually fix anything in reality, it just hides the broken check (and it will also hide the warning from check_shift_count(). The code *used* to do if (r >= ctype->bit_size) { if (conservative) return 0; ... ie it would *not* simplify expressions where the shift size was equal to or larger than the type size. Which is correct. But then the check against the type size was moved into the "check_shift_count()" function, and now the "if (conservative)" test makes no sense what-so-ever any more. I think a better patch for expand.c would be something like the attached, that fixes the logic mistake, and moves the "conservative" check too into check_shift_count(). NOTE! This is entirely untested, and I think all credit for the patch should go to Thomas who write a test-case and a changelog. I just think the expand.c part should be made to make sense. Thanks, Linus expand.c | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) diff --git a/expand.c b/expand.c index e8e50b08..95f9fda6 100644 --- a/expand.c +++ b/expand.c @@ -158,19 +158,14 @@ Float: expr->type = EXPR_FVALUE; } -static void check_shift_count(struct expression *expr, struct expression *right) +static void warn_shift_count(struct expression *expr, struct symbol *ctype, long long count) { - struct symbol *ctype = expr->ctype; - long long count = get_longlong(right); - if (count < 0) { if (!Wshift_count_negative) return; warning(expr->pos, "shift count is negative (%lld)", count); return; } - if (count < ctype->bit_size) - return; if (ctype->type == SYM_NODE) ctype = ctype->ctype.base_type; @@ -179,6 +174,19 @@ static void check_shift_count(struct expression *expr, struct expression *right) warning(expr->pos, "shift too big (%llu) for type %s", count, show_typename(ctype)); } +/* Return true if constant shift size is valid */ +static bool check_shift_count(struct expression *expr, struct expression *right) +{ + struct symbol *ctype = expr->ctype; + long long count = get_longlong(right); + + if (count >= 0 && count < ctype->bit_size) + return true; + if (!conservative) + warn_shift_count(expr, ctype, count); + return false; +} + /* * CAREFUL! We need to get the size and sign of the * result right! @@ -197,9 +205,8 @@ 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 (conservative) + if (!check_shift_count(expr, right)) return 0; - check_shift_count(expr, right); } if (left->type != EXPR_VALUE) return 0;
On Sat, Mar 02, 2019 at 08:26:36AM -0800, Linus Torvalds wrote: > On Sat, Mar 2, 2019 at 4:16 AM Thomas Weißschuh <thomas@t-8ch.de> wrote: > > > > The result of a shift operation on a constants by a constant value is > > also constant. > > Yes it is, and sparse used to get this right. > > This was actually broken by commit 0b73dee0 ("big-shift: move the > check into check_shift_count()") which clearly _intended_ to do no > harm, but which was completely broken. > > The > > if (conservative) > return 0; > > test makes no sense at all. Your patch "fixed" it by limiting it to a > non-constant value, but that doesn't actually fix anything in reality, > it just hides the broken check (and it will also hide the warning from > check_shift_count(). > > The code *used* to do > > if (r >= ctype->bit_size) { > if (conservative) > return 0; > ... > > ie it would *not* simplify expressions where the shift size was equal > to or larger than the type size. Which is correct. But then the check > against the type size was moved into the "check_shift_count()" > function, and now the "if (conservative)" test makes no sense > what-so-ever any more. Yes, indeed. Mea culpa. > I think a better patch for expand.c would be something like the > attached, that fixes the logic mistake, and moves the "conservative" > check too into check_shift_count(). I just sent a smaller fix (but with duplicated test for the size) but yes, separating the check from the warn is much better. > NOTE! This is entirely untested, and I think all credit for the patch > should go to Thomas who write a test-case and a changelog. and found the problem. Sure. -- Luc
On Sat, 2019-03-02T18:38+0100, Luc Van Oostenryck wrote: > On Sat, Mar 02, 2019 at 08:26:36AM -0800, Linus Torvalds wrote: >> On Sat, Mar 2, 2019 at 4:16 AM Thomas Weißschuh <thomas@t-8ch.de> wrote: >>> >>> The result of a shift operation on a constants by a constant value is >>> also constant. >> >> Yes it is, and sparse used to get this right. >> >> This was actually broken by commit 0b73dee0 ("big-shift: move the >> check into check_shift_count()") which clearly _intended_ to do no >> harm, but which was completely broken. >> >> [..] > > Yes, indeed. Mea culpa. > >> I think a better patch for expand.c would be something like the >> attached, that fixes the logic mistake, and moves the "conservative" >> check too into check_shift_count(). > > I just sent a smaller fix (but with duplicated test for the size) > but yes, separating the check from the warn is much better. I'm actually not sure how to proceed. Should I integrate Linus' fix, your description and my test and resend them, or do you want to do it? >> NOTE! This is entirely untested, and I think all credit for the patch >> should go to Thomas who write a test-case and a changelog. > > and found the problem. Sure. Thanks! Thomas
On Sat, Mar 02, 2019 at 11:34:15PM +0100, Thomas Weißschuh wrote: > > I'm actually not sure how to proceed. > Should I integrate Linus' fix, your description and my test and resend them, or > do you want to do it? It's fine, thanks. I've taken Linus' version, adapted my description, renamed you test and added another test. I'm proposing to push the patch here under. Thanks -- Luc From 83cfb92761f4602bc08aa4be6fd9834a3b98d5e3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Thomas=20Wei=C3=9Fschuh?= <thomas@t-8ch.de> Date: Sat, 2 Mar 2019 13:16:05 +0100 Subject: [PATCH v2] expand: 'conservative' must not bypass valid simplifications MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit During the expansion of shifts, the variable 'conservative' is used to inhibit any possible diagnostics (for example, because he needed information is if the expression is a constant or not). However, this must not inhibit the simplification of valid shift expressions. Unfortunately, by moving the validation inside check_shift_count(), this what was done by commit 0b73dee01 ("big-shift: move the check into check_shift_count()"). Found through a false positive VLA detected in the Linux kernel. The array size was computed through min() on a shifted constant value and sparse complained about it. Fix this by changing the logic of check_shift_count(): 1) moving the test of 'conservative' inside check_shift_count() and only issuing warnings if set. 2) moving the warning part in a separate function: warn_shift_count() 3) let check_shift_count() return if the shift count is valid so that the simplication can be eluded if not. Fixes: 0b73dee0171a15800d0a4ae6225b602bf8961599 Signed-off-by: Thomas Weißschuh <thomas@t-8ch.de> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- expand.c | 23 ++++++++----- validation/constexpr-shift.c | 12 +++++++ validation/expand/bad-shift.c | 64 +++++++++++++++++++++++++++++++++++ 3 files changed, 91 insertions(+), 8 deletions(-) create mode 100644 validation/constexpr-shift.c create mode 100644 validation/expand/bad-shift.c diff --git a/expand.c b/expand.c index e8e50b080..95f9fda63 100644 --- a/expand.c +++ b/expand.c @@ -158,19 +158,14 @@ Float: expr->type = EXPR_FVALUE; } -static void check_shift_count(struct expression *expr, struct expression *right) +static void warn_shift_count(struct expression *expr, struct symbol *ctype, long long count) { - struct symbol *ctype = expr->ctype; - long long count = get_longlong(right); - if (count < 0) { if (!Wshift_count_negative) return; warning(expr->pos, "shift count is negative (%lld)", count); return; } - if (count < ctype->bit_size) - return; if (ctype->type == SYM_NODE) ctype = ctype->ctype.base_type; @@ -179,6 +174,19 @@ static void check_shift_count(struct expression *expr, struct expression *right) warning(expr->pos, "shift too big (%llu) for type %s", count, show_typename(ctype)); } +/* Return true if constant shift size is valid */ +static bool check_shift_count(struct expression *expr, struct expression *right) +{ + struct symbol *ctype = expr->ctype; + long long count = get_longlong(right); + + if (count >= 0 && count < ctype->bit_size) + return true; + if (!conservative) + warn_shift_count(expr, ctype, count); + return false; +} + /* * CAREFUL! We need to get the size and sign of the * result right! @@ -197,9 +205,8 @@ 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 (conservative) + if (!check_shift_count(expr, right)) return 0; - check_shift_count(expr, right); } if (left->type != EXPR_VALUE) return 0; diff --git a/validation/constexpr-shift.c b/validation/constexpr-shift.c new file mode 100644 index 000000000..df01b74e8 --- /dev/null +++ b/validation/constexpr-shift.c @@ -0,0 +1,12 @@ +#define __is_constexpr(x) \ + (sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8))) + +static void test(int x) { + static int b[] = { + [__builtin_choose_expr(__is_constexpr(1 << 1), 1, x)] = 0, + }; +} + +/* + * check-name: constexpr-shift + */ diff --git a/validation/expand/bad-shift.c b/validation/expand/bad-shift.c new file mode 100644 index 000000000..22c4341f1 --- /dev/null +++ b/validation/expand/bad-shift.c @@ -0,0 +1,64 @@ +#define MAX (sizeof(int) * __CHAR_BIT__) + +static int lmax(int a) +{ + return 1 << MAX; +} + +static int lneg(int a) +{ + return 1 << -1; +} + +static int rmax(int a) +{ + return 1 >> MAX; +} + +static int rneg(int a) +{ + return 1 >> -1; +} + +/* + * check-name: bad-shift + * check-command: test-linearize -Wno-decl $file + * + * check-output-start +lmax: +.L0: + <entry-point> + shl.32 %r1 <- $1, $32 + ret.32 %r1 + + +lneg: +.L2: + <entry-point> + shl.32 %r3 <- $1, $0xffffffff + ret.32 %r3 + + +rmax: +.L4: + <entry-point> + asr.32 %r5 <- $1, $32 + ret.32 %r5 + + +rneg: +.L6: + <entry-point> + asr.32 %r7 <- $1, $0xffffffff + ret.32 %r7 + + + * check-output-end + * + * check-error-start +expand/bad-shift.c:5:18: warning: shift too big (32) for type int +expand/bad-shift.c:10:18: warning: shift count is negative (-1) +expand/bad-shift.c:15:18: warning: shift too big (32) for type int +expand/bad-shift.c:20:18: warning: shift count is negative (-1) + * check-error-end + */
On Sun, 2019-03-03T00:20+0100, Luc Van Oostenryck wrote: > On Sat, Mar 02, 2019 at 11:34:15PM +0100, Thomas Weißschuh wrote: > > > > I'm actually not sure how to proceed. > > Should I integrate Linus' fix, your description and my test and resend them, or > > do you want to do it? > > It's fine, thanks. I've taken Linus' version, adapted my description, > renamed you test and added another test. I'm proposing to push the > patch here under. Thanks! Sounds good to me. (A few minor notes below). Thomas > From 83cfb92761f4602bc08aa4be6fd9834a3b98d5e3 Mon Sep 17 00:00:00 2001 > > During the expansion of shifts, the variable 'conservative' is used > to inhibit any possible diagnostics (for example, because he needed Typo: ^^ the > information is if the expression is a constant or not). The explanation about 'conservative' would be nice as a comment in the source. I misunderstood its meaning before. (Probably because I looked at the place where it was used to actually change behaviour) > --- > expand.c | 23 ++++++++----- > validation/constexpr-shift.c | 12 +++++++ > validation/expand/bad-shift.c | 64 +++++++++++++++++++++++++++++++++++ > 3 files changed, 91 insertions(+), 8 deletions(-) > create mode 100644 validation/constexpr-shift.c > create mode 100644 validation/expand/bad-shift.c > > diff --git a/expand.c b/expand.c > index e8e50b080..95f9fda63 100644 > --- a/expand.c > +++ b/expand.c > @@ -158,19 +158,14 @@ Float: > expr->type = EXPR_FVALUE; > } > > -static void check_shift_count(struct expression *expr, struct expression *right) > +static void warn_shift_count(struct expression *expr, struct symbol *ctype, long long count) The 'struct symbol *ctype' could be 'const', after adapting the signatures of the functions called with it. If you want I can send a patch after this went in. > { > - struct symbol *ctype = expr->ctype; > - long long count = get_longlong(right); > - > if (count < 0) { > if (!Wshift_count_negative) > return; > warning(expr->pos, "shift count is negative (%lld)", count); > return; > } > - if (count < ctype->bit_size) > - return; > if (ctype->type == SYM_NODE) > ctype = ctype->ctype.base_type;
On Sun, Mar 03, 2019 at 10:10:45AM +0100, Thomas Weißschuh wrote: > On Sun, 2019-03-03T00:20+0100, Luc Van Oostenryck wrote: > > It's fine, thanks. I've taken Linus' version, adapted my description, > > renamed you test and added another test. I'm proposing to push the > > patch here under. > > Thanks! Sounds good to me. > > (A few minor notes below). > > Thomas > > > From 83cfb92761f4602bc08aa4be6fd9834a3b98d5e3 Mon Sep 17 00:00:00 2001 > > > > During the expansion of shifts, the variable 'conservative' is used > > to inhibit any possible diagnostics (for example, because he needed > Typo: ^^ the Yes, thanks. > > information is if the expression is a constant or not). > > The explanation about 'conservative' would be nice as a comment in the source. > I misunderstood its meaning before. > (Probably because I looked at the place where it was used to actually change > behaviour) You're right. It's far from obvious. See the patch here under. > > > > -static void check_shift_count(struct expression *expr, struct expression *right) > > +static void warn_shift_count(struct expression *expr, struct symbol *ctype, long long count) > > The 'struct symbol *ctype' could be 'const', after adapting the signatures of > the functions called with it. > If you want I can send a patch after this went in. Yes, sure. Best regards, -- Luc From 7fd3778e2d3a7b17aefea66819bf07feb7a257d3 Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> Date: Sun, 3 Mar 2019 10:59:40 +0100 Subject: [PATCH] expand: add explanation to 'conservative' MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The variable 'conservative' is used to allow testing some characteristics of an expression while inhibiting any possible side-efects like issuing a warning or marking the expression as erroneous. But this role is not immedialtely apparent. So, add a comment to the variable declaration. Suggested-by: Thomas Weißschuh <thomas@t-8ch.de> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- expand.c | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/expand.c b/expand.c index 95f9fda63..455d5baef 100644 --- a/expand.c +++ b/expand.c @@ -47,6 +47,11 @@ static int expand_expression(struct expression *); static int expand_statement(struct statement *); + +// If set, don't issue a warning on divide-by-0, invalid shift, ... +// and don't mark the expression as erroneous but leave it as-is. +// This allows testing some characteristics of the expression +// without creating any side-effects (e.g.: is_zero_constant()). static int conservative; static int expand_symbol_expression(struct expression *expr)
diff --git a/expand.c b/expand.c index e8e50b0..7936e29 100644 --- a/expand.c +++ b/expand.c @@ -197,7 +197,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 (conservative) + if (conservative && left->type != EXPR_VALUE) return 0; check_shift_count(expr, right); } diff --git a/validation/simplify-binops.c b/validation/simplify-binops.c new file mode 100644 index 0000000..e464c37 --- /dev/null +++ b/validation/simplify-binops.c @@ -0,0 +1,12 @@ +#define __is_constexpr(x) \ + (sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8))) + +static void test(int x) { + static int b[] = { + [__builtin_choose_expr(__is_constexpr(1 << 1), 1, x)] = 0, + }; +} + +/* + * check-name: simplify-binops + */
The result of a shift operation on a constants by a constant value is also constant. Found through a false positive VLA detected in the Linux kernel. The array size was computed through min() on a shifted constant value and sparse complained about it. Signed-off-by: Thomas Weißschuh <thomas@t-8ch.de> --- expand.c | 2 +- validation/simplify-binops.c | 12 ++++++++++++ 2 files changed, 13 insertions(+), 1 deletion(-) create mode 100644 validation/simplify-binops.c