check_memory.c

   1 /*
   2  * sparse/check_memory.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <fcntl.h>
  11 #include <unistd.h>
  12 #include "parse.h"
  13 #include "smatch.h"
  14 #include "smatch_slist.h"
  15
  16 static int my_id;
  17
  18 STATE(allocated);
  19 STATE(assigned);
  20 STATE(isfree);
  21 STATE(malloced);
  22 STATE(isnull);
  23 STATE(unfree);
  24
  25 /*
  26   malloced --> allocated --> assigned --> isfree +
  27             \-> isnull.    \-> isfree +
  28
  29   isfree --> unfree.
  30           \-> isnull.
  31 */
  32
  33 static struct tracker_list *arguments;
  34
  35 static const char *allocation_funcs[] = {
  36         "malloc",
  37         "kmalloc",
  38         "kzalloc",
  39         NULL,
  40 };
  41
  42 static struct smatch_state *unmatched_state(struct sm_state *sm)
  43 {
  44         if (!strcmp(sm->name, "-"))
  45                 return &assigned;
  46         return &undefined;
  47 }
  48
  49 static void assign_parent(struct symbol *sym)
  50 {
  51         set_state("-", my_id, sym, &assigned);
  52 }
  53
  54 static int parent_is_assigned(struct symbol *sym)
  55 {
  56         struct smatch_state *state;
  57
  58         state = get_state("-", my_id, sym);
  59         if (state == &assigned)
  60                 return 1;
  61         return 0;
  62 }
  63
  64 static int is_allocation(struct expression *expr)
  65 {
  66         char *fn_name;
  67         int i;
  68
  69         if (expr->type != EXPR_CALL)
  70                 return 0;
  71
  72         if (!(fn_name = get_variable_from_expr(expr->fn, NULL)))
  73                 return 0;
  74
  75         for (i = 0; allocation_funcs[i]; i++) {
  76                 if (!strcmp(fn_name, allocation_funcs[i])) {
  77                         free_string(fn_name);
  78                         return 1;
  79                 }
  80         }
  81         free_string(fn_name);
  82         return 0;
  83 }
  84
  85 static int is_freed(const char *name, struct symbol *sym)
  86 {
  87         struct state_list *slist;
  88
  89         slist = get_possible_states(name, my_id, sym);
  90         if (slist_has_state(slist, &isfree)) {
  91                 return 1;
  92         }
  93         return 0;
  94 }
  95
  96 static int is_argument(struct symbol *sym)
  97 {
  98         struct tracker *arg;
  99
 100         FOR_EACH_PTR(arguments, arg) {
 101                 if (arg->sym == sym)
 102                         return 1;
 103         } END_FOR_EACH_PTR(arg);
 104         return 0;
 105 }
 106
 107 static void match_function_def(struct symbol *sym)
 108 {
 109         struct symbol *arg;
 110
 111         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 112                 add_tracker(&arguments, (arg->ident?arg->ident->name:"NULL"), my_id, arg);
 113         } END_FOR_EACH_PTR(arg);
 114 }
 115
 116 static void match_declarations(struct symbol *sym)
 117 {
 118         const char *name;
 119
 120         if ((get_base_type(sym))->type == SYM_ARRAY) {
 121                 return;
 122         }
 123
 124         name = sym->ident->name;
 125
 126         if (sym->initializer) {
 127                 if (is_allocation(sym->initializer)) {
 128                         set_state(name, my_id, sym, &malloced);
 129                 } else {
 130                         assign_parent(sym);
 131                 }
 132         }
 133 }
 134
 135 static int is_parent(struct expression *expr)
 136 {
 137         if (expr->type == EXPR_DEREF)
 138                 return 0;
 139         return 1;
 140 }
 141
 142 static void match_assign(struct expression *expr)
 143 {
 144         struct expression *left, *right;
 145         char *left_name = NULL;
 146         char *right_name = NULL;
 147         struct symbol *left_sym, *right_sym;
 148         struct smatch_state *state;
 149
 150         left = strip_expr(expr->left);
 151         left_name = get_variable_from_expr_complex(left, &left_sym);
 152
 153         right = strip_expr(expr->right);
 154         if (left_name && left_sym && is_allocation(right) &&
 155             !(left_sym->ctype.modifiers &
 156               (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE)) &&
 157             !parent_is_assigned(left_sym)) {
 158                 set_state(left_name, my_id, left_sym, &malloced);
 159                 goto exit;
 160         }
 161
 162         right_name = get_variable_from_expr_complex(right, &right_sym);
 163
 164         if (right_name && (state = get_state(right_name, my_id, right_sym))) {
 165                 if (state == &isfree)
 166                         smatch_msg("error: assigning freed pointer");
 167                 set_state(right_name, my_id, right_sym, &assigned);
 168         }
 169
 170         if (is_freed(left_name, left_sym)) {
 171                 set_state(left_name, my_id, left_sym, &unfree);
 172         }
 173         if (left_name && is_parent(left))
 174                 assign_parent(left_sym);
 175         if (right_name && is_parent(right))
 176                 assign_parent(right_sym);
 177 exit:
 178         free_string(left_name);
 179         free_string(right_name);
 180 }
 181
 182 static int is_null(const char *name, struct symbol *sym)
 183 {
 184         struct smatch_state *state;
 185
 186         state = get_state(name, my_id, sym);
 187         if (state && !strcmp(state->name, "isnull"))
 188                 return 1;
 189         return 0;
 190 }
 191
 192 static void match_free_func(const char *fn, struct expression *expr, void *data)
 193 {
 194         struct expression *ptr_expr;
 195         char *ptr_name;
 196         struct symbol *ptr_sym;
 197         int arg_num = (int)data;
 198
 199         ptr_expr = get_argument_from_call_expr(expr->args, arg_num);
 200         ptr_name = get_variable_from_expr_complex(ptr_expr, &ptr_sym);
 201         if (is_freed(ptr_name, ptr_sym) && !is_null(ptr_name, ptr_sym)) {
 202                 smatch_msg("error: double free of %s", ptr_name);
 203         }
 204         set_state(ptr_name, my_id, ptr_sym, &isfree);
 205         free_string(ptr_name);
 206 }
 207
 208 static int possibly_allocated(struct state_list *slist)
 209 {
 210         struct sm_state *tmp;
 211
 212         FOR_EACH_PTR(slist, tmp) {
 213                 if (tmp->state == &allocated)
 214                         return 1;
 215                 if (tmp->state == &malloced)
 216                         return 1;
 217         } END_FOR_EACH_PTR(tmp);
 218         return 0;
 219 }
 220
 221 static void check_for_allocated(void)
 222 {
 223         struct state_list *slist;
 224         struct sm_state *tmp;
 225
 226         slist = get_all_states(my_id);
 227         FOR_EACH_PTR(slist, tmp) {
 228                 if (possibly_allocated(tmp->possible) &&
 229                     !is_null(tmp->name, tmp->sym) &&
 230                     !is_argument(tmp->sym) &&
 231                     !parent_is_assigned(tmp->sym))
 232                         smatch_msg("error: memery leak of %s", tmp->name);
 233         } END_FOR_EACH_PTR(tmp);
 234         free_slist(&slist);
 235 }
 236
 237 static void match_return(struct statement *stmt)
 238 {
 239         char *name;
 240         struct symbol *sym;
 241
 242         name = get_variable_from_expr_complex(stmt->ret_value, &sym);
 243         if (sym)
 244                 assign_parent(sym);
 245         free_string(name);
 246         check_for_allocated();
 247 }
 248
 249 static void set_new_true_false_paths(const char *name, struct symbol *sym)
 250 {
 251         struct smatch_state *tmp;
 252
 253         tmp = get_state(name, my_id, sym);
 254
 255         if (!tmp) {
 256                 return;
 257         }
 258
 259         if (tmp == &isfree) {
 260                 smatch_msg("warn: why do you care about freed memory?");
 261         }
 262
 263         if (tmp == &assigned) {
 264                 /* we don't care about assigned pointers any more */
 265                 return;
 266         }
 267         set_true_false_states(name, my_id, sym, &allocated, &isnull);
 268 }
 269
 270 static void match_condition(struct expression *expr)
 271 {
 272         struct symbol *sym;
 273         char *name;
 274
 275         expr = strip_expr(expr);
 276         switch(expr->type) {
 277         case EXPR_PREOP:
 278         case EXPR_SYMBOL:
 279         case EXPR_DEREF:
 280                 name = get_variable_from_expr_complex(expr, &sym);
 281                 if (!name)
 282                         return;
 283                 set_new_true_false_paths(name, sym);
 284                 free_string(name);
 285                 return;
 286         case EXPR_ASSIGNMENT:
 287                  /* You have to deal with stuff like if (a = b = c) */
 288                 match_condition(expr->right);
 289                 match_condition(expr->left);
 290                 return;
 291         default:
 292                 return;
 293         }
 294 }
 295
 296 static void match_function_call(struct expression *expr)
 297 {
 298         struct expression *tmp;
 299         struct symbol *sym;
 300         char *name;
 301         struct sm_state *state;
 302
 303         FOR_EACH_PTR(expr->args, tmp) {
 304                 tmp = strip_expr(tmp);
 305                 name = get_variable_from_expr_complex(tmp, &sym);
 306                 if (!name)
 307                         continue;
 308                 if ((state = get_sm_state(name, my_id, sym))) {
 309                         if (possibly_allocated(state->possible)) {
 310                                 set_state(name, my_id, sym, &assigned);
 311                         }
 312                 }
 313                 assign_parent(sym);
 314                 free_string(name);
 315         } END_FOR_EACH_PTR(tmp);
 316 }
 317
 318 static void match_dereferences(struct expression *expr)
 319 {
 320         char *deref = NULL;
 321         struct symbol *sym = NULL;
 322
 323         deref = get_variable_from_expr(expr->deref->unop, &sym);
 324         if (!deref)
 325                 return;
 326         if (is_freed(deref, sym)) {
 327                 smatch_msg("error: dereferencing freed memory '%s'", deref);
 328                 set_state(deref, my_id, sym, &unfree);
 329         }
 330         free_string(deref);
 331 }
 332
 333 static void match_end_func(struct symbol *sym)
 334 {
 335         check_for_allocated();
 336         free_trackers_and_list(&arguments);
 337 }
 338
 339 static void register_funcs_from_file(void)
 340 {
 341         struct token *token;
 342         const char *func;
 343         int arg;
 344
 345         token = get_tokens_file("kernel.frees_argument");
 346         if (!token)
 347                 return;
 348         if (token_type(token) != TOKEN_STREAMBEGIN)
 349                 return;
 350         token = token->next;
 351         while (token_type(token) != TOKEN_STREAMEND) {
 352                 if (token_type(token) != TOKEN_IDENT)
 353                         return;
 354                 func = show_ident(token->ident);
 355                 token = token->next;
 356                 if (token_type(token) != TOKEN_NUMBER)
 357                         return;
 358                 arg = atoi(token->number);
 359                 add_function_hook(func, &match_free_func, (void *)arg);
 360                 token = token->next;
 361         }
 362         clear_token_alloc();
 363 }
 364
 365 void check_memory(int id)
 366 {
 367         my_id = id;
 368         add_unmatched_state_hook(my_id, &unmatched_state);
 369         add_hook(&match_function_def, FUNC_DEF_HOOK);
 370         add_hook(&match_declarations, DECLARATION_HOOK);
 371         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 372         add_hook(&match_condition, CONDITION_HOOK);
 373         add_hook(&match_dereferences, DEREF_HOOK);
 374         add_hook(&match_assign, ASSIGNMENT_HOOK);
 375         add_hook(&match_return, RETURN_HOOK);
 376         add_hook(&match_end_func, END_FUNC_HOOK);
 377         add_function_hook("kfree", &match_free_func, (void *)0);
 378         register_funcs_from_file();
 379 }