From 8f3cb0e19f0955e6eb0538d8057fa9a16187db01 Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Wed, 29 Mar 2017 11:58:33 +0300 Subject: [PATCH] extra: handle MOD conditions like "if (a % 4) {" better We're basically dorking around the minimum and maximum limits here. If the start range is not known then we give up. In other words: if (i == 0 || !(i % 4)) { is handled differently from the same condition: if (!(i % 4) || i == 0) { Because the starting minimum condition is 1 in the first example and 0 in the second. That's fine, because this patch is better than doing nothing and there is some kind of limit to the smatch_extra approach to tracking values because you can only express so many values. Smatch is about being practical more than being 100% perfect. So many things are handled as special cases. Doing "foo % 4" is way more common than doing "foo % 5" and I plan to handle that later by tracking set and cleared bits better. Another idea would be to track all the true conditions at any given time so you could say "if idx is 100 then were out of bounds." then you could verify that all the conditions were still possibly true. The point is that this isn't perfect but maybe there will be ways later to get the other information that we want. Signed-off-by: Dan Carpenter --- smatch_extra.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++ validation/sm_mod.c | 38 ++++++++++++++++++++++++++++++ 2 files changed, 104 insertions(+) create mode 100644 validation/sm_mod.c diff --git a/smatch_extra.c b/smatch_extra.c index b5fc720a..9819c541 100644 --- a/smatch_extra.c +++ b/smatch_extra.c @@ -1683,6 +1683,70 @@ static void handle_AND_condition(struct expression *expr) } } +static void handle_MOD_condition(struct expression *expr) +{ + struct range_list *orig_rl; + struct range_list *true_rl; + struct range_list *false_rl = NULL; + sval_t right; + sval_t zero = { + .value = 0, + }; + + if (!get_implied_value(expr->right, &right) || right.value == 0) + return; + get_absolute_rl(expr->left, &orig_rl); + + zero.type = rl_type(orig_rl); + + /* We're basically dorking around the min and max here */ + true_rl = remove_range(orig_rl, zero, zero); + if (!sval_is_max(rl_max(true_rl)) && + !(rl_max(true_rl).value % right.value)) + true_rl = remove_range(true_rl, rl_max(true_rl), rl_max(true_rl)); + + if (rl_equiv(true_rl, orig_rl)) + true_rl = NULL; + + if (sval_is_positive(rl_min(orig_rl)) && + (rl_max(orig_rl).value - rl_min(orig_rl).value) / right.value < 5) { + sval_t add; + int i; + + add = rl_min(orig_rl); + add.value += right.value - (add.value % right.value); + add.value -= right.value; + + for (i = 0; i < 5; i++) { + add.value += right.value; + if (add.value > rl_max(orig_rl).value) + break; + add_range(&false_rl, add, add); + } + } else { + if (rl_min(orig_rl).uvalue != 0 && + rl_min(orig_rl).uvalue < right.uvalue) { + sval_t chop = right; + chop.value--; + false_rl = remove_range(orig_rl, zero, chop); + } + + if (!sval_is_max(rl_max(orig_rl)) && + (rl_max(orig_rl).value % right.value)) { + sval_t chop = rl_max(orig_rl); + chop.value -= chop.value % right.value; + chop.value++; + if (!false_rl) + false_rl = clone_rl(orig_rl); + false_rl = remove_range(false_rl, chop, rl_max(orig_rl)); + } + } + + set_extra_expr_true_false(expr->left, + true_rl ? alloc_estate_rl(true_rl) : NULL, + false_rl ? alloc_estate_rl(false_rl) : NULL); +} + /* this is actually hooked from smatch_implied.c... it's hacky, yes */ void __extra_match_condition(struct expression *expr) { @@ -1721,6 +1785,8 @@ void __extra_match_condition(struct expression *expr) case EXPR_BINOP: if (expr->op == '&') handle_AND_condition(expr); + if (expr->op == '%') + handle_MOD_condition(expr); return; } } diff --git a/validation/sm_mod.c b/validation/sm_mod.c new file mode 100644 index 00000000..3c5df3d6 --- /dev/null +++ b/validation/sm_mod.c @@ -0,0 +1,38 @@ +#include "check_debug.h" + +int a, b; + +int frob(int size) +{ + if (a <= 0 || a > 10) + return; + if (a % 4) { + __smatch_implied(a); + } else { + __smatch_implied(a); + } + + if (b <= 0 || b > 100) + return; + if (b % 4) { + __smatch_implied(b); + } else { + __smatch_implied(b); + } + + + + return 0; +} + +/* + * check-name: smatch mod condition + * check-command: smatch -I.. sm_mod.c + * + * check-output-start +sm_mod.c:10 frob() implied: a = '1-10' +sm_mod.c:12 frob() implied: a = '4,8' +sm_mod.c:18 frob() implied: b = '1-99' +sm_mod.c:20 frob() implied: b = '4-100' + * check-output-end + */ -- 2.11.4.GIT