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