check_signed.c

   1 /*
   2  * Copyright (C) 2009 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /*
  19  * Check for things which are signed but probably should be unsigned.
  20  *
  21  * Hm...  It seems like at this point in the processing, sparse makes all
  22  * bitfields unsigned.  Which is logical but not what GCC does.
  23  *
  24  */
  25
  26 #include "smatch.h"
  27 #include "smatch_extra.h"
  28
  29 static int my_id;
  30
  31 #define VAR_ON_RIGHT 0
  32 #define VAR_ON_LEFT 1
  33
  34 static void match_assign(struct expression *expr)
  35 {
  36         struct symbol *sym;
  37         sval_t sval;
  38         sval_t max;
  39         sval_t min;
  40         char *left_name, *right_name;
  41
  42         if (__in_fake_assign)
  43                 return;
  44         if (is_fake_var_assign(expr))
  45                 return;
  46         if (expr->op == SPECIAL_AND_ASSIGN || expr->op == SPECIAL_OR_ASSIGN)
  47                 return;
  48
  49         sym = get_type(expr->left);
  50         if (!sym || sym->type != SYM_BASETYPE) {
  51                 //sm_msg("could not get type");
  52                 return;
  53         }
  54         if (type_bits(sym) < 0 || type_bits(sym) >= 32) /* max_val limits this */
  55                 return;
  56         if (!get_implied_value(expr->right, &sval))
  57                 return;
  58         max = sval_type_max(sym);
  59         if (sym != &bool_ctype && sym != &uchar_ctype &&
  60             sval_cmp(max, sval) < 0 &&
  61             !(sval.value < 256 && max.value == 127)) {
  62                 left_name = expr_to_str(expr->left);
  63                 right_name = expr_to_str(expr->right);
  64                 sm_warning("'%s' %s can't fit into %s '%s'",
  65                        right_name, sval_to_numstr(sval), sval_to_numstr(max), left_name);
  66                 free_string(left_name);
  67         }
  68         min = sval_type_min(sym);
  69         if (sval_cmp_t(&llong_ctype, min, sval) > 0) {
  70                 if (min.value == 0 && sval.value == -1) /* assigning -1 to unsigned variables is idiomatic */
  71                         return;
  72                 if (expr->right->type == EXPR_PREOP && expr->right->op == '~')
  73                         return;
  74                 if (expr->op == SPECIAL_SUB_ASSIGN || expr->op == SPECIAL_ADD_ASSIGN)
  75                         return;
  76                 if (sval_positive_bits(sval) == 7)
  77                         return;
  78                 left_name = expr_to_str(expr->left);
  79                 if (min.value == 0) {
  80                         sm_warning("assigning %s to unsigned variable '%s'",
  81                                sval_to_str(sval), left_name);
  82                 } else {
  83                         sm_warning("value %s can't fit into %s '%s'",
  84                                sval_to_str(sval), sval_to_str(min), left_name);
  85                 }
  86                 free_string(left_name);
  87         }
  88 }
  89
  90 static int cap_gt_zero_and_lt(struct expression *expr)
  91 {
  92
  93         struct expression *var = expr->left;
  94         struct expression *tmp;
  95         char *name1 = NULL;
  96         char *name2 = NULL;
  97         sval_t known;
  98         int ret = 0;
  99         int i;
 100
 101         if (!get_value(expr->right, &known) || known.value != 0)
 102                 return 0;
 103
 104         i = 0;
 105         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 106                 if (!i++)
 107                         continue;
 108                 if (tmp->op == SPECIAL_LOGICAL_AND) {
 109                         struct expression *right = strip_expr(tmp->right);
 110
 111                         if (right->op != '<' &&
 112                             right->op != SPECIAL_UNSIGNED_LT &&
 113                             right->op != SPECIAL_LTE &&
 114                             right->op != SPECIAL_UNSIGNED_LTE)
 115                                 return 0;
 116
 117                         name1 = expr_to_str(var);
 118                         if (!name1)
 119                                 goto free;
 120
 121                         name2 = expr_to_str(right->left);
 122                         if (!name2)
 123                                 goto free;
 124                         if (!strcmp(name1, name2))
 125                                 ret = 1;
 126                         goto free;
 127
 128                 }
 129                 return 0;
 130         } END_FOR_EACH_PTR_REVERSE(tmp);
 131
 132 free:
 133         free_string(name1);
 134         free_string(name2);
 135         return ret;
 136 }
 137
 138 static int cap_lt_zero_or_gt(struct expression *expr)
 139 {
 140
 141         struct expression *var = expr->left;
 142         struct expression *tmp;
 143         char *name1 = NULL;
 144         char *name2 = NULL;
 145         sval_t known;
 146         int ret = 0;
 147         int i;
 148
 149         if (!get_value(expr->right, &known) || known.value != 0)
 150                 return 0;
 151
 152         i = 0;
 153         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 154                 if (!i++)
 155                         continue;
 156                 if (tmp->op == SPECIAL_LOGICAL_OR) {
 157                         struct expression *right = strip_expr(tmp->right);
 158
 159                         if (right->op != '>' &&
 160                             right->op != SPECIAL_UNSIGNED_GT &&
 161                             right->op != SPECIAL_GTE &&
 162                             right->op != SPECIAL_UNSIGNED_GTE)
 163                                 return 0;
 164
 165                         name1 = expr_to_str(var);
 166                         if (!name1)
 167                                 goto free;
 168
 169                         name2 = expr_to_str(right->left);
 170                         if (!name2)
 171                                 goto free;
 172                         if (!strcmp(name1, name2))
 173                                 ret = 1;
 174                         goto free;
 175
 176                 }
 177                 return 0;
 178         } END_FOR_EACH_PTR_REVERSE(tmp);
 179
 180 free:
 181         free_string(name1);
 182         free_string(name2);
 183         return ret;
 184 }
 185
 186 static int cap_both_sides(struct expression *expr)
 187 {
 188         switch (expr->op) {
 189         case '<':
 190         case SPECIAL_UNSIGNED_LT:
 191         case SPECIAL_LTE:
 192         case SPECIAL_UNSIGNED_LTE:
 193                 return cap_lt_zero_or_gt(expr);
 194         case '>':
 195         case SPECIAL_UNSIGNED_GT:
 196         case SPECIAL_GTE:
 197         case SPECIAL_UNSIGNED_GTE:
 198                 return cap_gt_zero_and_lt(expr);
 199         }
 200         return 0;
 201 }
 202
 203 static int compare_against_macro(struct expression *expr)
 204 {
 205         sval_t known;
 206
 207         if (expr->op != SPECIAL_UNSIGNED_LT)
 208                 return 0;
 209
 210         if (!get_value(expr->right, &known) || known.value != 0)
 211                 return 0;
 212         return !!get_macro_name(expr->right->pos);
 213 }
 214
 215 static int print_unsigned_never_less_than_zero(struct expression *expr)
 216 {
 217         sval_t known;
 218         char *name;
 219
 220         if (expr->op != SPECIAL_UNSIGNED_LT)
 221                 return 0;
 222
 223         if (!get_value(expr->right, &known) || known.value != 0)
 224                 return 0;
 225
 226         name = expr_to_str(expr->left);
 227         sm_warning("unsigned '%s' is never less than zero.", name);
 228         free_string(name);
 229         return 1;
 230 }
 231
 232 static bool check_is_ulong_max_recursive(struct expression *expr)
 233 {
 234         sval_t sval;
 235
 236         expr = strip_expr(expr);
 237
 238         if (!get_value(expr, &sval))
 239                 return false;
 240
 241         if (expr->type == EXPR_BINOP) {
 242                 if (check_is_ulong_max_recursive(expr->left))
 243                         return true;
 244                 return false;
 245         }
 246
 247         if (sval_cmp(sval, sval_type_max(&ulong_ctype)) == 0)
 248                 return true;
 249         return false;
 250 }
 251
 252 static bool is_u64_vs_ulongmax(struct expression *expr)
 253 {
 254         struct symbol *left, *right;
 255
 256         if (expr->op != '>' && expr->op != SPECIAL_UNSIGNED_GT)
 257                 return false;
 258         if (!check_is_ulong_max_recursive(expr->right))
 259                 return false;
 260
 261         left = get_type(expr->left);
 262         right = get_type(expr->right);
 263
 264         if (left == right)
 265                 return true;
 266         if (type_positive_bits(left) < type_positive_bits(right))
 267                 return true;
 268
 269         if (type_bits(left) != 64)
 270                 return false;
 271         if (right != &ulong_ctype && right != &uint_ctype)
 272                 return false;
 273
 274         return true;
 275 }
 276
 277 static void match_condition(struct expression *expr)
 278 {
 279         struct symbol *type;
 280         sval_t known;
 281         sval_t min, max;
 282         struct range_list *rl_left_orig, *rl_right_orig;
 283         struct range_list *rl_left, *rl_right;
 284
 285         if (expr->type != EXPR_COMPARE)
 286                 return;
 287
 288         type = get_type(expr);
 289         if (!type)
 290                 return;
 291
 292         /* screw it.  I am writing this to mark yoda code as buggy.
 293          * Valid comparisons between an unsigned and zero are:
 294          * 1) inside a macro.
 295          * 2) foo < LOWER_BOUND where LOWER_BOUND is a macro.
 296          * 3) foo < 0 || foo > X in exactly this format.  No Yoda.
 297          * 4) foo >= 0 && foo < X
 298          */
 299         if (get_macro_name(expr->pos))
 300                 return;
 301         if (compare_against_macro(expr))
 302                 return;
 303         if (cap_both_sides(expr))
 304                 return;
 305
 306         /* This is a special case for the common error */
 307         if (print_unsigned_never_less_than_zero(expr))
 308                 return;
 309
 310         /* check that one and only one side is known */
 311         if (get_value(expr->left, &known)) {
 312                 if (get_value(expr->right, &known))
 313                         return;
 314                 rl_left_orig = alloc_rl(known, known);
 315                 rl_left = cast_rl(type, rl_left_orig);
 316
 317                 min = sval_type_min(get_type(expr->right));
 318                 max = sval_type_max(get_type(expr->right));
 319                 rl_right_orig = alloc_rl(min, max);
 320                 rl_right = cast_rl(type, rl_right_orig);
 321         } else if (get_value(expr->right, &known)) {
 322                 rl_right_orig = alloc_rl(known, known);
 323                 rl_right = cast_rl(type, rl_right_orig);
 324
 325                 min = sval_type_min(get_type(expr->left));
 326                 max = sval_type_max(get_type(expr->left));
 327                 rl_left_orig = alloc_rl(min, max);
 328                 rl_left = cast_rl(type, rl_left_orig);
 329         } else {
 330                 return;
 331         }
 332
 333         if (!possibly_true_rl(rl_left, expr->op, rl_right) &&
 334             !is_u64_vs_ulongmax(expr)) {
 335                 char *name = expr_to_str(expr);
 336
 337                 sm_warning("impossible condition '(%s) => (%s %s %s)'", name,
 338                        show_rl(rl_left), show_special(expr->op),
 339                        show_rl(rl_right));
 340                 free_string(name);
 341         }
 342
 343         if (!possibly_false_rl(rl_left, expr->op, rl_right) &&
 344             !is_unconstant_macro(expr->left) &&
 345             !is_unconstant_macro(expr->right)) {
 346                 char *name = expr_to_str(expr);
 347
 348                 sm_warning("always true condition '(%s) => (%s %s %s)'", name,
 349                        show_rl(rl_left_orig), show_special(expr->op),
 350                        show_rl(rl_right_orig));
 351                 free_string(name);
 352         }
 353 }
 354
 355 void check_signed(int id)
 356 {
 357         my_id = id;
 358
 359         add_hook(&match_assign, ASSIGNMENT_HOOK);
 360         add_hook(&match_condition, CONDITION_HOOK);
 361 }