check_null_deref.c

   1 /*
   2  * sparse/check_deference.c
   3  *
   4  * Copyright (C) 2006 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "token.h"
  11 #include "smatch.h"
  12
  13 struct func_n_param {
  14         struct symbol *func;
  15         int param;
  16         int line;
  17 };
  18 ALLOCATOR(func_n_param, "func parameters");
  19 DECLARE_PTR_LIST(param_list, struct func_n_param);
  20
  21 static struct param_list *funcs;
  22 static struct param_list *do_not_call;
  23 static struct param_list *calls;
  24
  25 static int my_id;
  26
  27 STATE(argument);
  28 STATE(assumed_nonnull);
  29 STATE(ignore);
  30 STATE(isnull);
  31 STATE(nonnull);
  32
  33 static struct symbol *func_sym;
  34
  35 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
  36                                        struct smatch_state *s1,
  37                                        struct smatch_state *s2)
  38 {
  39         /*
  40          * conditions are a special case.  In the cond_(true|false)_stack
  41          * we expect to be merging null with a new specified state all the
  42          * time.  Outside of a condition we have things where the code
  43          * assumes a global variable is non null.  That gets merged with
  44          * other code and it becomes undefined.  But really it should be
  45          * non-null.
  46          * In theory we could test for that latter case by printing a message
  47          * when someone checks a variable we already had marked as non-null.
  48          * In practise that didn't work really well because a lot of macros
  49          * have "unneeded" checks for null.
  50          */
  51         if (!in_condition() && s1 == NULL)
  52                 return s2;
  53         if (s1 == &ignore || s2 == &ignore)
  54                 return &ignore;
  55         if (s1 == NULL && s2 == &assumed_nonnull)
  56                 return &assumed_nonnull;
  57         if (s1 == &assumed_nonnull && s2 == &nonnull)
  58                 return &assumed_nonnull;
  59         if (s1 == &argument && s2 == &assumed_nonnull)
  60                 return &assumed_nonnull;
  61         if (s1 == &argument && s2 == &nonnull)
  62                 return &nonnull;
  63         return &undefined;
  64 }
  65
  66 static struct func_n_param *alloc_func_n_param(struct symbol *func, int param,
  67                                                int line)
  68 {
  69         struct func_n_param *tmp = __alloc_func_n_param(0);
  70
  71         tmp->func = func;
  72         tmp->param = param;
  73         tmp->line = line;
  74         return tmp;
  75 }
  76
  77 static int get_arg_num(struct symbol *sym)
  78 {
  79         struct symbol *arg;
  80         int i = 0;
  81
  82         FOR_EACH_PTR(func_sym->ctype.base_type->arguments, arg) {
  83                 if (arg == sym) {
  84                         return i;
  85                 }
  86                 i++;
  87         } END_FOR_EACH_PTR(arg);
  88         return -1;
  89 }
  90
  91 static void add_do_not_call(struct symbol *sym, int line)
  92 {
  93         struct func_n_param *tmp;
  94         int num = get_arg_num(sym);
  95
  96         FOR_EACH_PTR(do_not_call, tmp) {
  97                 if (tmp->func == func_sym && tmp->param == num)
  98                         return;
  99         } END_FOR_EACH_PTR(tmp);
 100         tmp = alloc_func_n_param(func_sym, num, line);
 101         add_ptr_list(&do_not_call, tmp);
 102 }
 103
 104 static void add_param(struct param_list **list, struct symbol *func, int param,
 105                       int line)
 106 {
 107         struct func_n_param *tmp;
 108
 109         tmp = alloc_func_n_param(func, param, line);
 110         add_ptr_list(list, tmp);
 111 }
 112
 113 static void match_function_def(struct symbol *sym)
 114 {
 115         struct symbol *arg;
 116
 117         func_sym = sym;
 118         add_param(&funcs, sym, 0, 0);
 119         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 120                 if (!arg->ident) {
 121                         continue;
 122                 }
 123                 set_state(arg->ident->name, my_id, arg, &argument);
 124         } END_FOR_EACH_PTR(arg);
 125 }
 126
 127 static void match_function_call_after(struct expression *expr)
 128 {
 129         struct expression *tmp;
 130         struct symbol *sym;
 131         char *name;
 132         struct symbol *func = NULL;
 133         int i;
 134
 135         if (expr->fn->type == EXPR_SYMBOL) {
 136                 func = expr->fn->symbol;
 137         }
 138
 139         i = 0;
 140         FOR_EACH_PTR(expr->args, tmp) {
 141                 tmp = strip_expr(tmp);
 142                 if (tmp->op == '&') {
 143                         name = get_variable_from_expr_simple(tmp->unop, &sym);
 144                         if (name) {
 145                                 name = alloc_string(name);
 146                                 set_state(name, my_id, sym, &assumed_nonnull);
 147                         }
 148                 } else {
 149                         name = get_variable_from_expr_simple(tmp, &sym);
 150                         if (func && name && sym)
 151                                 if (get_state(name, my_id, sym) == &undefined)
 152                                         add_param(&calls, func, i, get_lineno());
 153                 }
 154                 i++;
 155         } END_FOR_EACH_PTR(tmp);
 156 }
 157
 158 static int assign_seen;
 159 static void match_assign(struct expression *expr)
 160 {
 161         struct expression *left;
 162         struct symbol *sym;
 163         char *name;
 164
 165         if (assign_seen) {
 166                 assign_seen--;
 167                 return;
 168         }
 169         left = strip_expr(expr->left);
 170         name = get_variable_from_expr_simple(left, &sym);
 171         if (!name)
 172                 return;
 173         name = alloc_string(name);
 174         if (is_zero(expr->right))
 175                 set_state(name, my_id, sym, &isnull);
 176         else
 177                 set_state(name, my_id, sym, &assumed_nonnull);
 178 }
 179
 180 /*
 181  * set_new_true_false_states is used in the following conditions
 182  * if (a) { ... if (a) { ... } }
 183  * The problem is that after the second blog a is set to undefined
 184  * even though the second condition is meaning less.  (The second test
 185  * could be a macro for example).
 186  */
 187
 188 static void set_new_true_false_states(const char *name, int my_id,
 189                                       struct symbol *sym, struct smatch_state *true_state,
 190                                       struct smatch_state *false_state)
 191 {
 192         struct smatch_state *tmp;
 193
 194         tmp = get_state(name, my_id, sym);
 195
 196         SM_DEBUG("set_new_stuff called at %d value='%s'\n", get_lineno(), show_state(tmp));
 197
 198         if (!tmp || tmp == &undefined || tmp == &isnull || tmp == &argument)
 199                 set_true_false_states(name, my_id, sym, true_state, false_state);
 200 }
 201
 202 static void match_condition(struct expression *expr)
 203 {
 204         struct symbol *sym;
 205         char *name;
 206
 207         expr = strip_expr(expr);
 208         switch(expr->type) {
 209         case EXPR_SYMBOL:
 210         case EXPR_DEREF:
 211                 name = get_variable_from_expr_simple(expr, &sym);
 212                 if (!name)
 213                         return;
 214                 name = alloc_string(name);
 215                 set_new_true_false_states(name, my_id, sym, &nonnull, &isnull);
 216                 return;
 217         case EXPR_ASSIGNMENT:
 218                 assign_seen++;
 219                 /*
 220                  * There is a kernel macro that does
 221                  *  for ( ... ; ... || x = NULL ; ) ...
 222                  */
 223                 if (is_zero(expr->right)) {
 224                         name = get_variable_from_expr_simple(expr->left, &sym);
 225                         if (!name)
 226                                 return;
 227                         name = alloc_string(name);
 228                         set_new_true_false_states(name, my_id, sym, NULL, &isnull);
 229                         return;
 230                 }
 231                  /* You have to deal with stuff like if (a = b = c) */
 232                 match_condition(expr->right);
 233                 match_condition(expr->left);
 234                 return;
 235         default:
 236                 return;
 237         }
 238 }
 239
 240 static void match_declarations(struct symbol *sym)
 241 {
 242         const char * name;
 243
 244         if ((get_base_type(sym))->type == SYM_ARRAY) {
 245                 return;
 246         }
 247
 248         name = sym->ident->name;
 249
 250         if (sym->initializer) {
 251                 if (is_zero(sym->initializer))
 252                         set_state(name, my_id, sym, &isnull);
 253                 else
 254                         set_state(name, my_id, sym, &assumed_nonnull);
 255         } else {
 256                 set_state(name, my_id, sym, &undefined);
 257         }
 258 }
 259
 260 static void match_dereferences(struct expression *expr)
 261 {
 262         char *deref = NULL;
 263         struct symbol *sym = NULL;
 264         struct smatch_state *state;
 265
 266         if (strcmp(show_special(expr->deref->op), "*"))
 267                 return;
 268
 269         deref = get_variable_from_expr_simple(expr->deref->unop, &sym);
 270         if (!deref)
 271                 return;
 272         deref = alloc_string(deref);
 273
 274         state = get_state(deref, my_id, sym);
 275         if (state == &undefined) {
 276                 smatch_msg("Dereferencing Undefined:  '%s'", deref);
 277                 set_state(deref, my_id, sym, &ignore);
 278         } else if (state == &isnull) {
 279                 /*
 280                  * It turns out that you only get false positives from
 281                  * this.  Mostly foo = NULL; sizeof(*foo);
 282                  * And even if it wasn't always a false positive you'd think
 283                  * it would get caught in testing if it failed every time.
 284                  */
 285                 set_state(deref, my_id, sym, &ignore);
 286         } else if (state == &argument) {
 287                 add_do_not_call(sym, get_lineno());
 288                 set_state(deref, my_id, sym, &assumed_nonnull);
 289         } else {
 290                 free_string(deref);
 291         }
 292 }
 293
 294 static void end_file_processing()
 295 {
 296         struct func_n_param *param1, *param2;
 297
 298         // if a function is not static print it out...
 299         FOR_EACH_PTR(do_not_call, param1) {
 300                 if (!(param1->func->ctype.modifiers & MOD_STATIC))
 301                         printf("%s +%d unchecked param %s %d\n",
 302                                get_filename(), param1->line,
 303                                param1->func->ident->name, param1->param);
 304         } END_FOR_EACH_PTR(param1);
 305
 306         // if there is an error print it out...
 307         FOR_EACH_PTR(calls, param1) {
 308                 FOR_EACH_PTR(do_not_call, param2) {
 309                         if (param1->func == param2->func &&
 310                             param1->param == param2->param)
 311                                 printf("%s +%d cross_func deref %s %d\n",
 312                                        get_filename(), param1->line,
 313                                        param1->func->ident->name,
 314                                        param1->param);
 315                 } END_FOR_EACH_PTR(param2);
 316         } END_FOR_EACH_PTR(param1);
 317
 318         // if someone calls a non-static function print that..
 319         FOR_EACH_PTR(calls, param1) {
 320                 int defined = 0;
 321
 322                 FOR_EACH_PTR(funcs, param2) {
 323                         if (param1->func == param2->func)
 324                                 defined = 1;
 325                 } END_FOR_EACH_PTR(param2);
 326                 if (!defined)
 327                         printf("%s +%d undefined param %s %d\n", get_filename(),
 328                                param1->line, param1->func->ident->name,
 329                                param1->param);
 330         } END_FOR_EACH_PTR(param1);
 331 }
 332
 333 void register_null_deref(int id)
 334 {
 335         my_id = id;
 336         add_merge_hook(my_id, &merge_func);
 337         add_hook(&match_function_def, FUNC_DEF_HOOK);
 338         add_hook(&match_function_call_after, FUNCTION_CALL_AFTER_HOOK);
 339         add_hook(&match_assign, ASSIGNMENT_AFTER_HOOK);
 340         add_hook(&match_condition, CONDITION_HOOK);
 341         add_hook(&match_dereferences, DEREF_HOOK);
 342         add_hook(&match_declarations, DECLARATION_HOOK);
 343         add_hook(&end_file_processing, END_FILE_HOOK);
 344 }