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