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
 100 static const char *get_tf(long long variable, long long known, int var_pos, int op)
 101 {
 102         if (op == SPECIAL_EQUAL)
 103                 return "false";
 104         if (op == SPECIAL_NOTEQUAL)
 105                 return "true";
 106         if (var_pos == VAR_ON_LEFT) {
 107                 if (variable > known && (op == '<' || op == SPECIAL_LTE))
 108                         return "false";
 109                 if (variable > known && (op == '>' || op == SPECIAL_GTE))
 110                         return "true";
 111                 if (variable < known && (op == '<' || op == SPECIAL_LTE))
 112                         return "true";
 113                 if (variable < known && (op == '>' || op == SPECIAL_GTE))
 114                         return "false";
 115         }
 116         if (var_pos == VAR_ON_RIGHT) {
 117                 if (known > variable && (op == '<' || op == SPECIAL_LTE))
 118                         return "false";
 119                 if (known > variable && (op == '>' || op == SPECIAL_GTE))
 120                         return "true";
 121                 if (known < variable && (op == '<' || op == SPECIAL_LTE))
 122                         return "true";
 123                 if (known < variable && (op == '>' || op == SPECIAL_GTE))
 124                         return "false";
 125         }
 126         return "the same";
 127 }
 128
 129 static int compare_against_macro(int lr, struct expression *expr)
 130 {
 131         struct expression *known = expr->left;
 132
 133         if (lr == VAR_ON_LEFT)
 134                 known = expr->right;
 135
 136         return !!get_macro_name(known->pos);
 137 }
 138
 139 static int cap_both_size(int lr, struct expression *expr)
 140 {
 141
 142         struct expression *var = expr->left;
 143         struct expression *tmp;
 144         char *name1 = NULL;
 145         char *name2 = NULL;
 146         int ret = 0;
 147         int i;
 148
 149         /* screw it.  I am writing this to mark yoda code as buggy.
 150          * Valid comparisons between an unsigned and zero are:
 151          * 1) inside a macro.
 152          * 2) foo < LOWER_BOUND where LOWER_BOUND is a macro.
 153          * 3) foo < 0 || foo > X in exactly this format.  No Yoda.
 154          */
 155
 156         if (lr != VAR_ON_LEFT)
 157                 return 0;
 158         if (expr->op != '<')  /* this is implied by lr == VAR_ON_LEFT */
 159                 return 0;
 160
 161         i = 0;
 162         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 163                 if (!i++)
 164                         continue;
 165                 if (tmp->op == SPECIAL_LOGICAL_OR) {
 166                         if (tmp->right->op != '>' &&
 167                             tmp->right->op != SPECIAL_GTE &&
 168                             tmp->right->op != SPECIAL_UNSIGNED_GTE)
 169                                 return 0;
 170
 171                         name1 = get_variable_from_expr_complex(var, NULL);
 172                         if (!name1)
 173                                 goto free;
 174
 175                         name2 = get_variable_from_expr_complex(tmp->right->left, NULL);
 176                         if (!name2)
 177                                 goto free;
 178                         if (!strcmp(name1, name2))
 179                                 ret = 1;
 180                         goto free;
 181
 182                 }
 183                 return 0;
 184         } END_FOR_EACH_PTR_REVERSE(tmp);
 185
 186 free:
 187         free_string(name1);
 188         free_string(name2);
 189         return ret;
 190 }
 191
 192 static void match_condition(struct expression *expr)
 193 {
 194         long long known;
 195         struct expression *var = NULL;
 196         struct symbol *var_type = NULL;
 197         struct symbol *known_type = NULL;
 198         long long max;
 199         long long min;
 200         int lr;
 201         char *name;
 202
 203         if (expr->type != EXPR_COMPARE)
 204                 return;
 205
 206         if (get_value(expr->left, &known)) {
 207                 if (get_value(expr->right, &max))
 208                         return; /* both sides known */
 209                 lr = VAR_ON_RIGHT;
 210                 var = expr->right;
 211                 known_type = get_type(expr->left);
 212         } else if (get_value(expr->right, &known)) {
 213                 lr = VAR_ON_LEFT;
 214                 var = expr->left;
 215                 known_type = get_type(expr->right);
 216         } else {
 217                 return;
 218         }
 219
 220         var_type = get_type(var);
 221         if (!var_type)
 222                 return;
 223         if (var_type->bit_size >= 32 && !option_spammy)
 224                 return;
 225
 226         name = get_variable_from_expr_complex(var, NULL);
 227
 228         if (expr->op == SPECIAL_EQUAL || expr->op == SPECIAL_NOTEQUAL) {
 229                 if (eqneq_max(var_type) < known || eqneq_min(var_type) > known)
 230                         sm_msg("error: %s is never equal to %lld (wrong type %lld - %lld).",
 231                                 name, known, eqneq_min(var_type), eqneq_max(var_type));
 232                 goto free;
 233         }
 234
 235         max = type_max(var_type);
 236         min = type_min(var_type);
 237
 238         if (max < known) {
 239                 const char *tf = get_tf(max, known, lr, expr->op);
 240
 241                 sm_msg("warn: %lld is more than %lld (max '%s' can be) so this is always %s.",
 242                         known, max, name, tf);
 243         }
 244
 245         if (known == 0 && type_unsigned(var_type)) {
 246                 if ((lr && expr->op == '<') || (!lr && expr->op == '>')) {
 247                         if (!compare_against_macro(lr, expr) && !cap_both_size(lr, expr)) {
 248                                 sm_msg("warn: unsigned '%s' is never less than zero.", name);
 249                                 goto free;
 250                         }
 251                 }
 252         }
 253
 254         if (type_unsigned(var_type) && known_type && !type_unsigned(known_type) && known < 0) {
 255                 sm_msg("warn: unsigned '%s' is never less than zero (%lld).", name, known);
 256                 goto free;
 257         }
 258
 259         if (min < 0 && min > known) {
 260                 const char *tf = get_tf(min, known, lr, expr->op);
 261
 262                 sm_msg("warn: %lld is less than %lld (min '%s' can be) so this is always %s.",
 263                         known, min, name, tf);
 264         }
 265 free:
 266         free_string(name);
 267 }
 268
 269 void check_signed(int id)
 270 {
 271         my_id = id;
 272
 273         add_hook(&match_assign, ASSIGNMENT_HOOK);
 274         add_hook(&match_condition, CONDITION_HOOK);
 275 }