check_locking.c

   1 /*
   2  * sparse/check_locking.c
   3  *
   4  * Copyright (C) 2009 Dan Carpenter.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * This test checks that locks are held the same across all returns.
  12  *
  13  * Of course, some functions are designed to only hold the locks on success.
  14  * Oh well... We can rewrite it later if we want.
  15  */
  16
  17 #include "parse.h"
  18 #include "smatch.h"
  19 #include "smatch_slist.h"
  20
  21 static const char *lock_funcs[] = {
  22         "_spin_lock",
  23         "_spin_lock_irqsave",
  24         "_spin_lock_irq",
  25         "_spin_lock_bh",
  26         "_spin_lock_nested",
  27         "_spin_lock_irqsave_nested",
  28         "_raw_spin_lock",
  29         "_read_lock",
  30         "_read_lock_irqsave",
  31         "_read_lock_irq",
  32         "_read_lock_bh",
  33         "_write_lock",
  34         "_write_lock_irqsave",
  35         "_write_lock_irq",
  36         "_write_lock_bh",
  37         "down",
  38         NULL,
  39 };
  40
  41 static const char *unlock_funcs[] = {
  42         "_spin_unlock",
  43         "_spin_unlock_irqrestore",
  44         "_spin_unlock_irq",
  45         "_spin_unlock_bh",
  46         "_raw_spin_unlock",
  47         "_read_unlock",
  48         "_read_unlock_irqrestore",
  49         "_read_unlock_irq",
  50         "_read_unlock_bh",
  51         "_write_unlock",
  52         "_write_unlock_irqrestore",
  53         "_write_unlock_irq",
  54         "_write_unlock_bh",
  55         "up",
  56         NULL,
  57 };
  58
  59 static const char *conditional_funcs[] = {
  60         "_spin_trylock",
  61         "_read_trylock",
  62         "_write_trylock",
  63         "generic__raw_read_trylock",
  64         "_raw_spin_trylock",
  65         "_raw_read_trylock",
  66         "_raw_write_trylock",
  67         "__raw_spin_trylock",
  68         "__raw_read_trylock",
  69         "__raw_write_trylock",
  70         "__raw_write_trylock",
  71         NULL,
  72 };
  73
  74 /* todo still need to handle__raw_spin_is_locked */
  75
  76
  77 struct locked_call {
  78         const char *function;
  79         const char *lock;
  80 };
  81
  82 static struct locked_call lock_needed[] = {
  83         {"tty_ldisc_ref_wait", "tty_ldisc_lock"},
  84 };
  85
  86 static int my_id;
  87
  88 static struct tracker_list *starts_locked;
  89 static struct tracker_list *starts_unlocked;
  90
  91 struct locks_on_return {
  92         int line;
  93         struct tracker_list *locked;
  94         struct tracker_list *unlocked;
  95 };
  96 DECLARE_PTR_LIST(return_list, struct locks_on_return);
  97 static struct return_list *all_returns;
  98
  99 STATE(locked);
 100 STATE(unlocked);
 101
 102 static char kernel[] = "kernel";
 103 static char *match_lock_func(char *fn_name, struct expression_list *args)
 104 {
 105         struct expression *lock_expr;
 106         int i;
 107
 108         for (i = 0; lock_funcs[i]; i++) {
 109                 if (!strcmp(fn_name, lock_funcs[i])) {
 110                         lock_expr = get_argument_from_call_expr(args, 0);
 111                         return get_variable_from_expr(lock_expr, NULL);
 112                 }
 113         }
 114         if (!strcmp(fn_name, "lock_kernel"))
 115                 return kernel;
 116         return NULL;
 117 }
 118
 119 static char *match_unlock_func(char *fn_name, struct expression_list *args)
 120 {
 121         struct expression *lock_expr;
 122         int i;
 123
 124         for (i = 0; unlock_funcs[i]; i++) {
 125                 if (!strcmp(fn_name, unlock_funcs[i])) {
 126                         lock_expr = get_argument_from_call_expr(args, 0);
 127                         return get_variable_from_expr(lock_expr, NULL);
 128                 }
 129         }
 130         if (!strcmp(fn_name, "unlock_kernel"))
 131                 return kernel;
 132         return NULL;
 133 }
 134
 135 static char *match_conditional_func(char *fn_name, struct expression_list *args)
 136 {
 137         struct expression *lock_expr;
 138         int i;
 139
 140         for (i = 0; conditional_funcs[i]; i++) {
 141                 if (!strcmp(fn_name, conditional_funcs[i])) {
 142                         lock_expr = get_argument_from_call_expr(args, 0);
 143                         return get_variable_from_expr(lock_expr, NULL);
 144                 }
 145         }
 146         return NULL;
 147 }
 148
 149 static void check_locks_needed(const char *fn_name)
 150 {
 151         struct smatch_state *state;
 152         int i;
 153
 154         for (i = 0; i < sizeof(lock_needed)/sizeof(struct locked_call); i++) {
 155                 if (!strcmp(fn_name, lock_needed[i].function)) {
 156                         state = get_state(lock_needed[i].lock, my_id, NULL);
 157                         if (state != &locked) {
 158                                 smatch_msg("%s called without holding '%s' lock",
 159                                         lock_needed[i].function,
 160                                         lock_needed[i].lock);
 161                         }
 162                 }
 163         }
 164 }
 165
 166 static void match_call(struct expression *expr)
 167 {
 168         char *fn_name;
 169         char *lock_name;
 170         struct sm_state *sm;
 171
 172         fn_name = get_variable_from_expr(expr->fn, NULL);
 173         if (!fn_name)
 174                 return;
 175
 176         if ((lock_name = match_lock_func(fn_name, expr->args))) {
 177                 sm = get_sm_state(lock_name, my_id, NULL);
 178                 if (!sm)
 179                         add_tracker(&starts_unlocked, lock_name, my_id, NULL);
 180                 if (sm && slist_has_state(sm->possible, &locked))
 181                         smatch_msg("double lock.");
 182                 set_state(lock_name, my_id, NULL, &locked);
 183         } else if ((lock_name = match_unlock_func(fn_name, expr->args))) {
 184                 sm = get_sm_state(lock_name, my_id, NULL);
 185                 if (!sm)
 186                         add_tracker(&starts_locked, lock_name, my_id, NULL);
 187                 if (sm && slist_has_state(sm->possible, &unlocked))
 188                         smatch_msg("double unlock.");
 189                 set_state(lock_name, my_id, NULL, &unlocked);
 190         } else
 191                 check_locks_needed(fn_name);
 192         free_string(fn_name);
 193         return;
 194 }
 195
 196 static void match_condition(struct expression *expr)
 197 {
 198         char *fn_name;
 199         char *lock_name;
 200
 201         if (expr->type != EXPR_CALL)
 202                 return;
 203
 204         fn_name = get_variable_from_expr(expr->fn, NULL);
 205         if (!fn_name)
 206                 return;
 207
 208         if ((lock_name = match_conditional_func(fn_name, expr->args))) {
 209                 if (!get_state(lock_name, my_id, NULL))
 210                         add_tracker(&starts_unlocked, lock_name, my_id, NULL);
 211                 set_true_false_states(lock_name, my_id, NULL, &locked, &unlocked);
 212         }
 213         free_string(fn_name);
 214         return;
 215 }
 216
 217 static struct locks_on_return *alloc_return(int line)
 218 {
 219         struct locks_on_return *ret;
 220
 221         ret = malloc(sizeof(*ret));
 222         ret->line = line;
 223         ret->locked = NULL;
 224         ret->unlocked = NULL;
 225         return ret;
 226 }
 227
 228 static void check_possible(struct sm_state *sm)
 229 {
 230         struct sm_state *tmp;
 231         int islocked = 0;
 232         int isunlocked = 0;
 233         int undef = 0;
 234
 235         FOR_EACH_PTR(sm->possible, tmp) {
 236                 if (tmp->state == &locked)
 237                         islocked = 1;
 238                 else if (tmp->state == &unlocked)
 239                         isunlocked = 1;
 240                 else if (tmp->state == &undefined)
 241                         undef = 1;
 242         } END_FOR_EACH_PTR(tmp);
 243         if (islocked && (isunlocked || undef))
 244                 smatch_msg("Unclear if '%s' is locked or unlocked.", tmp->name);
 245 }
 246
 247 static void match_return(struct statement *stmt)
 248 {
 249         struct locks_on_return *ret;
 250         struct state_list *slist;
 251         struct sm_state *tmp;
 252
 253         ret = alloc_return(get_lineno());
 254
 255         slist = get_all_states(my_id);
 256         FOR_EACH_PTR(slist, tmp) {
 257                 if (tmp->state == &locked) {
 258                         add_tracker(&ret->locked, tmp->name, tmp->owner,
 259                                 tmp->sym);
 260                 } else if (tmp->state == &unlocked) {
 261                         add_tracker(&ret->unlocked, tmp->name, tmp->owner,
 262                                 tmp->sym);
 263                 } else {
 264                         check_possible(tmp);
 265                 }
 266         } END_FOR_EACH_PTR(tmp);
 267         add_ptr_list(&all_returns, ret);
 268 }
 269
 270 static void check_returns_consistently(struct tracker *lock,
 271                                 struct smatch_state *start)
 272 {
 273         int returns_locked = 0;
 274         int returns_unlocked = 0;
 275         struct locks_on_return *tmp;
 276
 277         FOR_EACH_PTR(all_returns, tmp) {
 278                 if (in_tracker_list(tmp->unlocked, lock->name, lock->owner,
 279                                         lock->sym))
 280                         returns_unlocked = tmp->line;
 281                 else if (in_tracker_list(tmp->locked, lock->name, lock->owner,
 282                                                 lock->sym))
 283                         returns_locked = tmp->line;
 284                 else if (start == &locked)
 285                         returns_locked = tmp->line;
 286                 else if (start == &unlocked)
 287                         returns_unlocked = tmp->line;
 288         } END_FOR_EACH_PTR(tmp);
 289
 290         if (returns_locked && returns_unlocked)
 291                 smatch_msg("Lock '%s' held on line %d but not on %d.",
 292                         lock->name, returns_locked, returns_unlocked);
 293
 294 }
 295
 296 static void clear_lists()
 297 {
 298         struct locks_on_return *tmp;
 299
 300         __free_ptr_list((struct ptr_list **)&starts_locked);
 301         __free_ptr_list((struct ptr_list **)&starts_unlocked);
 302
 303         FOR_EACH_PTR(all_returns, tmp) {
 304                 __free_ptr_list((struct ptr_list **)&tmp->locked);
 305                 __free_ptr_list((struct ptr_list **)&tmp->unlocked);
 306         } END_FOR_EACH_PTR(tmp);
 307         __free_ptr_list((struct ptr_list **)&all_returns);
 308 }
 309
 310 static void check_consistency(struct symbol *sym)
 311 {
 312         struct tracker *tmp;
 313
 314         FOR_EACH_PTR(starts_locked, tmp) {
 315                 if (in_tracker_list(starts_unlocked, tmp->name, tmp->owner,
 316                                         tmp->sym))
 317                         smatch_msg("Locking inconsistency.  We assume '%s' is "
 318                                 "both locked and unlocked at the start.",
 319                                 tmp->name);
 320         } END_FOR_EACH_PTR(tmp);
 321
 322         FOR_EACH_PTR(starts_locked, tmp) {
 323                 check_returns_consistently(tmp, &locked);
 324         } END_FOR_EACH_PTR(tmp);
 325
 326         FOR_EACH_PTR(starts_unlocked, tmp) {
 327                 check_returns_consistently(tmp, &unlocked);
 328         } END_FOR_EACH_PTR(tmp);
 329
 330         clear_lists();
 331 }
 332
 333 void register_locking(int id)
 334 {
 335         my_id = id;
 336         add_hook(&match_condition, CONDITION_HOOK);
 337         add_hook(&match_call, FUNCTION_CALL_HOOK);
 338         add_hook(&match_return, RETURN_HOOK);
 339         add_hook(&check_consistency, END_FUNC_HOOK);
 340 }