check_signed.c

   1 /*
   2  * sparse/check_signed.c
   3  *
   4  * Copyright (C) 2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * Check for things which are signed but probably should be unsigned.
  12  *
  13  * Hm...  It seems like at this point in the processing, sparse makes all
  14  * bitfields unsigned.  Which is logical but not what GCC does.
  15  *
  16  */
  17
  18 #include "smatch.h"
  19
  20 static int my_id;
  21
  22 #define VAR_ON_RIGHT 0
  23 #define VAR_ON_LEFT 1
  24
  25 static long long eqneq_max(struct symbol *base_type)
  26 {
  27         long long ret = whole_range.max;
  28         int bits;
  29
  30         if (!base_type || !base_type->bit_size)
  31                 return ret;
  32         bits = base_type->bit_size;
  33         if (bits == 64)
  34                 return ret;
  35         if (bits < 32)
  36                 return type_max(base_type);
  37         ret >>= (63 - bits);
  38         return ret;
  39 }
  40
  41 static long long eqneq_min(struct symbol *base_type)
  42 {
  43         long long ret = whole_range.min;
  44         int bits;
  45
  46         if (!base_type || !base_type->bit_size)
  47                 return ret;
  48         if (base_type->bit_size < 32)
  49                 return type_min(base_type);
  50         ret = whole_range.max;
  51         bits = base_type->bit_size - 1;
  52         ret >>= (63 - bits);
  53         return -(ret + 1);
  54 }
  55
  56 static void match_assign(struct expression *expr)
  57 {
  58         struct symbol *sym;
  59         long long val;
  60         long long max;
  61         long long min;
  62         char *name;
  63
  64         if (expr->op == SPECIAL_AND_ASSIGN || expr->op == SPECIAL_OR_ASSIGN)
  65                 return;
  66
  67         sym = get_type(expr->left);
  68         if (!sym) {
  69                 //sm_msg("could not get type");
  70                 return;
  71         }
  72         if (sym->bit_size >= 32) /* max_val limits this */
  73                 return;
  74         if (!get_implied_value(expr->right, &val))
  75                 return;
  76         max = type_max(sym);
  77         if (max < val && !(val < 256 && max == 127)) {
  78                 name = get_variable_from_expr_complex(expr->left, NULL);
  79                 sm_msg("warn: value %lld can't fit into %lld '%s'", val, max, name);
  80                 free_string(name);
  81         }
  82         min = type_min(sym);
  83         if (min > val) {
  84                 if (min == 0 && val == -1) /* assigning -1 to unsigned variables is idiomatic */
  85                         return;
  86                 if (expr->right->type == EXPR_PREOP && expr->right->op == '~')
  87                         return;
  88                 if (expr->op == SPECIAL_SUB_ASSIGN || expr->op == SPECIAL_ADD_ASSIGN)
  89                         return;
  90                 name = get_variable_from_expr_complex(expr->left, NULL);
  91                 if (min == 0)
  92                         sm_msg("warn: assigning %lld to unsigned variable '%s'", val, name);
  93                 else
  94                         sm_msg("warn: value %lld can't fit into %lld '%s'", val, min, name);
  95                 free_string(name);
  96         }
  97 }
  98
  99 static const char *get_tf(long long variable, long long known, int var_pos, int op)
 100 {
 101         if (op == SPECIAL_EQUAL)
 102                 return "false";
 103         if (op == SPECIAL_NOTEQUAL)
 104                 return "true";
 105         if (var_pos == VAR_ON_LEFT) {
 106                 if (variable > known && (op == '<' || op == SPECIAL_LTE))
 107                         return "false";
 108                 if (variable > known && (op == '>' || op == SPECIAL_GTE))
 109                         return "true";
 110                 if (variable < known && (op == '<' || op == SPECIAL_LTE))
 111                         return "true";
 112                 if (variable < known && (op == '>' || op == SPECIAL_GTE))
 113                         return "false";
 114         }
 115         if (var_pos == VAR_ON_RIGHT) {
 116                 if (known > variable && (op == '<' || op == SPECIAL_LTE))
 117                         return "false";
 118                 if (known > variable && (op == '>' || op == SPECIAL_GTE))
 119                         return "true";
 120                 if (known < variable && (op == '<' || op == SPECIAL_LTE))
 121                         return "true";
 122                 if (known < variable && (op == '>' || op == SPECIAL_GTE))
 123                         return "false";
 124         }
 125         return "the same";
 126 }
 127
 128 static int compare_against_macro(int lr, struct expression *expr)
 129 {
 130         struct expression *known = expr->left;
 131
 132         if (lr == VAR_ON_LEFT)
 133                 known = expr->right;
 134
 135         return !!get_macro_name(known->pos);
 136 }
 137
 138 static int cap_both_size(int lr, struct expression *expr)
 139 {
 140
 141         struct expression *var = expr->left;
 142         struct expression *tmp;
 143         char *name1 = NULL;
 144         char *name2 = NULL;
 145         int ret = 0;
 146         int i;
 147
 148         /* screw it.  I am writing this to mark yoda code as buggy.
 149          * Valid comparisons between an unsigned and zero are:
 150          * 1) inside a macro.
 151          * 2) foo < LOWER_BOUND where LOWER_BOUND is a macro.
 152          * 3) foo < 0 || foo > X in exactly this format.  No Yoda.
 153          */
 154
 155         if (lr != VAR_ON_LEFT)
 156                 return 0;
 157         if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
 158                 return 0;
 159
 160         i = 0;
 161         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 162                 if (!i++)
 163                         continue;
 164                 if (tmp->op == SPECIAL_LOGICAL_OR) {
 165                         struct expression *right = strip_expr(tmp->right);
 166
 167                         if (right->op != '>' &&
 168                             right->op != SPECIAL_UNSIGNED_GT &&
 169                             right->op != SPECIAL_GTE &&
 170                             right->op != SPECIAL_UNSIGNED_GTE)
 171                                 return 0;
 172
 173                         name1 = get_variable_from_expr_complex(var, NULL);
 174                         if (!name1)
 175                                 goto free;
 176
 177                         name2 = get_variable_from_expr_complex(right->left, NULL);
 178                         if (!name2)
 179                                 goto free;
 180                         if (!strcmp(name1, name2))
 181                                 ret = 1;
 182                         goto free;
 183
 184                 }
 185                 return 0;
 186         } END_FOR_EACH_PTR_REVERSE(tmp);
 187
 188 free:
 189         free_string(name1);
 190         free_string(name2);
 191         return ret;
 192 }
 193
 194 static void match_condition(struct expression *expr)
 195 {
 196         long long known;
 197         struct expression *var = NULL;
 198         struct symbol *var_type = NULL;
 199         struct symbol *known_type = NULL;
 200         long long max;
 201         long long min;
 202         int lr;
 203         char *name;
 204
 205         if (expr->type != EXPR_COMPARE)
 206                 return;
 207
 208         if (get_value(expr->left, &known)) {
 209                 if (get_value(expr->right, &max))
 210                         return; /* both sides known */
 211                 lr = VAR_ON_RIGHT;
 212                 var = expr->right;
 213                 known_type = get_type(expr->left);
 214         } else if (get_value(expr->right, &known)) {
 215                 lr = VAR_ON_LEFT;
 216                 var = expr->left;
 217                 known_type = get_type(expr->right);
 218         } else {
 219                 return;
 220         }
 221
 222         var_type = get_type(var);
 223         if (!var_type)
 224                 return;
 225         if (var_type->bit_size >= 32 && !option_spammy)
 226                 return;
 227
 228         name = get_variable_from_expr_complex(var, NULL);
 229
 230         if (expr->op == SPECIAL_EQUAL || expr->op == SPECIAL_NOTEQUAL) {
 231                 if (eqneq_max(var_type) < known || eqneq_min(var_type) > known)
 232                         sm_msg("error: %s is never equal to %lld (wrong type %lld - %lld).",
 233                                 name, known, eqneq_min(var_type), eqneq_max(var_type));
 234                 goto free;
 235         }
 236
 237         max = type_max(var_type);
 238         min = type_min(var_type);
 239
 240         if (max < known) {
 241                 const char *tf = get_tf(max, known, lr, expr->op);
 242
 243                 sm_msg("warn: %lld is more than %lld (max '%s' can be) so this is always %s.",
 244                         known, max, name, tf);
 245         }
 246
 247         if (known == 0 && type_unsigned(var_type)) {
 248                 if ((lr && expr->op == '<') ||
 249                     (lr && expr->op == SPECIAL_UNSIGNED_LT) ||
 250                     (!lr && expr->op == '>') ||
 251                     (!lr && expr->op == SPECIAL_UNSIGNED_GT)) {
 252                         if (!compare_against_macro(lr, expr) && !cap_both_size(lr, expr)) {
 253                                 sm_msg("warn: unsigned '%s' is never less than zero.", name);
 254                                 goto free;
 255                         }
 256                 }
 257         }
 258
 259         if (type_unsigned(var_type) && known_type && !type_unsigned(known_type) && known < 0) {
 260                 sm_msg("warn: unsigned '%s' is never less than zero (%lld).", name, known);
 261                 goto free;
 262         }
 263
 264         if (min < 0 && min > known) {
 265                 const char *tf = get_tf(min, known, lr, expr->op);
 266
 267                 sm_msg("warn: %lld is less than %lld (min '%s' can be) so this is always %s.",
 268                         known, min, name, tf);
 269         }
 270 free:
 271         free_string(name);
 272 }
 273
 274 void check_signed(int id)
 275 {
 276         my_id = id;
 277
 278         add_hook(&match_assign, ASSIGNMENT_HOOK);
 279         add_hook(&match_condition, CONDITION_HOOK);
 280 }