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 != '<' && expr->op != SPECIAL_UNSIGNED_LT)
 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                         struct expression *right = strip_expr(tmp->right);
 167
 168                         if (right->op != '>' &&
 169                             right->op != SPECIAL_UNSIGNED_GT &&
 170                             right->op != SPECIAL_GTE &&
 171                             right->op != SPECIAL_UNSIGNED_GTE)
 172                                 return 0;
 173
 174                         name1 = get_variable_from_expr_complex(var, NULL);
 175                         if (!name1)
 176                                 goto free;
 177
 178                         name2 = get_variable_from_expr_complex(right->left, NULL);
 179                         if (!name2)
 180                                 goto free;
 181                         if (!strcmp(name1, name2))
 182                                 ret = 1;
 183                         goto free;
 184
 185                 }
 186                 return 0;
 187         } END_FOR_EACH_PTR_REVERSE(tmp);
 188
 189 free:
 190         free_string(name1);
 191         free_string(name2);
 192         return ret;
 193 }
 194
 195 static void match_condition(struct expression *expr)
 196 {
 197         long long known;
 198         struct expression *var = NULL;
 199         struct symbol *var_type = NULL;
 200         struct symbol *known_type = NULL;
 201         long long max;
 202         long long min;
 203         int lr;
 204         char *name;
 205
 206         if (expr->type != EXPR_COMPARE)
 207                 return;
 208
 209         if (get_value(expr->left, &known)) {
 210                 if (get_value(expr->right, &max))
 211                         return; /* both sides known */
 212                 lr = VAR_ON_RIGHT;
 213                 var = expr->right;
 214                 known_type = get_type(expr->left);
 215         } else if (get_value(expr->right, &known)) {
 216                 lr = VAR_ON_LEFT;
 217                 var = expr->left;
 218                 known_type = get_type(expr->right);
 219         } else {
 220                 return;
 221         }
 222
 223         var_type = get_type(var);
 224         if (!var_type)
 225                 return;
 226         if (var_type->bit_size >= 32 && !option_spammy)
 227                 return;
 228
 229         name = get_variable_from_expr_complex(var, NULL);
 230
 231         if (expr->op == SPECIAL_EQUAL || expr->op == SPECIAL_NOTEQUAL) {
 232                 if (eqneq_max(var_type) < known || eqneq_min(var_type) > known)
 233                         sm_msg("error: %s is never equal to %lld (wrong type %lld - %lld).",
 234                                 name, known, eqneq_min(var_type), eqneq_max(var_type));
 235                 goto free;
 236         }
 237
 238         max = type_max(var_type);
 239         min = type_min(var_type);
 240
 241         if (max < known) {
 242                 const char *tf = get_tf(max, known, lr, expr->op);
 243
 244                 sm_msg("warn: %lld is more than %lld (max '%s' can be) so this is always %s.",
 245                         known, max, name, tf);
 246         }
 247
 248         if (known == 0 && type_unsigned(var_type)) {
 249                 if ((lr && expr->op == '<') ||
 250                     (lr && expr->op == SPECIAL_UNSIGNED_LT) ||
 251                     (!lr && expr->op == '>') ||
 252                     (!lr && expr->op == SPECIAL_UNSIGNED_GT)) {
 253                         if (!compare_against_macro(lr, expr) && !cap_both_size(lr, expr)) {
 254                                 sm_msg("warn: unsigned '%s' is never less than zero.", name);
 255                                 goto free;
 256                         }
 257                 }
 258         }
 259
 260         if (type_unsigned(var_type) && known_type && !type_unsigned(known_type) && known < 0) {
 261                 sm_msg("warn: unsigned '%s' is never less than zero (%lld).", name, known);
 262                 goto free;
 263         }
 264
 265         if (min < 0 && min > known) {
 266                 const char *tf = get_tf(min, known, lr, expr->op);
 267
 268                 sm_msg("warn: %lld is less than %lld (min '%s' can be) so this is always %s.",
 269                         known, min, name, tf);
 270         }
 271 free:
 272         free_string(name);
 273 }
 274
 275 void check_signed(int id)
 276 {
 277         my_id = id;
 278
 279         add_hook(&match_assign, ASSIGNMENT_HOOK);
 280         add_hook(&match_condition, CONDITION_HOOK);
 281 }