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