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 struct locked_call {
  94         const char *function;
  95         const char *lock;
  96 };
  97
  98 static struct locked_call lock_needed[] = {
  99         {"tty_ldisc_ref_wait", "tty_ldisc_lock"},
 100 };
 101
 102 static int my_id;
 103
 104 static struct tracker_list *starts_locked;
 105 static struct tracker_list *starts_unlocked;
 106
 107 struct locks_on_return {
 108         int line;
 109         struct tracker_list *locked;
 110         struct tracker_list *unlocked;
 111 };
 112 DECLARE_PTR_LIST(return_list, struct locks_on_return);
 113 static struct return_list *all_returns;
 114
 115 STATE(locked);
 116 STATE(start_state);
 117 STATE(unlocked);
 118
 119 static struct smatch_state *get_start_state(struct sm_state *sm)
 120 {
 121        int is_locked = 0;
 122        int is_unlocked = 0;
 123
 124        if (in_tracker_list(starts_locked, sm->name, my_id, sm->sym))
 125                is_locked = 1;
 126        if (in_tracker_list(starts_unlocked, sm->name, my_id, sm->sym))
 127                is_unlocked = 1;
 128        if (is_locked && is_unlocked)
 129                return &undefined;
 130        if (is_locked)
 131                return &locked;
 132        if (is_unlocked)
 133                return &unlocked;
 134         return &undefined;
 135 }
 136
 137 static struct smatch_state *unmatched_state(struct sm_state *sm)
 138 {
 139         return &start_state;
 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 *get_lock_name(struct expression *expr, void *data)
 158 {
 159         struct expression *lock_expr;
 160
 161         if (data) {
 162                 return alloc_string((char *)data);
 163         } else {
 164                 lock_expr = get_argument_from_call_expr(expr->args, 0);
 165                 return get_variable_from_expr(lock_expr, NULL);
 166         }
 167 }
 168
 169 static void match_lock_func(struct expression *expr, void *data)
 170 {
 171         char *lock_name;
 172         struct sm_state *sm;
 173
 174         lock_name = get_lock_name(expr, data);
 175         if (!lock_name)
 176                 return;
 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("error: double lock '%s'", lock_name);
 182         set_state(lock_name, my_id, NULL, &locked);
 183         free_string(lock_name);
 184 }
 185
 186 static void match_unlock_func(struct expression *expr, void *data)
 187 {
 188         char *lock_name;
 189         struct sm_state *sm;
 190
 191         lock_name = get_lock_name(expr, data);
 192         if (!lock_name)
 193                 return;
 194         sm = get_sm_state(lock_name, my_id, NULL);
 195         if (!sm)
 196                 add_tracker(&starts_locked, lock_name, my_id, NULL);
 197         if (sm && slist_has_state(sm->possible, &unlocked))
 198                 smatch_msg("error: double unlock '%s'", lock_name);
 199         set_state(lock_name, my_id, NULL, &unlocked);
 200         free_string(lock_name);
 201 }
 202
 203 static void match_lock_needed(struct expression *expr, void *data)
 204 {
 205         struct smatch_state *state;
 206         char *fn_name;
 207
 208         state = get_state((char *)data, my_id, NULL);
 209         if (state == &locked)
 210                 return;
 211         fn_name = get_variable_from_expr(expr->fn, NULL);
 212         if (!fn_name) {
 213                 smatch_msg("Internal error.");
 214                 exit(1);
 215         }
 216         smatch_msg("error: %s called without holding '%s' lock", fn_name,
 217                    (char *)data);
 218         free_string(fn_name);
 219 }
 220
 221 static void match_condition(struct expression *expr)
 222 {
 223         char *fn_name;
 224         char *lock_name;
 225
 226         if (expr->type != EXPR_CALL)
 227                 return;
 228
 229         fn_name = get_variable_from_expr(expr->fn, NULL);
 230         if (!fn_name)
 231                 return;
 232
 233         if ((lock_name = match_func(conditional_funcs, fn_name, expr->args))) {
 234                 if (!get_state(lock_name, my_id, NULL))
 235                         add_tracker(&starts_unlocked, lock_name, my_id, NULL);
 236                 set_true_false_states(lock_name, my_id, NULL, &locked, &unlocked);
 237         }
 238         if ((lock_name = match_func(reverse_cond_funcs, fn_name, expr->args))) {
 239                 if (!get_state(lock_name, my_id, NULL))
 240                         add_tracker(&starts_unlocked, lock_name, my_id, NULL);
 241                 set_true_false_states(lock_name, my_id, NULL, &unlocked, &locked);
 242         }
 243         free_string(lock_name);
 244         free_string(fn_name);
 245         return;
 246 }
 247
 248 static struct locks_on_return *alloc_return(int line)
 249 {
 250         struct locks_on_return *ret;
 251
 252         ret = malloc(sizeof(*ret));
 253         ret->line = line;
 254         ret->locked = NULL;
 255         ret->unlocked = NULL;
 256         return ret;
 257 }
 258
 259 static void check_possible(struct sm_state *sm)
 260 {
 261         struct sm_state *tmp;
 262         int islocked = 0;
 263         int isunlocked = 0;
 264         int undef = 0;
 265
 266         FOR_EACH_PTR(sm->possible, tmp) {
 267                 if (tmp->state == &locked)
 268                         islocked = 1;
 269                 if (tmp->state == &unlocked)
 270                         isunlocked = 1;
 271                 if (tmp->state == &start_state) {
 272                         struct smatch_state *s;
 273
 274                         s = get_start_state(tmp);
 275                         if (s == &locked)
 276                                 islocked = 1;
 277                         else if (s == &unlocked)
 278                                 isunlocked = 1;
 279                         else
 280                                 undef = 1;
 281                 }
 282                 if (tmp->state == &undefined)
 283                         undef = 1;  // i don't think this is possible any more.
 284         } END_FOR_EACH_PTR(tmp);
 285         if ((islocked && isunlocked) || undef)
 286                 smatch_msg("warn: '%s' is sometimes locked here and "
 287                            "sometimes unlocked.", sm->name);
 288 }
 289
 290 static void match_return(struct statement *stmt)
 291 {
 292         struct locks_on_return *ret;
 293         struct state_list *slist;
 294         struct sm_state *tmp;
 295
 296         ret = alloc_return(get_lineno());
 297
 298         slist = get_all_states(my_id);
 299         FOR_EACH_PTR(slist, tmp) {
 300                 if (tmp->state == &locked) {
 301                         add_tracker(&ret->locked, tmp->name, tmp->owner,
 302                                 tmp->sym);
 303                 } else if (tmp->state == &unlocked) {
 304                         add_tracker(&ret->unlocked, tmp->name, tmp->owner,
 305                                 tmp->sym);
 306                 } else if (tmp->state == &start_state) {
 307                         struct smatch_state *s;
 308
 309                         s = get_start_state(tmp);
 310                         if (s == &locked)
 311                                 add_tracker(&ret->locked, tmp->name, tmp->owner,
 312                                             tmp->sym);
 313                         if (s == &unlocked)
 314                                 add_tracker(&ret->unlocked, tmp->name,
 315                                             tmp->owner, tmp->sym);
 316                 }else {
 317                         check_possible(tmp);
 318                 }
 319         } END_FOR_EACH_PTR(tmp);
 320         free_slist(&slist);
 321         add_ptr_list(&all_returns, ret);
 322 }
 323
 324 static void check_returns_consistently(struct tracker *lock,
 325                                 struct smatch_state *start)
 326 {
 327         int returns_locked = 0;
 328         int returns_unlocked = 0;
 329         struct locks_on_return *tmp;
 330
 331         FOR_EACH_PTR(all_returns, tmp) {
 332                 if (in_tracker_list(tmp->unlocked, lock->name, lock->owner,
 333                                         lock->sym))
 334                         returns_unlocked = tmp->line;
 335                 else if (in_tracker_list(tmp->locked, lock->name, lock->owner,
 336                                                 lock->sym))
 337                         returns_locked = tmp->line;
 338                 else if (start == &locked)
 339                         returns_locked = tmp->line;
 340                 else if (start == &unlocked)
 341                         returns_unlocked = tmp->line;
 342         } END_FOR_EACH_PTR(tmp);
 343
 344         if (returns_locked && returns_unlocked)
 345                 smatch_msg("warn: lock '%s' held on line %d but not on %d.",
 346                         lock->name, returns_locked, returns_unlocked);
 347
 348 }
 349
 350 static void check_consistency(struct symbol *sym)
 351 {
 352         struct tracker *tmp;
 353
 354         if (is_reachable())
 355                 match_return(NULL);
 356
 357         FOR_EACH_PTR(starts_locked, tmp) {
 358                 if (in_tracker_list(starts_unlocked, tmp->name, tmp->owner,
 359                                         tmp->sym))
 360                         smatch_msg("error:  locking inconsistency.  We assume "
 361                                    "'%s' is both locked and unlocked at the "
 362                                    "start.",
 363                                 tmp->name);
 364         } END_FOR_EACH_PTR(tmp);
 365
 366         FOR_EACH_PTR(starts_locked, tmp) {
 367                 check_returns_consistently(tmp, &locked);
 368         } END_FOR_EACH_PTR(tmp);
 369
 370         FOR_EACH_PTR(starts_unlocked, tmp) {
 371                 check_returns_consistently(tmp, &unlocked);
 372         } END_FOR_EACH_PTR(tmp);
 373
 374 }
 375
 376 static void clear_lists(void)
 377 {
 378         struct locks_on_return *tmp;
 379
 380         free_trackers_and_list(&starts_locked);
 381         free_trackers_and_list(&starts_unlocked);
 382
 383         FOR_EACH_PTR(all_returns, tmp) {
 384                 free_trackers_and_list(&tmp->locked);
 385                 free_trackers_and_list(&tmp->unlocked);
 386         } END_FOR_EACH_PTR(tmp);
 387         __free_ptr_list((struct ptr_list **)&all_returns);
 388 }
 389
 390 static void match_func_end(struct symbol *sym)
 391 {
 392         check_consistency(sym);
 393         clear_lists();
 394 }
 395
 396 void check_locking(int id)
 397 {
 398         int i;
 399
 400         my_id = id;
 401         add_unmatched_state_hook(my_id, &unmatched_state);
 402         add_hook(&match_condition, CONDITION_HOOK);
 403         add_hook(&match_return, RETURN_HOOK);
 404         add_hook(&match_func_end, END_FUNC_HOOK);
 405
 406         for (i = 0; lock_funcs[i]; i++) {
 407                 add_function_hook(lock_funcs[i], &match_lock_func, NULL);
 408         }
 409         add_function_hook("lock_kernel", &match_lock_func, (void *)"kernel");
 410         for (i = 0; unlock_funcs[i]; i++) {
 411                 add_function_hook(unlock_funcs[i], &match_unlock_func, NULL);
 412         }
 413         add_function_hook("unlock_kernel", &match_unlock_func, (void *)"kernel");
 414         for (i = 0; i < sizeof(lock_needed)/sizeof(struct locked_call); i++) {
 415                 add_function_hook(lock_needed[i].function, &match_lock_needed,
 416                                   (void *)lock_needed[i].lock);
 417         }
 418 }