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