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