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 and negative on failure */
  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, my_id, sm->name, sm->sym))
 125                is_locked = 1;
 126        if (in_tracker_list(starts_unlocked, my_id, sm->name, 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 *get_lock_name(struct expression *expr, void *data)
 143 {
 144         struct expression *lock_expr;
 145
 146         if (data) {
 147                 return alloc_string((char *)data);
 148         } else {
 149                 lock_expr = get_argument_from_call_expr(expr->args, 0);
 150                 return get_variable_from_expr(lock_expr, NULL);
 151         }
 152 }
 153
 154 static void match_lock_func(const char *fn, struct expression *expr, void *data)
 155 {
 156         char *lock_name;
 157         struct sm_state *sm;
 158
 159         lock_name = get_lock_name(expr, data);
 160         if (!lock_name)
 161                 return;
 162         sm = get_sm_state(my_id, lock_name, NULL);
 163         if (!sm)
 164                 add_tracker(&starts_unlocked, my_id, lock_name, NULL);
 165         if (sm && slist_has_state(sm->possible, &locked))
 166                 sm_msg("error: double lock '%s'", lock_name);
 167         set_state(my_id, lock_name, NULL, &locked);
 168         free_string(lock_name);
 169 }
 170
 171 static void match_unlock_func(const char *fn, struct expression *expr,
 172                               void *data)
 173 {
 174         char *lock_name;
 175         struct sm_state *sm;
 176
 177         lock_name = get_lock_name(expr, data);
 178         if (!lock_name)
 179                 return;
 180         sm = get_sm_state(my_id, lock_name, NULL);
 181         if (!sm)
 182                 add_tracker(&starts_locked, my_id, lock_name, NULL);
 183         if (sm && slist_has_state(sm->possible, &unlocked))
 184                 sm_msg("error: double unlock '%s'", lock_name);
 185         set_state(my_id, lock_name, NULL, &unlocked);
 186         free_string(lock_name);
 187 }
 188
 189 static void match_lock_failed(const char *fn, struct expression *expr, void *data)
 190 {
 191         char *lock_name;
 192         struct sm_state *sm;
 193
 194         lock_name = get_lock_name(expr, data);
 195         if (!lock_name)
 196                 return;
 197         sm = get_sm_state(my_id, lock_name, NULL);
 198         if (!sm)
 199                 add_tracker(&starts_unlocked, my_id, lock_name, NULL);
 200         set_state(my_id, lock_name, NULL, &unlocked);
 201         free_string(lock_name);
 202 }
 203
 204 static void match_lock_aquired(const char *fn, struct expression *expr, void *data)
 205 {
 206         char *lock_name;
 207         struct sm_state *sm;
 208
 209         lock_name = get_lock_name(expr, data);
 210         if (!lock_name)
 211                 return;
 212         sm = get_sm_state(my_id, lock_name, NULL);
 213         if (!sm)
 214                 add_tracker(&starts_unlocked, my_id, lock_name, NULL);
 215         if (sm && slist_has_state(sm->possible, &locked))
 216                 sm_msg("error: double lock '%s'", lock_name);
 217         set_state(my_id, lock_name, NULL, &locked);
 218         free_string(lock_name);
 219 }
 220
 221 static void match_lock_needed(const char *fn, struct expression *expr,
 222                               void *data)
 223 {
 224         struct smatch_state *state;
 225         char *fn_name;
 226
 227         state = get_state(my_id, (char *)data, NULL);
 228         if (state == &locked)
 229                 return;
 230         fn_name = get_variable_from_expr(expr->fn, NULL);
 231         if (!fn_name) {
 232                 sm_msg("Internal error.");
 233                 exit(1);
 234         }
 235         sm_msg("error: %s called without holding '%s' lock", fn_name,
 236                    (char *)data);
 237         free_string(fn_name);
 238 }
 239
 240 static void match_locks_on_non_zero(const char *fn, struct expression *expr,
 241                                    void *data)
 242 {
 243         char *lock_name;
 244         struct sm_state *sm;
 245
 246         lock_name = get_lock_name(expr, data);
 247         if (!lock_name)
 248                 return;
 249         sm = get_sm_state(my_id, lock_name, NULL);
 250         if (!sm)
 251                 add_tracker(&starts_unlocked, my_id, lock_name, NULL);
 252         set_true_false_states(my_id, lock_name, NULL, &locked, &unlocked);
 253         free_string(lock_name);
 254 }
 255
 256 static struct locks_on_return *alloc_return(int line)
 257 {
 258         struct locks_on_return *ret;
 259
 260         ret = malloc(sizeof(*ret));
 261         ret->line = line;
 262         ret->locked = NULL;
 263         ret->unlocked = NULL;
 264         return ret;
 265 }
 266
 267 static void check_possible(struct sm_state *sm)
 268 {
 269         struct sm_state *tmp;
 270         int islocked = 0;
 271         int isunlocked = 0;
 272         int undef = 0;
 273
 274         FOR_EACH_PTR(sm->possible, tmp) {
 275                 if (tmp->state == &locked)
 276                         islocked = 1;
 277                 if (tmp->state == &unlocked)
 278                         isunlocked = 1;
 279                 if (tmp->state == &start_state) {
 280                         struct smatch_state *s;
 281
 282                         s = get_start_state(tmp);
 283                         if (s == &locked)
 284                                 islocked = 1;
 285                         else if (s == &unlocked)
 286                                 isunlocked = 1;
 287                         else
 288                                 undef = 1;
 289                 }
 290                 if (tmp->state == &undefined)
 291                         undef = 1;  // i don't think this is possible any more.
 292         } END_FOR_EACH_PTR(tmp);
 293         if ((islocked && isunlocked) || undef)
 294                 sm_msg("warn: '%s' is sometimes locked here and "
 295                            "sometimes unlocked.", sm->name);
 296 }
 297
 298 static void match_return(struct statement *stmt)
 299 {
 300         struct locks_on_return *ret;
 301         struct state_list *slist;
 302         struct sm_state *tmp;
 303
 304         if (!final_pass)
 305                 return;
 306
 307         ret = alloc_return(get_lineno());
 308
 309         slist = get_all_states(my_id);
 310         FOR_EACH_PTR(slist, tmp) {
 311                 if (tmp->state == &locked) {
 312                         add_tracker(&ret->locked, tmp->owner, tmp->name,
 313                                 tmp->sym);
 314                 } else if (tmp->state == &unlocked) {
 315                         add_tracker(&ret->unlocked, tmp->owner, tmp->name,
 316                                 tmp->sym);
 317                 } else if (tmp->state == &start_state) {
 318                         struct smatch_state *s;
 319
 320                         s = get_start_state(tmp);
 321                         if (s == &locked)
 322                                 add_tracker(&ret->locked, tmp->owner, tmp->name,
 323                                             tmp->sym);
 324                         if (s == &unlocked)
 325                                 add_tracker(&ret->unlocked, tmp->owner,tmp->name,
 326                                              tmp->sym);
 327                 }else {
 328                         check_possible(tmp);
 329                 }
 330         } END_FOR_EACH_PTR(tmp);
 331         free_slist(&slist);
 332         add_ptr_list(&all_returns, ret);
 333 }
 334
 335 static void print_inconsistent_returns(struct tracker *lock,
 336                                 struct smatch_state *start)
 337 {
 338         struct locks_on_return *tmp;
 339         int i;
 340
 341         sm_printf("%s +%d %s(%d) ", get_filename(), get_lineno(), get_function(), get_func_pos());
 342         sm_printf("warn: inconsistent returns %s:", lock->name);
 343         sm_printf(" locked (");
 344         i = 0;
 345         FOR_EACH_PTR(all_returns, tmp) {
 346                 if (in_tracker_list(tmp->unlocked, lock->owner, lock->name, lock->sym))
 347                         continue;
 348                 if (in_tracker_list(tmp->locked, lock->owner, lock->name, lock->sym)) {
 349                         if (i++)
 350                                 sm_printf(",");
 351                         sm_printf("%d", tmp->line);
 352                         continue;
 353                 }
 354                 if (start == &locked) {
 355                         if (i++)
 356                                 sm_printf(",");
 357                         sm_printf("%d", tmp->line);
 358                 }
 359         } END_FOR_EACH_PTR(tmp);
 360
 361         sm_printf(") unlocked (");
 362         i = 0;
 363         FOR_EACH_PTR(all_returns, tmp) {
 364                 if (in_tracker_list(tmp->unlocked, lock->owner, lock->name, lock->sym)) {
 365                         if (i++)
 366                                 sm_printf(",");
 367                         sm_printf("%d", tmp->line);
 368                         continue;
 369                 }
 370                 if (in_tracker_list(tmp->locked, lock->owner, lock->name, lock->sym)) {
 371                         continue;
 372                 }
 373                 if (start == &unlocked) {
 374                         if (i++)
 375                                 sm_printf(",");
 376                         sm_printf("%d", tmp->line);
 377                 }
 378         } END_FOR_EACH_PTR(tmp);
 379         sm_printf(")\n");
 380 }
 381
 382 static void check_returns_consistently(struct tracker *lock,
 383                                 struct smatch_state *start)
 384 {
 385         int returns_locked = 0;
 386         int returns_unlocked = 0;
 387         struct locks_on_return *tmp;
 388
 389         FOR_EACH_PTR(all_returns, tmp) {
 390                 if (in_tracker_list(tmp->unlocked, lock->owner, lock->name,
 391                                         lock->sym))
 392                         returns_unlocked = tmp->line;
 393                 else if (in_tracker_list(tmp->locked, lock->owner, lock->name,
 394                                                 lock->sym))
 395                         returns_locked = tmp->line;
 396                 else if (start == &locked)
 397                         returns_locked = tmp->line;
 398                 else if (start == &unlocked)
 399                         returns_unlocked = tmp->line;
 400         } END_FOR_EACH_PTR(tmp);
 401
 402         if (returns_locked && returns_unlocked)
 403                 print_inconsistent_returns(lock, start);
 404 }
 405
 406 static void check_consistency(struct symbol *sym)
 407 {
 408         struct tracker *tmp;
 409
 410         if (is_reachable())
 411                 match_return(NULL);
 412
 413         FOR_EACH_PTR(starts_locked, tmp) {
 414                 if (in_tracker_list(starts_unlocked, tmp->owner, tmp->name,
 415                                         tmp->sym))
 416                         sm_msg("error:  locking inconsistency.  We assume "
 417                                    "'%s' is both locked and unlocked at the "
 418                                    "start.",
 419                                 tmp->name);
 420         } END_FOR_EACH_PTR(tmp);
 421
 422         FOR_EACH_PTR(starts_locked, tmp) {
 423                 check_returns_consistently(tmp, &locked);
 424         } END_FOR_EACH_PTR(tmp);
 425
 426         FOR_EACH_PTR(starts_unlocked, tmp) {
 427                 check_returns_consistently(tmp, &unlocked);
 428         } END_FOR_EACH_PTR(tmp);
 429
 430 }
 431
 432 static void clear_lists(void)
 433 {
 434         struct locks_on_return *tmp;
 435
 436         free_trackers_and_list(&starts_locked);
 437         free_trackers_and_list(&starts_unlocked);
 438
 439         FOR_EACH_PTR(all_returns, tmp) {
 440                 free_trackers_and_list(&tmp->locked);
 441                 free_trackers_and_list(&tmp->unlocked);
 442                 free(tmp);
 443         } END_FOR_EACH_PTR(tmp);
 444         __free_ptr_list((struct ptr_list **)&all_returns);
 445 }
 446
 447 static void match_func_end(struct symbol *sym)
 448 {
 449         check_consistency(sym);
 450         clear_lists();
 451 }
 452
 453 void check_locking(int id)
 454 {
 455         int i;
 456
 457         my_id = id;
 458         add_unmatched_state_hook(my_id, &unmatched_state);
 459         add_hook(&match_return, RETURN_HOOK);
 460         add_hook(&match_func_end, END_FUNC_HOOK);
 461
 462         for (i = 0; lock_funcs[i]; i++) {
 463                 add_function_hook(lock_funcs[i], &match_lock_func, NULL);
 464         }
 465         add_function_hook("lock_kernel", &match_lock_func, (void *)"kernel");
 466         for (i = 0; unlock_funcs[i]; i++) {
 467                 add_function_hook(unlock_funcs[i], &match_unlock_func, NULL);
 468         }
 469         add_function_hook("unlock_kernel", &match_unlock_func, (void *)"kernel");
 470         for (i = 0; i < sizeof(lock_needed)/sizeof(struct locked_call); i++) {
 471                 add_function_hook(lock_needed[i].function, &match_lock_needed,
 472                                   (void *)lock_needed[i].lock);
 473         }
 474
 475         for (i = 0; conditional_funcs[i]; i++) {
 476                 add_conditional_hook(conditional_funcs[i],
 477                                   &match_locks_on_non_zero, NULL);
 478         }
 479
 480         for (i = 0; reverse_cond_funcs[i]; i++) {
 481                 return_implies_state(reverse_cond_funcs[i], whole_range.min, -1,
 482                                      &match_lock_failed, NULL);
 483                 return_implies_state(reverse_cond_funcs[i], 0, 0,
 484                                      &match_lock_aquired, NULL);
 485
 486         }
 487 }