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 char *get_parent_name(struct symbol *sym)
  43 {
  44         static char buf[256];
  45
  46         if (!sym || !sym->ident)
  47                 return NULL;
  48
  49         snprintf(buf, 255, "-%s", sym->ident->name);
  50         buf[255] = '\0';
  51         return alloc_string(buf);
  52 }
  53
  54 static int is_parent_sym(const char *name)
  55 {
  56         if (!strncmp(name, "-", 1))
  57                 return 1;
  58         return 0;
  59 }
  60
  61 static struct smatch_state *unmatched_state(struct sm_state *sm)
  62 {
  63         if (is_parent_sym(sm->name))
  64                 return &assigned;
  65         return &undefined;
  66 }
  67
  68 static void assign_parent(struct symbol *sym)
  69 {
  70         char *name;
  71
  72         name = get_parent_name(sym);
  73         if (!name)
  74                 return;
  75         set_state(my_id, name, sym, &assigned);
  76         free_string(name);
  77 }
  78
  79 static int parent_is_assigned(struct symbol *sym)
  80 {
  81         struct smatch_state *state;
  82         char *name;
  83
  84         name = get_parent_name(sym);
  85         if (!name)
  86                 return 0;
  87         state = get_state(my_id, name, sym);
  88         free_string(name);
  89         if (state == &assigned)
  90                 return 1;
  91         return 0;
  92 }
  93
  94 static int is_allocation(struct expression *expr)
  95 {
  96         char *fn_name;
  97         int i;
  98
  99         if (expr->type != EXPR_CALL)
 100                 return 0;
 101
 102         if (!(fn_name = get_variable_from_expr(expr->fn, NULL)))
 103                 return 0;
 104
 105         for (i = 0; allocation_funcs[i]; i++) {
 106                 if (!strcmp(fn_name, allocation_funcs[i])) {
 107                         free_string(fn_name);
 108                         return 1;
 109                 }
 110         }
 111         free_string(fn_name);
 112         return 0;
 113 }
 114
 115 static int is_freed(const char *name, struct symbol *sym)
 116 {
 117         struct state_list *slist;
 118
 119         slist = get_possible_states(my_id, name, sym);
 120         if (slist_has_state(slist, &isfree)) {
 121                 return 1;
 122         }
 123         return 0;
 124 }
 125
 126 static int is_argument(struct symbol *sym)
 127 {
 128         struct tracker *arg;
 129
 130         FOR_EACH_PTR(arguments, arg) {
 131                 if (arg->sym == sym)
 132                         return 1;
 133         } END_FOR_EACH_PTR(arg);
 134         return 0;
 135 }
 136
 137 static void match_function_def(struct symbol *sym)
 138 {
 139         struct symbol *arg;
 140
 141         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 142                 add_tracker(&arguments, my_id, (arg->ident?arg->ident->name:"NULL"), arg);
 143         } END_FOR_EACH_PTR(arg);
 144 }
 145
 146 static int is_parent(struct expression *expr)
 147 {
 148         if (expr->type == EXPR_DEREF)
 149                 return 0;
 150         return 1;
 151 }
 152
 153 static void match_assign(struct expression *expr)
 154 {
 155         struct expression *left, *right;
 156         char *left_name = NULL;
 157         char *right_name = NULL;
 158         struct symbol *left_sym, *right_sym;
 159         struct smatch_state *state;
 160
 161         left = strip_expr(expr->left);
 162         left_name = get_variable_from_expr_complex(left, &left_sym);
 163
 164         right = strip_expr(expr->right);
 165         if (left_name && left_sym && is_allocation(right) &&
 166             !(left_sym->ctype.modifiers &
 167               (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE)) &&
 168             !parent_is_assigned(left_sym)) {
 169                 set_state(my_id, left_name, left_sym, &malloced);
 170                 goto exit;
 171         }
 172
 173         right_name = get_variable_from_expr_complex(right, &right_sym);
 174
 175         if (right_name && (state = get_state(my_id, right_name, right_sym))) {
 176                 if (state == &isfree)
 177                         sm_msg("error: assigning freed pointer");
 178                 set_state(my_id, right_name, right_sym, &assigned);
 179         }
 180
 181         if (is_freed(left_name, left_sym)) {
 182                 set_state(my_id, left_name, left_sym, &unfree);
 183         }
 184         if (left_name && is_parent(left))
 185                 assign_parent(left_sym);
 186         if (right_name && is_parent(right))
 187                 assign_parent(right_sym);
 188 exit:
 189         free_string(left_name);
 190         free_string(right_name);
 191 }
 192
 193 static int is_null(const char *name, struct symbol *sym)
 194 {
 195         struct smatch_state *state;
 196
 197         state = get_state(my_id, name, sym);
 198         if (state && !strcmp(state->name, "isnull"))
 199                 return 1;
 200         return 0;
 201 }
 202
 203 static void set_unfree(const char *name, struct symbol *sym, struct expression *expr, void *unused)
 204 {
 205         set_state(my_id, name, sym, &unfree);
 206 }
 207
 208 static void match_free_func(const char *fn, struct expression *expr, void *data)
 209 {
 210         struct expression *ptr_expr;
 211         char *ptr_name;
 212         struct symbol *ptr_sym;
 213         int arg_num = PTR_INT(data);
 214
 215         ptr_expr = get_argument_from_call_expr(expr->args, arg_num);
 216         ptr_name = get_variable_from_expr_complex(ptr_expr, &ptr_sym);
 217         if (!ptr_name)
 218                 return;
 219         if (is_freed(ptr_name, ptr_sym) && !is_null(ptr_name, ptr_sym)) {
 220                 sm_msg("error: double free of %s", ptr_name);
 221         }
 222         set_state(my_id, ptr_name, ptr_sym, &isfree);
 223         add_modification_hook(ptr_name, &set_unfree, NULL);
 224         free_string(ptr_name);
 225 }
 226
 227 static int possibly_allocated(struct state_list *slist)
 228 {
 229         struct sm_state *tmp;
 230
 231         FOR_EACH_PTR(slist, tmp) {
 232                 if (tmp->state == &allocated)
 233                         return 1;
 234                 if (tmp->state == &malloced)
 235                         return 1;
 236         } END_FOR_EACH_PTR(tmp);
 237         return 0;
 238 }
 239
 240 static void check_sm_is_leaked(struct sm_state *sm)
 241 {
 242         if (possibly_allocated(sm->possible) &&
 243                 !is_null(sm->name, sm->sym) &&
 244                 !is_argument(sm->sym) &&
 245                 !parent_is_assigned(sm->sym))
 246                 sm_msg("error: memory leak of %s", sm->name);
 247 }
 248
 249 static void check_tracker_is_leaked(struct tracker *t)
 250 {
 251         struct sm_state *sm;
 252
 253         sm = get_sm_state(t->owner, t->name, t->sym);
 254         if (sm)
 255                 check_sm_is_leaked(sm);
 256         __free_tracker(t);
 257 }
 258
 259 static void match_declarations(struct symbol *sym)
 260 {
 261         const char *name;
 262
 263         if ((get_base_type(sym))->type == SYM_ARRAY) {
 264                 return;
 265         }
 266
 267         name = sym->ident->name;
 268
 269         if (sym->initializer) {
 270                 if (is_allocation(sym->initializer)) {
 271                         set_state(my_id, name, sym, &malloced);
 272                         add_scope_hook((scope_hook *)&check_tracker_is_leaked,
 273                                 alloc_tracker(my_id, name, sym));
 274                         scoped_state(my_id, name, sym);
 275                 } else {
 276                         assign_parent(sym);
 277                 }
 278         }
 279 }
 280
 281 static void check_for_allocated(void)
 282 {
 283         struct state_list *slist;
 284         struct sm_state *tmp;
 285
 286         slist = get_all_states(my_id);
 287         FOR_EACH_PTR(slist, tmp) {
 288                 check_sm_is_leaked(tmp);
 289         } END_FOR_EACH_PTR(tmp);
 290         free_slist(&slist);
 291 }
 292
 293 static void match_return(struct expression *ret_value)
 294 {
 295         char *name;
 296         struct symbol *sym;
 297
 298         name = get_variable_from_expr_complex(ret_value, &sym);
 299         if (sym)
 300                 assign_parent(sym);
 301         free_string(name);
 302         check_for_allocated();
 303 }
 304
 305 static void set_new_true_false_paths(const char *name, struct symbol *sym)
 306 {
 307         struct smatch_state *tmp;
 308
 309         tmp = get_state(my_id, name, sym);
 310
 311         if (!tmp) {
 312                 return;
 313         }
 314
 315         if (tmp == &isfree) {
 316                 sm_msg("warn: why do you care about freed memory?");
 317         }
 318
 319         if (tmp == &assigned) {
 320                 /* we don't care about assigned pointers any more */
 321                 return;
 322         }
 323         set_true_false_states(my_id, name, sym, &allocated, &isnull);
 324 }
 325
 326 static void match_condition(struct expression *expr)
 327 {
 328         struct symbol *sym;
 329         char *name;
 330
 331         expr = strip_expr(expr);
 332         switch(expr->type) {
 333         case EXPR_PREOP:
 334         case EXPR_SYMBOL:
 335         case EXPR_DEREF:
 336                 name = get_variable_from_expr_complex(expr, &sym);
 337                 if (!name)
 338                         return;
 339                 set_new_true_false_paths(name, sym);
 340                 free_string(name);
 341                 return;
 342         case EXPR_ASSIGNMENT:
 343                  /* You have to deal with stuff like if (a = b = c) */
 344                 match_condition(expr->right);
 345                 match_condition(expr->left);
 346                 return;
 347         default:
 348                 return;
 349         }
 350 }
 351
 352 static void match_function_call(struct expression *expr)
 353 {
 354         struct expression *tmp;
 355         struct symbol *sym;
 356         char *name;
 357         struct sm_state *state;
 358
 359         FOR_EACH_PTR(expr->args, tmp) {
 360                 tmp = strip_expr(tmp);
 361                 name = get_variable_from_expr_complex(tmp, &sym);
 362                 if (!name)
 363                         continue;
 364                 if ((state = get_sm_state(my_id, name, sym))) {
 365                         if (possibly_allocated(state->possible)) {
 366                                 set_state(my_id, name, sym, &assigned);
 367                         }
 368                 }
 369                 assign_parent(sym);
 370                 free_string(name);
 371         } END_FOR_EACH_PTR(tmp);
 372 }
 373
 374 static void match_dereferences(struct expression *expr)
 375 {
 376         char *deref = NULL;
 377         struct symbol *sym = NULL;
 378
 379         if (expr->type != EXPR_PREOP)
 380                 return;
 381         expr = strip_expr(expr->unop);
 382
 383         deref = get_variable_from_expr(expr, &sym);
 384         if (!deref)
 385                 return;
 386         if (is_freed(deref, sym)) {
 387                 sm_msg("error: dereferencing freed memory '%s'", deref);
 388                 set_state(my_id, deref, sym, &unfree);
 389         }
 390         free_string(deref);
 391 }
 392
 393 static void match_end_func(struct symbol *sym)
 394 {
 395         check_for_allocated();
 396         free_trackers_and_list(&arguments);
 397 }
 398
 399 static void register_funcs_from_file(void)
 400 {
 401         struct token *token;
 402         const char *func;
 403         int arg;
 404
 405         token = get_tokens_file("kernel.frees_argument");
 406         if (!token)
 407                 return;
 408         if (token_type(token) != TOKEN_STREAMBEGIN)
 409                 return;
 410         token = token->next;
 411         while (token_type(token) != TOKEN_STREAMEND) {
 412                 if (token_type(token) != TOKEN_IDENT)
 413                         return;
 414                 func = show_ident(token->ident);
 415                 token = token->next;
 416                 if (token_type(token) != TOKEN_NUMBER)
 417                         return;
 418                 arg = atoi(token->number);
 419                 add_function_hook(func, &match_free_func, INT_PTR(arg));
 420                 token = token->next;
 421         }
 422         clear_token_alloc();
 423 }
 424
 425 void check_memory(int id)
 426 {
 427         my_id = id;
 428         add_unmatched_state_hook(my_id, &unmatched_state);
 429         add_hook(&match_function_def, FUNC_DEF_HOOK);
 430         add_hook(&match_declarations, DECLARATION_HOOK);
 431         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 432         add_hook(&match_condition, CONDITION_HOOK);
 433         add_hook(&match_dereferences, DEREF_HOOK);
 434         add_hook(&match_assign, ASSIGNMENT_HOOK);
 435         add_hook(&match_return, RETURN_HOOK);
 436         add_hook(&match_end_func, END_FUNC_HOOK);
 437         if (option_project == PROJ_KERNEL)
 438                 add_function_hook("kfree", &match_free_func, (void *)0);
 439         else
 440                 add_function_hook("free", &match_free_func, (void *)0);
 441         register_funcs_from_file();
 442 }