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