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