check_memory.c

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