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