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 int assign_seen;
 143 static int handle_double_assign(struct expression *expr)
 144 {
 145         struct symbol *sym;
 146         char *name;
 147
 148         if (expr->right->type != EXPR_ASSIGNMENT)
 149                 return 0;
 150         assign_seen++;
 151
 152         name = get_variable_from_expr_complex(expr->left, &sym);
 153         if (name && is_parent(expr->left))
 154                 assign_parent(sym);
 155
 156         name = get_variable_from_expr_complex(expr->right->left, &sym);
 157         if (name && is_parent(expr->right->left))
 158                 assign_parent(sym);
 159
 160         name = get_variable_from_expr_complex(expr->right->right, &sym);
 161         if (name && is_parent(expr->right->right))
 162                 assign_parent(sym);
 163
 164         return 1;
 165 }
 166
 167 static void match_assign(struct expression *expr)
 168 {
 169         struct expression *left, *right;
 170         char *left_name = NULL;
 171         char *right_name = NULL;
 172         struct symbol *left_sym, *right_sym;
 173         struct smatch_state *state;
 174
 175         if (assign_seen) {
 176                 assign_seen--;
 177                 return;
 178         }
 179
 180         if (handle_double_assign(expr)) {
 181                 return;
 182         }
 183
 184         left = strip_expr(expr->left);
 185         left_name = get_variable_from_expr_complex(left, &left_sym);
 186
 187         right = strip_expr(expr->right);
 188         if (left_name && left_sym && is_allocation(right) &&
 189             !(left_sym->ctype.modifiers &
 190               (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE)) &&
 191             !parent_is_assigned(left_sym)) {
 192                 set_state(left_name, my_id, left_sym, &malloced);
 193                 goto exit;
 194         }
 195
 196         right_name = get_variable_from_expr_complex(right, &right_sym);
 197
 198         if (right_name && (state = get_state(right_name, my_id, right_sym))) {
 199                 if (state == &isfree)
 200                         smatch_msg("error: assigning freed pointer");
 201                 set_state(right_name, my_id, right_sym, &assigned);
 202         }
 203
 204         if (is_freed(left_name, left_sym)) {
 205                 set_state(left_name, my_id, left_sym, &unfree);
 206         }
 207         if (left_name && is_parent(left))
 208                 assign_parent(left_sym);
 209         if (right_name && is_parent(right))
 210                 assign_parent(right_sym);
 211 exit:
 212         free_string(left_name);
 213         free_string(right_name);
 214 }
 215
 216 static int is_null(char *name, struct symbol *sym)
 217 {
 218         struct smatch_state *state;
 219
 220         state = get_state(name, my_id, sym);
 221         if (state && !strcmp(state->name, "isnull"))
 222                 return 1;
 223         return 0;
 224 }
 225
 226 static void match_free_func(struct expression *expr, void *data)
 227 {
 228         struct expression *ptr_expr;
 229         char *ptr_name;
 230         struct symbol *ptr_sym;
 231         int arg_num = (int)data;
 232
 233         ptr_expr = get_argument_from_call_expr(expr->args, arg_num);
 234         ptr_name = get_variable_from_expr_complex(ptr_expr, &ptr_sym);
 235         if (is_freed(ptr_name, ptr_sym) && !is_null(ptr_name, ptr_sym)) {
 236                 smatch_msg("error: double free of %s", ptr_name);
 237         }
 238         set_state(ptr_name, my_id, ptr_sym, &isfree);
 239         free_string(ptr_name);
 240 }
 241
 242 static int possibly_allocated(struct state_list *slist)
 243 {
 244         struct sm_state *tmp;
 245
 246         FOR_EACH_PTR(slist, tmp) {
 247                 if (tmp->state == &allocated)
 248                         return 1;
 249                 if (tmp->state == &malloced)
 250                         return 1;
 251         } END_FOR_EACH_PTR(tmp);
 252         return 0;
 253 }
 254
 255 static void check_for_allocated(void)
 256 {
 257         struct state_list *slist;
 258         struct sm_state *tmp;
 259
 260         slist = get_all_states(my_id);
 261         FOR_EACH_PTR(slist, tmp) {
 262                 if (possibly_allocated(tmp->possible) &&
 263                     !is_null(tmp->name, tmp->sym) &&
 264                     !is_argument(tmp->sym) &&
 265                     !parent_is_assigned(tmp->sym))
 266                         smatch_msg("error: memery leak of %s", tmp->name);
 267         } END_FOR_EACH_PTR(tmp);
 268         free_slist(&slist);
 269 }
 270
 271 static void match_return(struct statement *stmt)
 272 {
 273         char *name;
 274         struct symbol *sym;
 275
 276         name = get_variable_from_expr_complex(stmt->ret_value, &sym);
 277         if (sym)
 278                 assign_parent(sym);
 279         free_string(name);
 280         check_for_allocated();
 281 }
 282
 283 static void set_new_true_false_paths(const char *name, struct symbol *sym)
 284 {
 285         struct smatch_state *tmp;
 286
 287         tmp = get_state(name, my_id, sym);
 288
 289         if (!tmp) {
 290                 return;
 291         }
 292
 293         if (tmp == &isfree) {
 294                 smatch_msg("warn: why do you care about freed memory?");
 295         }
 296
 297         if (tmp == &assigned) {
 298                 /* we don't care about assigned pointers any more */
 299                 return;
 300         }
 301         set_true_false_states(name, my_id, sym, &allocated, &isnull);
 302 }
 303
 304 static void match_condition(struct expression *expr)
 305 {
 306         struct symbol *sym;
 307         char *name;
 308
 309         expr = strip_expr(expr);
 310         switch(expr->type) {
 311         case EXPR_PREOP:
 312         case EXPR_SYMBOL:
 313         case EXPR_DEREF:
 314                 name = get_variable_from_expr_complex(expr, &sym);
 315                 if (!name)
 316                         return;
 317                 set_new_true_false_paths(name, sym);
 318                 free_string(name);
 319                 return;
 320         case EXPR_ASSIGNMENT:
 321                 assign_seen++;
 322                  /* You have to deal with stuff like if (a = b = c) */
 323                 match_condition(expr->right);
 324                 match_condition(expr->left);
 325                 return;
 326         default:
 327                 return;
 328         }
 329 }
 330
 331 static void match_function_call(struct expression *expr)
 332 {
 333         struct expression *tmp;
 334         struct symbol *sym;
 335         char *name;
 336         char *fn_name;
 337         struct sm_state *state;
 338
 339         fn_name = get_variable_from_expr(expr->fn, NULL);
 340
 341         FOR_EACH_PTR(expr->args, tmp) {
 342                 tmp = strip_expr(tmp);
 343                 name = get_variable_from_expr_complex(tmp, &sym);
 344                 if (!name)
 345                         continue;
 346                 if ((state = get_sm_state(name, my_id, sym))) {
 347                         if (possibly_allocated(state->possible)) {
 348                                 set_state(name, my_id, sym, &assigned);
 349                         }
 350                 }
 351                 assign_parent(sym);
 352         } END_FOR_EACH_PTR(tmp);
 353 }
 354
 355 static void match_dereferences(struct expression *expr)
 356 {
 357         char *deref = NULL;
 358         struct symbol *sym = NULL;
 359
 360         deref = get_variable_from_expr(expr->deref->unop, &sym);
 361         if (!deref)
 362                 return;
 363         if (is_freed(deref, sym)) {
 364                 smatch_msg("error: dereferencing freed memory '%s'\n", deref);
 365                 set_state(deref, my_id, sym, &unfree);
 366         }
 367         free_string(deref);
 368 }
 369
 370 static void match_end_func(struct symbol *sym)
 371 {
 372         check_for_allocated();
 373         free_trackers_and_list(&arguments);
 374 }
 375
 376 static void register_funcs_from_file(void)
 377 {
 378         const char *filename = "frees";
 379         int fd;
 380         struct token *token;
 381         const char *func;
 382         int arg;
 383
 384         fd = open(filename, O_RDONLY);
 385         if (fd < 0)
 386                 return;
 387         token = tokenize(filename, fd, NULL, NULL);
 388         close(fd);
 389         if (token_type(token) != TOKEN_STREAMBEGIN)
 390                 return;
 391         token = token->next;
 392         while (token_type(token) != TOKEN_STREAMEND) {
 393                 if (token_type(token) != TOKEN_IDENT)
 394                         return;
 395                 func = show_ident(token->ident);
 396                 token = token->next;
 397                 if (token_type(token) != TOKEN_NUMBER)
 398                         return;
 399                 arg = atoi(token->number);
 400                 add_function_hook(func, &match_free_func, (void *)arg);
 401                 token = token->next;
 402         }
 403         clear_token_alloc();
 404 }
 405
 406 void check_memory(int id)
 407 {
 408         my_id = id;
 409         add_unmatched_state_hook(my_id, &unmatched_state);
 410         add_hook(&match_function_def, FUNC_DEF_HOOK);
 411         add_hook(&match_declarations, DECLARATION_HOOK);
 412         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 413         add_hook(&match_condition, CONDITION_HOOK);
 414         add_hook(&match_dereferences, DEREF_HOOK);
 415         add_hook(&match_assign, ASSIGNMENT_HOOK);
 416         add_hook(&match_return, RETURN_HOOK);
 417         add_hook(&match_end_func, END_FUNC_HOOK);
 418         add_function_hook("kfree", &match_free_func, (void *)0);
 419         register_funcs_from_file();
 420 }