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 "parse.h"
  11 #include "smatch.h"
  12 #include "smatch_slist.h"
  13
  14 static int my_id;
  15
  16 STATE(allocated);
  17 STATE(assigned);
  18 STATE(isfree);
  19 STATE(malloced);
  20 STATE(isnull);
  21 STATE(unfree);
  22
  23 /*
  24   malloced --> allocated --> assigned --> isfree +
  25             \-> isnull.    \-> isfree +
  26
  27   isfree --> unfree.
  28           \-> isnull.
  29 */
  30
  31 struct tracker_list *arguments;
  32
  33 /* If we pass a parent to a function that sets all the
  34    children to assigned.  frob(x) means x->data is assigned. */
  35 struct parent {
  36         struct symbol *sym;
  37         struct tracker_list *children;
  38 };
  39 ALLOCATOR(parent, "parents");
  40 DECLARE_PTR_LIST(parent_list, struct parent);
  41 static struct parent_list *parents;
  42
  43 static const char *allocation_funcs[] = {
  44         "malloc",
  45         "kmalloc",
  46         NULL,
  47 };
  48
  49 static void add_parent_to_parents(char *name, struct symbol *sym)
  50 {
  51         struct parent *tmp;
  52
  53         FOR_EACH_PTR(parents, tmp) {
  54                 if (tmp->sym == sym) {
  55                         add_tracker(&tmp->children, name, my_id, sym);
  56                         return;
  57                 }
  58         } END_FOR_EACH_PTR(tmp);
  59
  60         tmp = __alloc_parent(0);
  61         tmp->sym = sym;
  62         tmp->children = NULL;
  63         add_tracker(&tmp->children, name, my_id, sym);
  64         add_ptr_list(&parents, tmp);
  65 }
  66
  67 static void set_list_assigned(struct tracker_list *children)
  68 {
  69         struct tracker *child;
  70
  71         FOR_EACH_PTR(children, child) {
  72                 set_state(child->name, my_id, child->sym, &assigned);
  73         } END_FOR_EACH_PTR(child);
  74 }
  75
  76 static struct tracker_list *get_children(struct symbol *sym)
  77 {
  78         struct parent *tmp;
  79
  80         FOR_EACH_PTR(parents, tmp) {
  81                 if (tmp->sym == sym) {
  82                         return tmp->children;
  83                 }
  84         } END_FOR_EACH_PTR(tmp);
  85         return NULL;
  86 }
  87
  88 static void set_children_assigned(struct symbol *sym)
  89 {
  90         struct tracker_list *children;
  91
  92         if ((children = get_children(sym))) {
  93                 set_list_assigned(children);
  94         }
  95 }
  96
  97 static int is_allocation(struct expression *expr)
  98 {
  99         char *fn_name;
 100         int i;
 101
 102         if (expr->type != EXPR_CALL)
 103                 return 0;
 104
 105         if (!(fn_name = get_variable_from_expr(expr->fn, NULL)))
 106                 return 0;
 107
 108         for (i = 0; allocation_funcs[i]; i++) {
 109                 if (!strcmp(fn_name, allocation_funcs[i])) {
 110                         free_string(fn_name);
 111                         return 1;
 112                 }
 113         }
 114         free_string(fn_name);
 115         return 0;
 116 }
 117
 118 static int is_freed(const char *name, struct symbol *sym)
 119 {
 120         struct state_list *slist;
 121
 122         slist = get_possible_states(name, my_id, sym);
 123         if (slist_has_state(slist, &isfree)) {
 124                 return 1;
 125         }
 126         return 0;
 127 }
 128
 129 static int is_argument(struct symbol *sym)
 130 {
 131         struct tracker *arg;
 132
 133         FOR_EACH_PTR(arguments, arg) {
 134                 if (arg->sym == sym)
 135                         return 1;
 136         } END_FOR_EACH_PTR(arg);
 137         return 0;
 138 }
 139
 140 static void match_function_def(struct symbol *sym)
 141 {
 142         struct symbol *arg;
 143
 144         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 145                 add_tracker(&arguments, arg->ident->name, my_id, arg);
 146         } END_FOR_EACH_PTR(arg);
 147 }
 148
 149 static void match_assign(struct expression *expr)
 150 {
 151         struct expression *left, *right;
 152         char *left_name, *right_name;
 153         struct symbol *left_sym, *right_sym;
 154         struct smatch_state *state;
 155
 156         left = strip_expr(expr->left);
 157         left_name = get_variable_from_expr(left, &left_sym);
 158         if (!left_name)
 159                 return;
 160         if (!left_sym) {
 161                 free_string(left_name);
 162                 return;
 163         }
 164
 165         right = strip_expr(expr->right);
 166         if (is_allocation(right) && !(left_sym->ctype.modifiers &
 167                         (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE))) {
 168                 set_state(left_name, my_id, left_sym, &malloced);
 169                 add_parent_to_parents(left_name, left_sym);
 170                 free_string(left_name);
 171                 return;
 172         }
 173
 174         right_name = get_variable_from_expr(right, &right_sym);
 175         if (right_name && (state = get_state(right_name, my_id, right_sym))) {
 176                 if (state == &isfree)
 177                         smatch_msg("error: assigning freed pointer");
 178                 set_state(right_name, my_id, right_sym, &assigned);
 179         }
 180         free_string(right_name);
 181
 182         if (is_freed(left_name, left_sym)) {
 183                 set_state(left_name, my_id, left_sym, &unfree);
 184         }
 185         free_string(left_name);
 186 }
 187
 188 static int is_null(char *name, struct symbol *sym)
 189 {
 190         struct smatch_state *state;
 191
 192         /*
 193          * FIXME.  Ha ha ha... This is so wrong.
 194          * I'm pulling in data from the check_null_deref script.
 195          * I just happen to know that its ID is 3.
 196          * The correct approved way to do this is to get the data from
 197          * smatch_extra.  But right now smatch_extra doesn't track it.
 198          */
 199         state = get_state(name, my_id, sym);
 200         if (state && !strcmp(state->name, "isnull"))
 201                 return 1;
 202         return 0;
 203 }
 204
 205 static void match_kfree(struct expression *expr)
 206 {
 207         struct expression *ptr_expr;
 208         char *ptr_name;
 209         struct symbol *ptr_sym;
 210
 211         ptr_expr = get_argument_from_call_expr(expr->args, 0);
 212         ptr_name = get_variable_from_expr(ptr_expr, &ptr_sym);
 213         if (is_freed(ptr_name, ptr_sym) && !is_null(ptr_name, ptr_sym)) {
 214                 smatch_msg("error: double free of %s", ptr_name);
 215         }
 216         set_state(ptr_name, my_id, ptr_sym, &isfree);
 217         free_string(ptr_name);
 218 }
 219
 220 static int possibly_allocated(struct state_list *slist)
 221 {
 222         struct sm_state *tmp;
 223
 224         FOR_EACH_PTR(slist, tmp) {
 225                 if (tmp->state == &allocated)
 226                         return 1;
 227                 if (tmp->state == &malloced)
 228                         return 1;
 229         } END_FOR_EACH_PTR(tmp);
 230         return 0;
 231 }
 232
 233 static void check_for_allocated()
 234 {
 235         struct state_list *slist;
 236         struct sm_state *tmp;
 237
 238         slist = get_all_states(my_id);
 239         FOR_EACH_PTR(slist, tmp) {
 240                 if (possibly_allocated(tmp->possible) &&
 241                         !is_null(tmp->name, tmp->sym) &&
 242                         !is_argument(tmp->sym))
 243                         smatch_msg("error: memery leak of %s", tmp->name);
 244         } END_FOR_EACH_PTR(tmp);
 245         free_slist(&slist);
 246 }
 247
 248 static void match_return(struct statement *stmt)
 249 {
 250         char *name;
 251         struct symbol *sym;
 252         struct smatch_state *state;
 253
 254         name = get_variable_from_expr(stmt->ret_value, &sym);
 255         if ((state = get_state(name, my_id, sym))) {
 256                 set_state(name, my_id, sym, &assigned);
 257                 add_parent_to_parents(name, sym);
 258         }
 259         free_string(name);
 260         check_for_allocated();
 261 }
 262
 263 static void set_new_true_false_paths(const char *name, struct symbol *sym)
 264 {
 265         struct smatch_state *tmp;
 266
 267         tmp = get_state(name, my_id, sym);
 268
 269         if (!tmp) {
 270                 return;
 271         }
 272
 273         if (tmp == &isfree) {
 274                 smatch_msg("warn: why do you care about freed memory?");
 275         }
 276
 277         if (tmp == &malloced) {
 278                 set_true_false_states(name, my_id, sym, &allocated, &isnull);
 279         }
 280 }
 281
 282 static void match_condition(struct expression *expr)
 283 {
 284         struct symbol *sym;
 285         char *name;
 286
 287         expr = strip_expr(expr);
 288         switch(expr->type) {
 289         case EXPR_PREOP:
 290         case EXPR_SYMBOL:
 291         case EXPR_DEREF:
 292                 name = get_variable_from_expr(expr, &sym);
 293                 if (!name)
 294                         return;
 295                 set_new_true_false_paths(name, sym);
 296                 free_string(name);
 297                 return;
 298         default:
 299                 return;
 300         }
 301 }
 302
 303 static void match_function_call(struct expression *expr)
 304 {
 305         struct expression *tmp;
 306         struct symbol *sym;
 307         char *name;
 308         char *fn_name;
 309         struct sm_state *state;
 310
 311         fn_name = get_variable_from_expr(expr->fn, NULL);
 312
 313         if (fn_name && !strcmp(fn_name, "kfree")) {
 314                 match_kfree(expr);
 315         }
 316
 317         FOR_EACH_PTR(expr->args, tmp) {
 318                 tmp = strip_expr(tmp);
 319                 name = get_variable_from_expr(tmp, &sym);
 320                 if (!name)
 321                         continue;
 322                 if ((state = get_sm_state(name, my_id, sym))) {
 323                         if (possibly_allocated(state->possible)) {
 324                                 set_state(name, my_id, sym, &assigned);
 325                         }
 326                 }
 327                 set_children_assigned(sym);
 328                 /* get parent.  set children to assigned */
 329         } END_FOR_EACH_PTR(tmp);
 330 }
 331
 332 static void free_the_parents()
 333 {
 334         struct parent *tmp;
 335
 336         FOR_EACH_PTR(parents, tmp) {
 337                 free_trackers_and_list(&tmp->children);
 338         } END_FOR_EACH_PTR(tmp);
 339         __free_ptr_list((struct ptr_list **)&parents);
 340 }
 341
 342 static void match_end_func(struct symbol *sym)
 343 {
 344         check_for_allocated();
 345         free_the_parents();
 346 }
 347
 348 void register_memory(int id)
 349 {
 350         my_id = id;
 351         add_hook(&match_function_def, FUNC_DEF_HOOK);
 352         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 353         add_hook(&match_condition, CONDITION_HOOK);
 354         add_hook(&match_assign, ASSIGNMENT_HOOK);
 355         add_hook(&match_return, RETURN_HOOK);
 356         add_hook(&match_end_func, END_FUNC_HOOK);
 357 }