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