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         "__raw_spin_lock",
  23         "_spin_lock",
  24         "_spin_lock_irqsave",
  25         "_spin_lock_irq",
  26         "_spin_lock_bh",
  27         "_spin_lock_nested",
  28         "_spin_lock_irqsave_nested",
  29         "_raw_spin_lock",
  30         "_read_lock",
  31         "_read_lock_irqsave",
  32         "_read_lock_irq",
  33         "_read_lock_bh",
  34         "_write_lock",
  35         "_write_lock_irqsave",
  36         "_write_lock_irq",
  37         "_write_lock_bh",
  38         "down",
  39         "mutex_lock_nested",
  40         "mutex_lock",
  41         NULL,
  42 };
  43
  44 static const char *unlock_funcs[] = {
  45         "__raw_spin_unlock",
  46         "_spin_unlock",
  47         "_spin_unlock_irqrestore",
  48         "_spin_unlock_irq",
  49         "_spin_unlock_bh",
  50         "_raw_spin_unlock",
  51         "_read_unlock",
  52         "_read_unlock_irqrestore",
  53         "_read_unlock_irq",
  54         "_read_unlock_bh",
  55         "_write_unlock",
  56         "_write_unlock_irqrestore",
  57         "_write_unlock_irq",
  58         "_write_unlock_bh",
  59         "up",
  60         "mutex_unlock",
  61         NULL,
  62 };
  63
  64 /* These are return 1 if they aquire the lock */
  65 static const char *conditional_funcs[] = {
  66         "_spin_trylock",
  67         "_spin_trylock_bh",
  68         "_read_trylock",
  69         "_write_trylock",
  70         "generic__raw_read_trylock",
  71         "_raw_spin_trylock",
  72         "_raw_read_trylock",
  73         "_raw_write_trylock",
  74         "__raw_spin_trylock",
  75         "__raw_read_trylock",
  76         "__raw_write_trylock",
  77         "__raw_write_trylock",
  78         "mutex_trylock",
  79         NULL,
  80 };
  81
  82 /* These functions return 0 on success and negative on failure */
  83 static const char *reverse_cond_funcs[] = {
  84         "down_trylock",
  85         "down_interruptible",
  86         "mutex_lock_interruptible",
  87         "mutex_lock_interruptible_nested",
  88         "mutex_lock_killable",
  89         "mutex_lock_killable_nested",
  90         NULL,
  91 };
  92
  93 /* todo still need to handle__raw_spin_is_locked */
  94
  95 struct locked_call {
  96         const char *function;
  97         const char *lock;
  98 };
  99
 100 static struct locked_call lock_needed[] = {
 101         {"tty_ldisc_ref_wait", "tty_ldisc_lock"},
 102 };
 103
 104 static int my_id;
 105
 106 static struct tracker_list *starts_locked;
 107 static struct tracker_list *starts_unlocked;
 108
 109 struct locks_on_return {
 110         int line;
 111         struct tracker_list *locked;
 112         struct tracker_list *unlocked;
 113 };
 114 DECLARE_PTR_LIST(return_list, struct locks_on_return);
 115 static struct return_list *all_returns;
 116
 117 STATE(locked);
 118 STATE(start_state);
 119 STATE(unlocked);
 120
 121 static struct smatch_state *get_start_state(struct sm_state *sm)
 122 {
 123        int is_locked = 0;
 124        int is_unlocked = 0;
 125
 126        if (in_tracker_list(starts_locked, my_id, sm->name, sm->sym))
 127                is_locked = 1;
 128        if (in_tracker_list(starts_unlocked, my_id, sm->name, sm->sym))
 129                is_unlocked = 1;
 130        if (is_locked && is_unlocked)
 131                return &undefined;
 132        if (is_locked)
 133                return &locked;
 134        if (is_unlocked)
 135                return &unlocked;
 136         return &undefined;
 137 }
 138
 139 static struct smatch_state *unmatched_state(struct sm_state *sm)
 140 {
 141         return &start_state;
 142 }
 143
 144 static char *get_lock_name(struct expression *expr, void *data)
 145 {
 146         struct expression *lock_expr;
 147
 148         if (data) {
 149                 return alloc_string((char *)data);
 150         } else {
 151                 lock_expr = get_argument_from_call_expr(expr->args, 0);
 152                 return get_variable_from_expr(lock_expr, NULL);
 153         }
 154 }
 155
 156 static void match_lock_func(const char *fn, struct expression *expr, void *data)
 157 {
 158         char *lock_name;
 159         struct sm_state *sm;
 160
 161         lock_name = get_lock_name(expr, data);
 162         if (!lock_name)
 163                 return;
 164         sm = get_sm_state(my_id, lock_name, NULL);
 165         if (!sm)
 166                 add_tracker(&starts_unlocked, my_id, lock_name, NULL);
 167         if (sm && slist_has_state(sm->possible, &locked))
 168                 sm_msg("error: double lock '%s'", lock_name);
 169         set_state(my_id, lock_name, NULL, &locked);
 170         free_string(lock_name);
 171 }
 172
 173 static void match_unlock_func(const char *fn, struct expression *expr,
 174                               void *data)
 175 {
 176         char *lock_name;
 177         struct sm_state *sm;
 178
 179         lock_name = get_lock_name(expr, data);
 180         if (!lock_name)
 181                 return;
 182         sm = get_sm_state(my_id, lock_name, NULL);
 183         if (!sm)
 184                 add_tracker(&starts_locked, my_id, lock_name, NULL);
 185         if (sm && slist_has_state(sm->possible, &unlocked))
 186                 sm_msg("error: double unlock '%s'", lock_name);
 187         set_state(my_id, lock_name, NULL, &unlocked);
 188         free_string(lock_name);
 189 }
 190
 191 static void match_lock_failed(const char *fn, struct expression *expr,
 192                         struct expression *unused, void *data)
 193 {
 194         char *lock_name;
 195         struct sm_state *sm;
 196
 197         lock_name = get_lock_name(expr, data);
 198         if (!lock_name)
 199                 return;
 200         sm = get_sm_state(my_id, lock_name, NULL);
 201         if (!sm)
 202                 add_tracker(&starts_unlocked, my_id, lock_name, NULL);
 203         set_state(my_id, lock_name, NULL, &unlocked);
 204         free_string(lock_name);
 205 }
 206
 207 static void match_lock_aquired(const char *fn, struct expression *expr,
 208                         struct expression *unused, void *data)
 209 {
 210         char *lock_name;
 211         struct sm_state *sm;
 212
 213         lock_name = get_lock_name(expr, data);
 214         if (!lock_name)
 215                 return;
 216         sm = get_sm_state(my_id, lock_name, NULL);
 217         if (!sm)
 218                 add_tracker(&starts_unlocked, my_id, lock_name, NULL);
 219         if (sm && slist_has_state(sm->possible, &locked))
 220                 sm_msg("error: double lock '%s'", lock_name);
 221         set_state(my_id, lock_name, NULL, &locked);
 222         free_string(lock_name);
 223 }
 224
 225 static void match_lock_needed(const char *fn, struct expression *expr,
 226                               void *data)
 227 {
 228         struct smatch_state *state;
 229         char *fn_name;
 230
 231         state = get_state(my_id, (char *)data, NULL);
 232         if (state == &locked)
 233                 return;
 234         fn_name = get_variable_from_expr(expr->fn, NULL);
 235         if (!fn_name) {
 236                 sm_msg("Internal error.");
 237                 exit(1);
 238         }
 239         sm_msg("error: %s called without holding '%s' lock", fn_name,
 240                    (char *)data);
 241         free_string(fn_name);
 242 }
 243
 244 static void match_locks_on_non_zero(const char *fn, struct expression *expr,
 245                                    void *data)
 246 {
 247         char *lock_name;
 248         struct sm_state *sm;
 249
 250         lock_name = get_lock_name(expr, data);
 251         if (!lock_name)
 252                 return;
 253         sm = get_sm_state(my_id, lock_name, NULL);
 254         if (!sm)
 255                 add_tracker(&starts_unlocked, my_id, lock_name, NULL);
 256         set_true_false_states(my_id, lock_name, NULL, &locked, &unlocked);
 257         free_string(lock_name);
 258 }
 259
 260 static struct locks_on_return *alloc_return(int line)
 261 {
 262         struct locks_on_return *ret;
 263
 264         ret = malloc(sizeof(*ret));
 265         ret->line = line;
 266         ret->locked = NULL;
 267         ret->unlocked = NULL;
 268         return ret;
 269 }
 270
 271 static void check_possible(struct sm_state *sm)
 272 {
 273         struct sm_state *tmp;
 274         int islocked = 0;
 275         int isunlocked = 0;
 276         int undef = 0;
 277
 278         FOR_EACH_PTR(sm->possible, tmp) {
 279                 if (tmp->state == &locked)
 280                         islocked = 1;
 281                 if (tmp->state == &unlocked)
 282                         isunlocked = 1;
 283                 if (tmp->state == &start_state) {
 284                         struct smatch_state *s;
 285
 286                         s = get_start_state(tmp);
 287                         if (s == &locked)
 288                                 islocked = 1;
 289                         else if (s == &unlocked)
 290                                 isunlocked = 1;
 291                         else
 292                                 undef = 1;
 293                 }
 294                 if (tmp->state == &undefined)
 295                         undef = 1;  // i don't think this is possible any more.
 296         } END_FOR_EACH_PTR(tmp);
 297         if ((islocked && isunlocked) || undef)
 298                 sm_msg("warn: '%s' is sometimes locked here and "
 299                            "sometimes unlocked.", sm->name);
 300 }
 301
 302 static void match_return(struct expression *ret_value)
 303 {
 304         struct locks_on_return *ret;
 305         struct state_list *slist;
 306         struct sm_state *tmp;
 307
 308         if (!final_pass)
 309                 return;
 310
 311         ret = alloc_return(get_lineno());
 312
 313         slist = get_all_states(my_id);
 314         FOR_EACH_PTR(slist, tmp) {
 315                 if (tmp->state == &locked) {
 316                         add_tracker(&ret->locked, tmp->owner, tmp->name,
 317                                 tmp->sym);
 318                 } else if (tmp->state == &unlocked) {
 319                         add_tracker(&ret->unlocked, tmp->owner, tmp->name,
 320                                 tmp->sym);
 321                 } else if (tmp->state == &start_state) {
 322                         struct smatch_state *s;
 323
 324                         s = get_start_state(tmp);
 325                         if (s == &locked)
 326                                 add_tracker(&ret->locked, tmp->owner, tmp->name,
 327                                             tmp->sym);
 328                         if (s == &unlocked)
 329                                 add_tracker(&ret->unlocked, tmp->owner,tmp->name,
 330                                              tmp->sym);
 331                 }else {
 332                         check_possible(tmp);
 333                 }
 334         } END_FOR_EACH_PTR(tmp);
 335         free_slist(&slist);
 336         add_ptr_list(&all_returns, ret);
 337 }
 338
 339 static void print_inconsistent_returns(struct tracker *lock,
 340                                 struct smatch_state *start)
 341 {
 342         struct locks_on_return *tmp;
 343         int i;
 344
 345         sm_printf("%s +%d %s(%d) ", get_filename(), get_lineno(), get_function(), get_func_pos());
 346         sm_printf("warn: inconsistent returns %s:", lock->name);
 347         sm_printf(" locked (");
 348         i = 0;
 349         FOR_EACH_PTR(all_returns, tmp) {
 350                 if (in_tracker_list(tmp->unlocked, lock->owner, lock->name, lock->sym))
 351                         continue;
 352                 if (in_tracker_list(tmp->locked, lock->owner, lock->name, lock->sym)) {
 353                         if (i++)
 354                                 sm_printf(",");
 355                         sm_printf("%d", tmp->line);
 356                         continue;
 357                 }
 358                 if (start == &locked) {
 359                         if (i++)
 360                                 sm_printf(",");
 361                         sm_printf("%d", tmp->line);
 362                 }
 363         } END_FOR_EACH_PTR(tmp);
 364
 365         sm_printf(") unlocked (");
 366         i = 0;
 367         FOR_EACH_PTR(all_returns, tmp) {
 368                 if (in_tracker_list(tmp->unlocked, lock->owner, lock->name, lock->sym)) {
 369                         if (i++)
 370                                 sm_printf(",");
 371                         sm_printf("%d", tmp->line);
 372                         continue;
 373                 }
 374                 if (in_tracker_list(tmp->locked, lock->owner, lock->name, lock->sym)) {
 375                         continue;
 376                 }
 377                 if (start == &unlocked) {
 378                         if (i++)
 379                                 sm_printf(",");
 380                         sm_printf("%d", tmp->line);
 381                 }
 382         } END_FOR_EACH_PTR(tmp);
 383         sm_printf(")\n");
 384 }
 385
 386 static void check_returns_consistently(struct tracker *lock,
 387                                 struct smatch_state *start)
 388 {
 389         int returns_locked = 0;
 390         int returns_unlocked = 0;
 391         struct locks_on_return *tmp;
 392
 393         FOR_EACH_PTR(all_returns, tmp) {
 394                 if (in_tracker_list(tmp->unlocked, lock->owner, lock->name,
 395                                         lock->sym))
 396                         returns_unlocked = tmp->line;
 397                 else if (in_tracker_list(tmp->locked, lock->owner, lock->name,
 398                                                 lock->sym))
 399                         returns_locked = tmp->line;
 400                 else if (start == &locked)
 401                         returns_locked = tmp->line;
 402                 else if (start == &unlocked)
 403                         returns_unlocked = tmp->line;
 404         } END_FOR_EACH_PTR(tmp);
 405
 406         if (returns_locked && returns_unlocked)
 407                 print_inconsistent_returns(lock, start);
 408 }
 409
 410 static void check_consistency(struct symbol *sym)
 411 {
 412         struct tracker *tmp;
 413
 414         if (is_reachable())
 415                 match_return(NULL);
 416
 417         FOR_EACH_PTR(starts_locked, tmp) {
 418                 if (in_tracker_list(starts_unlocked, tmp->owner, tmp->name,
 419                                         tmp->sym))
 420                         sm_msg("error:  locking inconsistency.  We assume "
 421                                    "'%s' is both locked and unlocked at the "
 422                                    "start.",
 423                                 tmp->name);
 424         } END_FOR_EACH_PTR(tmp);
 425
 426         FOR_EACH_PTR(starts_locked, tmp) {
 427                 check_returns_consistently(tmp, &locked);
 428         } END_FOR_EACH_PTR(tmp);
 429
 430         FOR_EACH_PTR(starts_unlocked, tmp) {
 431                 check_returns_consistently(tmp, &unlocked);
 432         } END_FOR_EACH_PTR(tmp);
 433
 434 }
 435
 436 static void clear_lists(void)
 437 {
 438         struct locks_on_return *tmp;
 439
 440         free_trackers_and_list(&starts_locked);
 441         free_trackers_and_list(&starts_unlocked);
 442
 443         FOR_EACH_PTR(all_returns, tmp) {
 444                 free_trackers_and_list(&tmp->locked);
 445                 free_trackers_and_list(&tmp->unlocked);
 446                 free(tmp);
 447         } END_FOR_EACH_PTR(tmp);
 448         __free_ptr_list((struct ptr_list **)&all_returns);
 449 }
 450
 451 static void match_func_end(struct symbol *sym)
 452 {
 453         check_consistency(sym);
 454         clear_lists();
 455 }
 456
 457 void check_locking(int id)
 458 {
 459         int i;
 460
 461         if (option_project != PROJ_KERNEL)
 462                 return;
 463
 464         my_id = id;
 465         add_unmatched_state_hook(my_id, &unmatched_state);
 466         add_hook(&match_return, RETURN_HOOK);
 467         add_hook(&match_func_end, END_FUNC_HOOK);
 468
 469         for (i = 0; lock_funcs[i]; i++) {
 470                 add_function_hook(lock_funcs[i], &match_lock_func, NULL);
 471         }
 472         add_function_hook("lock_kernel", &match_lock_func, (void *)"kernel");
 473         for (i = 0; unlock_funcs[i]; i++) {
 474                 add_function_hook(unlock_funcs[i], &match_unlock_func, NULL);
 475         }
 476         add_function_hook("unlock_kernel", &match_unlock_func, (void *)"kernel");
 477         for (i = 0; i < sizeof(lock_needed)/sizeof(struct locked_call); i++) {
 478                 add_function_hook(lock_needed[i].function, &match_lock_needed,
 479                                   (void *)lock_needed[i].lock);
 480         }
 481
 482         for (i = 0; conditional_funcs[i]; i++) {
 483                 add_conditional_hook(conditional_funcs[i],
 484                                   &match_locks_on_non_zero, NULL);
 485         }
 486
 487         for (i = 0; reverse_cond_funcs[i]; i++) {
 488                 return_implies_state(reverse_cond_funcs[i], whole_range.min, -1,
 489                                      &match_lock_failed, NULL);
 490                 return_implies_state(reverse_cond_funcs[i], 0, 0,
 491                                      &match_lock_aquired, NULL);
 492
 493         }
 494 }