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 #include "smatch_slist.h"
  13
  14 /*
  15  * TODO:  The return_null list of functions should be determined automatically
  16  */
  17 const char *return_null[] = {
  18         "kmalloc",
  19 };
  20
  21 struct func_n_param {
  22         struct symbol *func;
  23         int param;
  24         int line;
  25 };
  26 ALLOCATOR(func_n_param, "func parameters");
  27 DECLARE_PTR_LIST(param_list, struct func_n_param);
  28
  29 static struct param_list *funcs;
  30 static struct param_list *do_not_call;
  31 static struct param_list *calls;
  32
  33 static int my_id;
  34
  35 STATE(argument);
  36 STATE(arg_nonnull);
  37 STATE(arg_null);
  38 STATE(assumed_nonnull);
  39 STATE(ignore);
  40 STATE(isnull);
  41 STATE(nonnull);
  42
  43 static struct symbol *func_sym;
  44
  45 /*
  46  * merge_func() is to handle assumed_nonnull.
  47  *
  48  * Assumed_nonnull is a funny state.  It's almost the same as
  49  * no state.  Maybe it would be better to delete it completely...
  50  */
  51 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
  52                                        struct smatch_state *s1,
  53                                        struct smatch_state *s2)
  54 {
  55         if (s1 == &ignore || s2 == &ignore)
  56                 return &ignore;
  57         if (s1 == NULL && s2 == &assumed_nonnull)
  58                 return &assumed_nonnull;
  59         if (s1 == NULL)
  60                 return &undefined;
  61         return &merged;
  62
  63 }
  64
  65 static int is_maybe_null_no_arg(const char *name, struct symbol *sym)
  66 {
  67         struct state_list *slist;
  68         struct sm_state *tmp;
  69         int ret = 0;
  70
  71         slist = get_possible_states(name, my_id, sym);
  72         FOR_EACH_PTR(slist, tmp) {
  73                 if (tmp->state == &ignore)
  74                         return 0;
  75                 if (tmp->state == &isnull) {
  76                         SM_DEBUG("is_maybe_null_no_arg() says %s &isnull\n", name);
  77                         ret = 1;
  78                 }
  79                 if (tmp->state == &undefined) {
  80                         SM_DEBUG("is_maybe_null_no_arg() says %s &undefined\n", name);
  81                         ret = 1;
  82                 }
  83         } END_FOR_EACH_PTR(tmp);
  84         return ret;
  85 }
  86
  87
  88 static int is_maybe_null(const char *name, struct symbol *sym)
  89 {
  90         struct state_list *slist;
  91         struct sm_state *tmp;
  92         int ret = 0;
  93
  94         slist = get_possible_states(name, my_id, sym);
  95         FOR_EACH_PTR(slist, tmp) {
  96                 if (tmp->state == &ignore)
  97                         return 0;
  98                 if (tmp->state == &isnull) {
  99                         SM_DEBUG("is_maybe_null() says %s &isnull\n", name);
 100                         ret = 1;
 101                 }
 102                 if (tmp->state == &undefined) {
 103                         SM_DEBUG("is_maybe_null() says %s &undefined\n", name);
 104                         ret = 1;
 105                 }
 106                 if (tmp->state == &arg_null) {
 107                         SM_DEBUG("is_maybe_null() says %s &arg_null\n", name);
 108                         ret = 1;
 109                 }
 110         } END_FOR_EACH_PTR(tmp);
 111         return ret;
 112 }
 113
 114 static int is_maybe_null_arg(char *name, struct symbol *sym)
 115 {
 116         struct state_list *slist;
 117         struct sm_state *tmp;
 118         int maybe_null = 0;
 119
 120         slist = get_possible_states(name, my_id, sym);
 121         FOR_EACH_PTR(slist, tmp) {
 122                 if (tmp->state != &argument && tmp->state != &arg_null &&
 123                     tmp->state != &arg_nonnull && tmp->state !=  &merged &&
 124                     tmp->state != &assumed_nonnull)
 125                         return 0;
 126                 if (tmp->state == &argument || tmp->state == &arg_null)
 127                         maybe_null = 1;
 128         } END_FOR_EACH_PTR(tmp);
 129
 130         /* We really only care about arguments if they are null */
 131         return maybe_null;
 132 }
 133
 134 static struct func_n_param *alloc_func_n_param(struct symbol *func, int param,
 135                                                int line)
 136 {
 137         struct func_n_param *tmp = __alloc_func_n_param(0);
 138
 139         tmp->func = func;
 140         tmp->param = param;
 141         tmp->line = line;
 142         return tmp;
 143 }
 144
 145 static int get_arg_num(struct symbol *sym)
 146 {
 147         struct symbol *arg;
 148         int i = 0;
 149
 150         FOR_EACH_PTR(func_sym->ctype.base_type->arguments, arg) {
 151                 if (arg == sym) {
 152                         return i;
 153                 }
 154                 i++;
 155         } END_FOR_EACH_PTR(arg);
 156         return -1;
 157 }
 158
 159 static void add_do_not_call(struct symbol *sym, int line)
 160 {
 161         struct func_n_param *tmp;
 162         int num = get_arg_num(sym);
 163
 164         FOR_EACH_PTR(do_not_call, tmp) {
 165                 if (tmp->func == func_sym && tmp->param == num)
 166                         return;
 167         } END_FOR_EACH_PTR(tmp);
 168         tmp = alloc_func_n_param(func_sym, num, line);
 169         add_ptr_list(&do_not_call, tmp);
 170 }
 171
 172 static void add_param(struct param_list **list, struct symbol *func, int param,
 173                       int line)
 174 {
 175         struct func_n_param *tmp;
 176
 177         tmp = alloc_func_n_param(func, param, line);
 178         add_ptr_list(list, tmp);
 179 }
 180
 181 static void match_function_def(struct symbol *sym)
 182 {
 183         struct symbol *arg;
 184
 185         func_sym = sym;
 186         add_param(&funcs, sym, 0, 0);
 187         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 188                 if (!arg->ident) {
 189                         continue;
 190                 }
 191                 set_state(arg->ident->name, my_id, arg, &argument);
 192         } END_FOR_EACH_PTR(arg);
 193 }
 194
 195 static char *get_function_call(struct expression *expr)
 196 {
 197         if (expr->type != EXPR_CALL)
 198                 return NULL;
 199         if (expr->fn->type == EXPR_SYMBOL && expr->fn->symbol)
 200                 return expr->fn->symbol->ident->name;
 201         return NULL;
 202 }
 203
 204 static void match_function_call_after(struct expression *expr)
 205 {
 206         struct expression *tmp;
 207         struct symbol *sym;
 208         char *name;
 209         struct symbol *func = NULL;
 210         int i;
 211
 212         if (expr->fn->type == EXPR_SYMBOL)
 213                 func = expr->fn->symbol;
 214
 215         i = 0;
 216         FOR_EACH_PTR(expr->args, tmp) {
 217                 tmp = strip_expr(tmp);
 218                 if (tmp->op == '&') {
 219                         name = get_variable_from_expr(tmp->unop, &sym);
 220                         if (name) {
 221                                 set_state(name, my_id, sym, &assumed_nonnull);
 222                         }
 223                         free_string(name);
 224                 } else if (func) {
 225                         name = get_variable_from_expr(tmp, &sym);
 226                         if (name && is_maybe_null_no_arg(name, sym))
 227                                 add_param(&calls, func, i, get_lineno());
 228                         free_string(name);
 229                 }
 230                 i++;
 231         } END_FOR_EACH_PTR(tmp);
 232 }
 233
 234 static int check_null_returns(const char *name, struct symbol *sym,
 235                         struct expression *right)
 236 {
 237         int i;
 238         char *func_name;
 239
 240         func_name = get_function_call(right);
 241         if (!func_name)
 242                 return 0;
 243
 244         for(i = 0; i < sizeof(*return_null)/sizeof(return_null[0]); i++) {
 245                 if (!strcmp(func_name, return_null[i])) {
 246                         set_state(name, my_id, sym, &undefined);
 247                         return 1;
 248                 }
 249         }
 250         return 0;
 251 }
 252
 253 static int assign_seen;
 254 static void match_assign(struct expression *expr)
 255 {
 256         struct expression *left, *right;
 257         struct symbol *sym;
 258         char *name;
 259
 260         if (assign_seen) {
 261                 assign_seen--;
 262                 return;
 263         }
 264         left = strip_expr(expr->left);
 265         name = get_variable_from_expr(left, &sym);
 266         if (!name)
 267                 return;
 268         right = strip_expr(expr->right);
 269         if (is_zero(right)) {
 270                 set_state(name, my_id, sym, &isnull);
 271                 free_string(name);
 272                 return;
 273         }
 274         if (check_null_returns(name, sym, right)) {
 275                 free_string(name);
 276                 return;
 277         }
 278
 279         /* by default we assume it's assigned something nonnull */
 280         set_state(name, my_id, sym, &assumed_nonnull);
 281         free_string(name);
 282 }
 283
 284 /*
 285  * set_new_true_false_paths() is used in the following conditions
 286  * if (a) { ... if (a) { ... } }
 287  * The problem is that after the second blog a is set to undefined
 288  * even though the second condition is meaning less.  (The second test
 289  * could be a macro for example).
 290  *
 291  * Also, stuff passed to the condition hook is processed behind the scenes
 292  * a bit.  Instead of a condition like (foo == 0) which is true when foo is
 293  * null, we get just (foo) and the true and false states are adjusted later.
 294  * Basically the important thing to remember, is that for us, true is always
 295  * non null and false is always null.
 296  */
 297 static void set_new_true_false_paths(const char *name, struct symbol *sym)
 298 {
 299         struct smatch_state *tmp;
 300
 301         tmp = get_state(name, my_id, sym);
 302
 303         SM_DEBUG("set_new_stuff called at for %s on line %d value='%s'\n",
 304                 name, get_lineno(), show_state(tmp));
 305
 306         if (tmp == &argument) {
 307                 set_true_false_states(name, my_id, sym, &arg_nonnull, &arg_null);
 308                 return;
 309         }
 310
 311         if (!tmp || is_maybe_null(name, sym)) {
 312                 set_true_false_states(name, my_id, sym, &nonnull, &isnull);
 313                 return;
 314         }
 315 }
 316
 317
 318 static void match_condition(struct expression *expr)
 319 {
 320         struct symbol *sym;
 321         char *name;
 322
 323         expr = strip_expr(expr);
 324         switch(expr->type) {
 325         case EXPR_PREOP:
 326         case EXPR_SYMBOL:
 327         case EXPR_DEREF:
 328                 name = get_variable_from_expr(expr, &sym);
 329                 if (!name)
 330                         return;
 331                 set_new_true_false_paths(name, sym);
 332                 free_string(name);
 333                 return;
 334         case EXPR_ASSIGNMENT:
 335                 assign_seen++;
 336                 /*
 337                  * There is a kernel macro that does
 338                  *  for ( ... ; ... || x = NULL ; ) ...
 339                  */
 340                 if (is_zero(expr->right)) {
 341                         name = get_variable_from_expr(expr->left, &sym);
 342                         if (!name)
 343                                 return;
 344                         set_true_false_states(name, my_id, sym, NULL, &isnull);
 345                         free_string(name);
 346                         return;
 347                 }
 348                  /* You have to deal with stuff like if (a = b = c) */
 349                 match_condition(expr->right);
 350                 match_condition(expr->left);
 351                 return;
 352         default:
 353                 return;
 354         }
 355 }
 356
 357 static void match_declarations(struct symbol *sym)
 358 {
 359         const char *name;
 360
 361         if ((get_base_type(sym))->type == SYM_ARRAY) {
 362                 return;
 363         }
 364
 365         name = sym->ident->name;
 366
 367         if (sym->initializer) {
 368                 if (is_zero(sym->initializer)) {
 369                         set_state(name, my_id, sym, &isnull);
 370                         return;
 371                 }
 372                 if (check_null_returns(name, sym, strip_expr(sym->initializer)))
 373                         return;
 374                 set_state(name, my_id, sym, &assumed_nonnull);
 375         } else {
 376                 set_state(name, my_id, sym, &undefined);
 377         }
 378 }
 379
 380 static void match_dereferences(struct expression *expr)
 381 {
 382         char *deref = NULL;
 383         struct symbol *sym = NULL;
 384
 385         if (strcmp(show_special(expr->deref->op), "*"))
 386                 return;
 387
 388         deref = get_variable_from_expr(expr->deref->unop, &sym);
 389         if (!deref)
 390                 return;
 391
 392         if (is_maybe_null_arg(deref, sym)) {
 393                 add_do_not_call(sym, get_lineno());
 394                 set_state(deref, my_id, sym, &assumed_nonnull);
 395         } else if  (is_maybe_null(deref, sym)) {
 396                 smatch_msg("error: dereferencing undefined:  '%s'", deref);
 397                 set_state(deref, my_id, sym, &ignore);
 398         }
 399         free_string(deref);
 400 }
 401
 402 static void end_file_processing()
 403 {
 404         struct func_n_param *param1, *param2;
 405
 406         // if a function is not static print it out...
 407         FOR_EACH_PTR(do_not_call, param1) {
 408                 if (!(param1->func->ctype.modifiers & MOD_STATIC))
 409                         printf("%s +%d info: unchecked param %s %d\n",
 410                                get_filename(), param1->line,
 411                                param1->func->ident->name, param1->param);
 412         } END_FOR_EACH_PTR(param1);
 413
 414         // if there is an error print it out...
 415         FOR_EACH_PTR(calls, param1) {
 416                 FOR_EACH_PTR(do_not_call, param2) {
 417                         if (param1->func == param2->func &&
 418                             param1->param == param2->param)
 419                                 printf("%s +%d error: cross_func deref %s %d\n",
 420                                        get_filename(), param1->line,
 421                                        param1->func->ident->name,
 422                                        param1->param);
 423                 } END_FOR_EACH_PTR(param2);
 424         } END_FOR_EACH_PTR(param1);
 425
 426         // if someone calls a non-static function print that..
 427         FOR_EACH_PTR(calls, param1) {
 428                 int defined = 0;
 429
 430                 FOR_EACH_PTR(funcs, param2) {
 431                         if (param1->func == param2->func)
 432                                 defined = 1;
 433                 } END_FOR_EACH_PTR(param2);
 434                 if (!defined)
 435                         printf("%s +%d info: undefined param %s %d\n",
 436                                get_filename(), param1->line,
 437                                param1->func->ident->name, param1->param);
 438         } END_FOR_EACH_PTR(param1);
 439 }
 440
 441 void register_null_deref(int id)
 442 {
 443         my_id = id;
 444         add_merge_hook(my_id, &merge_func);
 445         add_hook(&match_function_def, FUNC_DEF_HOOK);
 446         add_hook(&match_function_call_after, FUNCTION_CALL_AFTER_HOOK);
 447         add_hook(&match_assign, ASSIGNMENT_AFTER_HOOK);
 448         add_hook(&match_condition, CONDITION_HOOK);
 449         add_hook(&match_dereferences, DEREF_HOOK);
 450         add_hook(&match_declarations, DECLARATION_HOOK);
 451         add_hook(&end_file_processing, END_FILE_HOOK);
 452 }