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         "_spin_trylock_bh",
  62         "_read_trylock",
  63         "_write_trylock",
  64         "generic__raw_read_trylock",
  65         "_raw_spin_trylock",
  66         "_raw_read_trylock",
  67         "_raw_write_trylock",
  68         "__raw_spin_trylock",
  69         "__raw_read_trylock",
  70         "__raw_write_trylock",
  71         "__raw_write_trylock",
  72         NULL,
  73 };
  74
  75 /* These functions return 0 on success */
  76 static const char *reverse_cond_funcs[] = {
  77         "down_trylock",
  78         "down_interruptible",
  79         NULL,
  80 };
  81
  82 /* todo still need to handle__raw_spin_is_locked */
  83
  84
  85 struct locked_call {
  86         const char *function;
  87         const char *lock;
  88 };
  89
  90 static struct locked_call lock_needed[] = {
  91         {"tty_ldisc_ref_wait", "tty_ldisc_lock"},
  92 };
  93
  94 static int my_id;
  95
  96 static struct tracker_list *starts_locked;
  97 static struct tracker_list *starts_unlocked;
  98
  99 struct locks_on_return {
 100         int line;
 101         struct tracker_list *locked;
 102         struct tracker_list *unlocked;
 103 };
 104 DECLARE_PTR_LIST(return_list, struct locks_on_return);
 105 static struct return_list *all_returns;
 106
 107 STATE(locked);
 108 STATE(unlocked);
 109
 110 /*
 111  * merge_func() is used merging NULL and a state should be merge plus
 112  * the state that the function was originally called with.  This way
 113  * we can sometimes avoid being &undefined.
 114  */
 115 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
 116                                        struct smatch_state *s1,
 117                                        struct smatch_state *s2)
 118 {
 119         int is_locked = 0;
 120         int is_unlocked = 0;
 121
 122         if (s1)
 123                 return &merged;
 124         if (in_tracker_list(starts_locked, name, my_id, sym))
 125                 is_locked = 1;
 126         if (in_tracker_list(starts_unlocked, name, my_id, sym))
 127                 is_unlocked = 1;
 128         if (is_locked && is_unlocked)
 129                 return &undefined;
 130         if (s2 == &locked && is_locked)
 131                 return &locked;
 132         if (s2 == &unlocked && is_unlocked)
 133                 return &unlocked;
 134         return &undefined;
 135 }
 136
 137 static char *match_func(const char *list[], char *fn_name,
 138                         struct expression_list *args)
 139 {
 140         struct expression *lock_expr;
 141         int i;
 142
 143         for (i = 0; list[i]; i++) {
 144                 if (!strcmp(fn_name, list[i])) {
 145                         lock_expr = get_argument_from_call_expr(args, 0);
 146                         return get_variable_from_expr(lock_expr, NULL);
 147                 }
 148         }
 149         return NULL;
 150 }
 151
 152 static char kernel[] = "kernel";
 153 static char *match_lock_func(char *fn_name, struct expression_list *args)
 154 {
 155         char *arg;
 156
 157         arg = match_func(lock_funcs, fn_name, args);
 158         if (arg)
 159                 return arg;
 160         if (!strcmp(fn_name, "lock_kernel"))
 161                 return alloc_string(kernel);
 162         return NULL;
 163 }
 164
 165 static char *match_unlock_func(char *fn_name, struct expression_list *args)
 166 {
 167         char *arg;
 168
 169         arg = match_func(unlock_funcs, fn_name, args);
 170         if (arg)
 171                 return arg;
 172         if (!strcmp(fn_name, "unlock_kernel"))
 173                 return alloc_string(kernel);
 174         return NULL;
 175 }
 176
 177 static void check_locks_needed(const char *fn_name)
 178 {
 179         struct smatch_state *state;
 180         int i;
 181
 182         for (i = 0; i < sizeof(lock_needed)/sizeof(struct locked_call); i++) {
 183                 if (!strcmp(fn_name, lock_needed[i].function)) {
 184                         state = get_state(lock_needed[i].lock, my_id, NULL);
 185                         if (state != &locked) {
 186                                 smatch_msg("%s called without holding '%s' lock",
 187                                         lock_needed[i].function,
 188                                         lock_needed[i].lock);
 189                         }
 190                 }
 191         }
 192 }
 193
 194 static void match_call(struct expression *expr)
 195 {
 196         char *fn_name;
 197         char *lock_name;
 198         struct sm_state *sm;
 199
 200         fn_name = get_variable_from_expr(expr->fn, NULL);
 201         if (!fn_name)
 202                 return;
 203
 204         if ((lock_name = match_lock_func(fn_name, expr->args))) {
 205                 sm = get_sm_state(lock_name, my_id, NULL);
 206                 if (!sm)
 207                         add_tracker(&starts_unlocked, lock_name, my_id, NULL);
 208                 if (sm && slist_has_state(sm->possible, &locked))
 209                         smatch_msg("double lock '%s'", lock_name);
 210                 set_state(lock_name, my_id, NULL, &locked);
 211         } else if ((lock_name = match_unlock_func(fn_name, expr->args))) {
 212                 sm = get_sm_state(lock_name, my_id, NULL);
 213                 if (!sm)
 214                         add_tracker(&starts_locked, lock_name, my_id, NULL);
 215                 if (sm && slist_has_state(sm->possible, &unlocked))
 216                         smatch_msg("double unlock '%s'", lock_name);
 217                 set_state(lock_name, my_id, NULL, &unlocked);
 218         } else
 219                 check_locks_needed(fn_name);
 220         free_string(lock_name);
 221         free_string(fn_name);
 222         return;
 223 }
 224
 225 static void match_condition(struct expression *expr)
 226 {
 227         char *fn_name;
 228         char *lock_name;
 229
 230         if (expr->type != EXPR_CALL)
 231                 return;
 232
 233         fn_name = get_variable_from_expr(expr->fn, NULL);
 234         if (!fn_name)
 235                 return;
 236
 237         if ((lock_name = match_func(conditional_funcs, fn_name, expr->args))) {
 238                 if (!get_state(lock_name, my_id, NULL))
 239                         add_tracker(&starts_unlocked, lock_name, my_id, NULL);
 240                 set_true_false_states(lock_name, my_id, NULL, &locked, &unlocked);
 241         }
 242         if ((lock_name = match_func(reverse_cond_funcs, fn_name, expr->args))) {
 243                 if (!get_state(lock_name, my_id, NULL))
 244                         add_tracker(&starts_unlocked, lock_name, my_id, NULL);
 245                 set_true_false_states(lock_name, my_id, NULL, &unlocked, &locked);
 246         }
 247         free_string(lock_name);
 248         free_string(fn_name);
 249         return;
 250 }
 251
 252 static struct locks_on_return *alloc_return(int line)
 253 {
 254         struct locks_on_return *ret;
 255
 256         ret = malloc(sizeof(*ret));
 257         ret->line = line;
 258         ret->locked = NULL;
 259         ret->unlocked = NULL;
 260         return ret;
 261 }
 262
 263 static void check_possible(struct sm_state *sm)
 264 {
 265         struct sm_state *tmp;
 266         int islocked = 0;
 267         int isunlocked = 0;
 268         int undef = 0;
 269
 270         FOR_EACH_PTR(sm->possible, tmp) {
 271                 if (tmp->state == &locked)
 272                         islocked = 1;
 273                 else if (tmp->state == &unlocked)
 274                         isunlocked = 1;
 275                 else if (tmp->state == &undefined)
 276                         undef = 1;
 277         } END_FOR_EACH_PTR(tmp);
 278         if ((islocked && isunlocked) || undef)
 279                 smatch_msg("Unclear if '%s' is locked or unlocked.", sm->name);
 280 }
 281
 282 static void match_return(struct statement *stmt)
 283 {
 284         struct locks_on_return *ret;
 285         struct state_list *slist;
 286         struct sm_state *tmp;
 287
 288         ret = alloc_return(get_lineno());
 289
 290         slist = get_all_states(my_id);
 291         FOR_EACH_PTR(slist, tmp) {
 292                 if (tmp->state == &locked) {
 293                         add_tracker(&ret->locked, tmp->name, tmp->owner,
 294                                 tmp->sym);
 295                 } else if (tmp->state == &unlocked) {
 296                         add_tracker(&ret->unlocked, tmp->name, tmp->owner,
 297                                 tmp->sym);
 298                 } else {
 299                         check_possible(tmp);
 300                 }
 301         } END_FOR_EACH_PTR(tmp);
 302         free_slist(&slist);
 303         add_ptr_list(&all_returns, ret);
 304 }
 305
 306 static void check_returns_consistently(struct tracker *lock,
 307                                 struct smatch_state *start)
 308 {
 309         int returns_locked = 0;
 310         int returns_unlocked = 0;
 311         struct locks_on_return *tmp;
 312
 313         FOR_EACH_PTR(all_returns, tmp) {
 314                 if (in_tracker_list(tmp->unlocked, lock->name, lock->owner,
 315                                         lock->sym))
 316                         returns_unlocked = tmp->line;
 317                 else if (in_tracker_list(tmp->locked, lock->name, lock->owner,
 318                                                 lock->sym))
 319                         returns_locked = tmp->line;
 320                 else if (start == &locked)
 321                         returns_locked = tmp->line;
 322                 else if (start == &unlocked)
 323                         returns_unlocked = tmp->line;
 324         } END_FOR_EACH_PTR(tmp);
 325
 326         if (returns_locked && returns_unlocked)
 327                 smatch_msg("Lock '%s' held on line %d but not on %d.",
 328                         lock->name, returns_locked, returns_unlocked);
 329
 330 }
 331
 332 static void clear_lists()
 333 {
 334         struct locks_on_return *tmp;
 335
 336         free_trackers_and_list(&starts_locked);
 337         free_trackers_and_list(&starts_unlocked);
 338
 339         FOR_EACH_PTR(all_returns, tmp) {
 340                 free_trackers_and_list(&tmp->locked);
 341                 free_trackers_and_list(&tmp->unlocked);
 342         } END_FOR_EACH_PTR(tmp);
 343         __free_ptr_list((struct ptr_list **)&all_returns);
 344 }
 345
 346 static void check_consistency(struct symbol *sym)
 347 {
 348         struct tracker *tmp;
 349
 350         if (is_reachable())
 351                 match_return(NULL);
 352
 353         FOR_EACH_PTR(starts_locked, tmp) {
 354                 if (in_tracker_list(starts_unlocked, tmp->name, tmp->owner,
 355                                         tmp->sym))
 356                         smatch_msg("Locking inconsistency.  We assume '%s' is "
 357                                 "both locked and unlocked at the start.",
 358                                 tmp->name);
 359         } END_FOR_EACH_PTR(tmp);
 360
 361         FOR_EACH_PTR(starts_locked, tmp) {
 362                 check_returns_consistently(tmp, &locked);
 363         } END_FOR_EACH_PTR(tmp);
 364
 365         FOR_EACH_PTR(starts_unlocked, tmp) {
 366                 check_returns_consistently(tmp, &unlocked);
 367         } END_FOR_EACH_PTR(tmp);
 368
 369         clear_lists();
 370 }
 371
 372 void register_locking(int id)
 373 {
 374         my_id = id;
 375         add_merge_hook(my_id, &merge_func);
 376         add_hook(&match_condition, CONDITION_HOOK);
 377         add_hook(&match_call, FUNCTION_CALL_HOOK);
 378         add_hook(&match_return, RETURN_HOOK);
 379         add_hook(&check_consistency, END_FUNC_HOOK);
 380 }