linux/lib/locking-selftest.c
<<
>>
Prefs
   1/*
   2 * lib/locking-selftest.c
   3 *
   4 * Testsuite for various locking APIs: spinlocks, rwlocks,
   5 * mutexes and rw-semaphores.
   6 *
   7 * It is checking both false positives and false negatives.
   8 *
   9 * Started by Ingo Molnar:
  10 *
  11 *  Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
  12 */
  13#include <linux/rwsem.h>
  14#include <linux/mutex.h>
  15#include <linux/sched.h>
  16#include <linux/delay.h>
  17#include <linux/module.h>
  18#include <linux/lockdep.h>
  19#include <linux/spinlock.h>
  20#include <linux/kallsyms.h>
  21#include <linux/interrupt.h>
  22#include <linux/debug_locks.h>
  23#include <linux/irqflags.h>
  24
  25/*
  26 * Change this to 1 if you want to see the failure printouts:
  27 */
  28static unsigned int debug_locks_verbose;
  29
  30static int __init setup_debug_locks_verbose(char *str)
  31{
  32        get_option(&str, &debug_locks_verbose);
  33
  34        return 1;
  35}
  36
  37__setup("debug_locks_verbose=", setup_debug_locks_verbose);
  38
  39#define FAILURE         0
  40#define SUCCESS         1
  41
  42#define LOCKTYPE_SPIN   0x1
  43#define LOCKTYPE_RWLOCK 0x2
  44#define LOCKTYPE_MUTEX  0x4
  45#define LOCKTYPE_RWSEM  0x8
  46
  47/*
  48 * Normal standalone locks, for the circular and irq-context
  49 * dependency tests:
  50 */
  51static DEFINE_SPINLOCK(lock_A);
  52static DEFINE_SPINLOCK(lock_B);
  53static DEFINE_SPINLOCK(lock_C);
  54static DEFINE_SPINLOCK(lock_D);
  55
  56static DEFINE_RWLOCK(rwlock_A);
  57static DEFINE_RWLOCK(rwlock_B);
  58static DEFINE_RWLOCK(rwlock_C);
  59static DEFINE_RWLOCK(rwlock_D);
  60
  61static DEFINE_MUTEX(mutex_A);
  62static DEFINE_MUTEX(mutex_B);
  63static DEFINE_MUTEX(mutex_C);
  64static DEFINE_MUTEX(mutex_D);
  65
  66static DECLARE_RWSEM(rwsem_A);
  67static DECLARE_RWSEM(rwsem_B);
  68static DECLARE_RWSEM(rwsem_C);
  69static DECLARE_RWSEM(rwsem_D);
  70
  71/*
  72 * Locks that we initialize dynamically as well so that
  73 * e.g. X1 and X2 becomes two instances of the same class,
  74 * but X* and Y* are different classes. We do this so that
  75 * we do not trigger a real lockup:
  76 */
  77static DEFINE_SPINLOCK(lock_X1);
  78static DEFINE_SPINLOCK(lock_X2);
  79static DEFINE_SPINLOCK(lock_Y1);
  80static DEFINE_SPINLOCK(lock_Y2);
  81static DEFINE_SPINLOCK(lock_Z1);
  82static DEFINE_SPINLOCK(lock_Z2);
  83
  84static DEFINE_RWLOCK(rwlock_X1);
  85static DEFINE_RWLOCK(rwlock_X2);
  86static DEFINE_RWLOCK(rwlock_Y1);
  87static DEFINE_RWLOCK(rwlock_Y2);
  88static DEFINE_RWLOCK(rwlock_Z1);
  89static DEFINE_RWLOCK(rwlock_Z2);
  90
  91static DEFINE_MUTEX(mutex_X1);
  92static DEFINE_MUTEX(mutex_X2);
  93static DEFINE_MUTEX(mutex_Y1);
  94static DEFINE_MUTEX(mutex_Y2);
  95static DEFINE_MUTEX(mutex_Z1);
  96static DEFINE_MUTEX(mutex_Z2);
  97
  98static DECLARE_RWSEM(rwsem_X1);
  99static DECLARE_RWSEM(rwsem_X2);
 100static DECLARE_RWSEM(rwsem_Y1);
 101static DECLARE_RWSEM(rwsem_Y2);
 102static DECLARE_RWSEM(rwsem_Z1);
 103static DECLARE_RWSEM(rwsem_Z2);
 104
 105/*
 106 * non-inlined runtime initializers, to let separate locks share
 107 * the same lock-class:
 108 */
 109#define INIT_CLASS_FUNC(class)                          \
 110static noinline void                                    \
 111init_class_##class(spinlock_t *lock, rwlock_t *rwlock, struct mutex *mutex, \
 112                 struct rw_semaphore *rwsem)            \
 113{                                                       \
 114        spin_lock_init(lock);                           \
 115        rwlock_init(rwlock);                            \
 116        mutex_init(mutex);                              \
 117        init_rwsem(rwsem);                              \
 118}
 119
 120INIT_CLASS_FUNC(X)
 121INIT_CLASS_FUNC(Y)
 122INIT_CLASS_FUNC(Z)
 123
 124static void init_shared_classes(void)
 125{
 126        init_class_X(&lock_X1, &rwlock_X1, &mutex_X1, &rwsem_X1);
 127        init_class_X(&lock_X2, &rwlock_X2, &mutex_X2, &rwsem_X2);
 128
 129        init_class_Y(&lock_Y1, &rwlock_Y1, &mutex_Y1, &rwsem_Y1);
 130        init_class_Y(&lock_Y2, &rwlock_Y2, &mutex_Y2, &rwsem_Y2);
 131
 132        init_class_Z(&lock_Z1, &rwlock_Z1, &mutex_Z1, &rwsem_Z1);
 133        init_class_Z(&lock_Z2, &rwlock_Z2, &mutex_Z2, &rwsem_Z2);
 134}
 135
 136/*
 137 * For spinlocks and rwlocks we also do hardirq-safe / softirq-safe tests.
 138 * The following functions use a lock from a simulated hardirq/softirq
 139 * context, causing the locks to be marked as hardirq-safe/softirq-safe:
 140 */
 141
 142#define HARDIRQ_DISABLE         local_irq_disable
 143#define HARDIRQ_ENABLE          local_irq_enable
 144
 145#define HARDIRQ_ENTER()                         \
 146        local_irq_disable();                    \
 147        irq_enter();                            \
 148        WARN_ON(!in_irq());
 149
 150#define HARDIRQ_EXIT()                          \
 151        __irq_exit();                           \
 152        local_irq_enable();
 153
 154#define SOFTIRQ_DISABLE         local_bh_disable
 155#define SOFTIRQ_ENABLE          local_bh_enable
 156
 157#define SOFTIRQ_ENTER()                         \
 158                local_bh_disable();             \
 159                local_irq_disable();            \
 160                lockdep_softirq_enter();        \
 161                WARN_ON(!in_softirq());
 162
 163#define SOFTIRQ_EXIT()                          \
 164                lockdep_softirq_exit();         \
 165                local_irq_enable();             \
 166                local_bh_enable();
 167
 168/*
 169 * Shortcuts for lock/unlock API variants, to keep
 170 * the testcases compact:
 171 */
 172#define L(x)                    spin_lock(&lock_##x)
 173#define U(x)                    spin_unlock(&lock_##x)
 174#define LU(x)                   L(x); U(x)
 175#define SI(x)                   spin_lock_init(&lock_##x)
 176
 177#define WL(x)                   write_lock(&rwlock_##x)
 178#define WU(x)                   write_unlock(&rwlock_##x)
 179#define WLU(x)                  WL(x); WU(x)
 180
 181#define RL(x)                   read_lock(&rwlock_##x)
 182#define RU(x)                   read_unlock(&rwlock_##x)
 183#define RLU(x)                  RL(x); RU(x)
 184#define RWI(x)                  rwlock_init(&rwlock_##x)
 185
 186#define ML(x)                   mutex_lock(&mutex_##x)
 187#define MU(x)                   mutex_unlock(&mutex_##x)
 188#define MI(x)                   mutex_init(&mutex_##x)
 189
 190#define WSL(x)                  down_write(&rwsem_##x)
 191#define WSU(x)                  up_write(&rwsem_##x)
 192
 193#define RSL(x)                  down_read(&rwsem_##x)
 194#define RSU(x)                  up_read(&rwsem_##x)
 195#define RWSI(x)                 init_rwsem(&rwsem_##x)
 196
 197#define LOCK_UNLOCK_2(x,y)      LOCK(x); LOCK(y); UNLOCK(y); UNLOCK(x)
 198
 199/*
 200 * Generate different permutations of the same testcase, using
 201 * the same basic lock-dependency/state events:
 202 */
 203
 204#define GENERATE_TESTCASE(name)                 \
 205                                                \
 206static void name(void) { E(); }
 207
 208#define GENERATE_PERMUTATIONS_2_EVENTS(name)    \
 209                                                \
 210static void name##_12(void) { E1(); E2(); }     \
 211static void name##_21(void) { E2(); E1(); }
 212
 213#define GENERATE_PERMUTATIONS_3_EVENTS(name)            \
 214                                                        \
 215static void name##_123(void) { E1(); E2(); E3(); }      \
 216static void name##_132(void) { E1(); E3(); E2(); }      \
 217static void name##_213(void) { E2(); E1(); E3(); }      \
 218static void name##_231(void) { E2(); E3(); E1(); }      \
 219static void name##_312(void) { E3(); E1(); E2(); }      \
 220static void name##_321(void) { E3(); E2(); E1(); }
 221
 222/*
 223 * AA deadlock:
 224 */
 225
 226#define E()                                     \
 227                                                \
 228        LOCK(X1);                               \
 229        LOCK(X2); /* this one should fail */
 230
 231/*
 232 * 6 testcases:
 233 */
 234#include "locking-selftest-spin.h"
 235GENERATE_TESTCASE(AA_spin)
 236#include "locking-selftest-wlock.h"
 237GENERATE_TESTCASE(AA_wlock)
 238#include "locking-selftest-rlock.h"
 239GENERATE_TESTCASE(AA_rlock)
 240#include "locking-selftest-mutex.h"
 241GENERATE_TESTCASE(AA_mutex)
 242#include "locking-selftest-wsem.h"
 243GENERATE_TESTCASE(AA_wsem)
 244#include "locking-selftest-rsem.h"
 245GENERATE_TESTCASE(AA_rsem)
 246
 247#undef E
 248
 249/*
 250 * Special-case for read-locking, they are
 251 * allowed to recurse on the same lock class:
 252 */
 253static void rlock_AA1(void)
 254{
 255        RL(X1);
 256        RL(X1); // this one should NOT fail
 257}
 258
 259static void rlock_AA1B(void)
 260{
 261        RL(X1);
 262        RL(X2); // this one should NOT fail
 263}
 264
 265static void rsem_AA1(void)
 266{
 267        RSL(X1);
 268        RSL(X1); // this one should fail
 269}
 270
 271static void rsem_AA1B(void)
 272{
 273        RSL(X1);
 274        RSL(X2); // this one should fail
 275}
 276/*
 277 * The mixing of read and write locks is not allowed:
 278 */
 279static void rlock_AA2(void)
 280{
 281        RL(X1);
 282        WL(X2); // this one should fail
 283}
 284
 285static void rsem_AA2(void)
 286{
 287        RSL(X1);
 288        WSL(X2); // this one should fail
 289}
 290
 291static void rlock_AA3(void)
 292{
 293        WL(X1);
 294        RL(X2); // this one should fail
 295}
 296
 297static void rsem_AA3(void)
 298{
 299        WSL(X1);
 300        RSL(X2); // this one should fail
 301}
 302
 303/*
 304 * ABBA deadlock:
 305 */
 306
 307#define E()                                     \
 308                                                \
 309        LOCK_UNLOCK_2(A, B);                    \
 310        LOCK_UNLOCK_2(B, A); /* fail */
 311
 312/*
 313 * 6 testcases:
 314 */
 315#include "locking-selftest-spin.h"
 316GENERATE_TESTCASE(ABBA_spin)
 317#include "locking-selftest-wlock.h"
 318GENERATE_TESTCASE(ABBA_wlock)
 319#include "locking-selftest-rlock.h"
 320GENERATE_TESTCASE(ABBA_rlock)
 321#include "locking-selftest-mutex.h"
 322GENERATE_TESTCASE(ABBA_mutex)
 323#include "locking-selftest-wsem.h"
 324GENERATE_TESTCASE(ABBA_wsem)
 325#include "locking-selftest-rsem.h"
 326GENERATE_TESTCASE(ABBA_rsem)
 327
 328#undef E
 329
 330/*
 331 * AB BC CA deadlock:
 332 */
 333
 334#define E()                                     \
 335                                                \
 336        LOCK_UNLOCK_2(A, B);                    \
 337        LOCK_UNLOCK_2(B, C);                    \
 338        LOCK_UNLOCK_2(C, A); /* fail */
 339
 340/*
 341 * 6 testcases:
 342 */
 343#include "locking-selftest-spin.h"
 344GENERATE_TESTCASE(ABBCCA_spin)
 345#include "locking-selftest-wlock.h"
 346GENERATE_TESTCASE(ABBCCA_wlock)
 347#include "locking-selftest-rlock.h"
 348GENERATE_TESTCASE(ABBCCA_rlock)
 349#include "locking-selftest-mutex.h"
 350GENERATE_TESTCASE(ABBCCA_mutex)
 351#include "locking-selftest-wsem.h"
 352GENERATE_TESTCASE(ABBCCA_wsem)
 353#include "locking-selftest-rsem.h"
 354GENERATE_TESTCASE(ABBCCA_rsem)
 355
 356#undef E
 357
 358/*
 359 * AB CA BC deadlock:
 360 */
 361
 362#define E()                                     \
 363                                                \
 364        LOCK_UNLOCK_2(A, B);                    \
 365        LOCK_UNLOCK_2(C, A);                    \
 366        LOCK_UNLOCK_2(B, C); /* fail */
 367
 368/*
 369 * 6 testcases:
 370 */
 371#include "locking-selftest-spin.h"
 372GENERATE_TESTCASE(ABCABC_spin)
 373#include "locking-selftest-wlock.h"
 374GENERATE_TESTCASE(ABCABC_wlock)
 375#include "locking-selftest-rlock.h"
 376GENERATE_TESTCASE(ABCABC_rlock)
 377#include "locking-selftest-mutex.h"
 378GENERATE_TESTCASE(ABCABC_mutex)
 379#include "locking-selftest-wsem.h"
 380GENERATE_TESTCASE(ABCABC_wsem)
 381#include "locking-selftest-rsem.h"
 382GENERATE_TESTCASE(ABCABC_rsem)
 383
 384#undef E
 385
 386/*
 387 * AB BC CD DA deadlock:
 388 */
 389
 390#define E()                                     \
 391                                                \
 392        LOCK_UNLOCK_2(A, B);                    \
 393        LOCK_UNLOCK_2(B, C);                    \
 394        LOCK_UNLOCK_2(C, D);                    \
 395        LOCK_UNLOCK_2(D, A); /* fail */
 396
 397/*
 398 * 6 testcases:
 399 */
 400#include "locking-selftest-spin.h"
 401GENERATE_TESTCASE(ABBCCDDA_spin)
 402#include "locking-selftest-wlock.h"
 403GENERATE_TESTCASE(ABBCCDDA_wlock)
 404#include "locking-selftest-rlock.h"
 405GENERATE_TESTCASE(ABBCCDDA_rlock)
 406#include "locking-selftest-mutex.h"
 407GENERATE_TESTCASE(ABBCCDDA_mutex)
 408#include "locking-selftest-wsem.h"
 409GENERATE_TESTCASE(ABBCCDDA_wsem)
 410#include "locking-selftest-rsem.h"
 411GENERATE_TESTCASE(ABBCCDDA_rsem)
 412
 413#undef E
 414
 415/*
 416 * AB CD BD DA deadlock:
 417 */
 418#define E()                                     \
 419                                                \
 420        LOCK_UNLOCK_2(A, B);                    \
 421        LOCK_UNLOCK_2(C, D);                    \
 422        LOCK_UNLOCK_2(B, D);                    \
 423        LOCK_UNLOCK_2(D, A); /* fail */
 424
 425/*
 426 * 6 testcases:
 427 */
 428#include "locking-selftest-spin.h"
 429GENERATE_TESTCASE(ABCDBDDA_spin)
 430#include "locking-selftest-wlock.h"
 431GENERATE_TESTCASE(ABCDBDDA_wlock)
 432#include "locking-selftest-rlock.h"
 433GENERATE_TESTCASE(ABCDBDDA_rlock)
 434#include "locking-selftest-mutex.h"
 435GENERATE_TESTCASE(ABCDBDDA_mutex)
 436#include "locking-selftest-wsem.h"
 437GENERATE_TESTCASE(ABCDBDDA_wsem)
 438#include "locking-selftest-rsem.h"
 439GENERATE_TESTCASE(ABCDBDDA_rsem)
 440
 441#undef E
 442
 443/*
 444 * AB CD BC DA deadlock:
 445 */
 446#define E()                                     \
 447                                                \
 448        LOCK_UNLOCK_2(A, B);                    \
 449        LOCK_UNLOCK_2(C, D);                    \
 450        LOCK_UNLOCK_2(B, C);                    \
 451        LOCK_UNLOCK_2(D, A); /* fail */
 452
 453/*
 454 * 6 testcases:
 455 */
 456#include "locking-selftest-spin.h"
 457GENERATE_TESTCASE(ABCDBCDA_spin)
 458#include "locking-selftest-wlock.h"
 459GENERATE_TESTCASE(ABCDBCDA_wlock)
 460#include "locking-selftest-rlock.h"
 461GENERATE_TESTCASE(ABCDBCDA_rlock)
 462#include "locking-selftest-mutex.h"
 463GENERATE_TESTCASE(ABCDBCDA_mutex)
 464#include "locking-selftest-wsem.h"
 465GENERATE_TESTCASE(ABCDBCDA_wsem)
 466#include "locking-selftest-rsem.h"
 467GENERATE_TESTCASE(ABCDBCDA_rsem)
 468
 469#undef E
 470
 471/*
 472 * Double unlock:
 473 */
 474#define E()                                     \
 475                                                \
 476        LOCK(A);                                \
 477        UNLOCK(A);                              \
 478        UNLOCK(A); /* fail */
 479
 480/*
 481 * 6 testcases:
 482 */
 483#include "locking-selftest-spin.h"
 484GENERATE_TESTCASE(double_unlock_spin)
 485#include "locking-selftest-wlock.h"
 486GENERATE_TESTCASE(double_unlock_wlock)
 487#include "locking-selftest-rlock.h"
 488GENERATE_TESTCASE(double_unlock_rlock)
 489#include "locking-selftest-mutex.h"
 490GENERATE_TESTCASE(double_unlock_mutex)
 491#include "locking-selftest-wsem.h"
 492GENERATE_TESTCASE(double_unlock_wsem)
 493#include "locking-selftest-rsem.h"
 494GENERATE_TESTCASE(double_unlock_rsem)
 495
 496#undef E
 497
 498/*
 499 * Bad unlock ordering:
 500 */
 501#define E()                                     \
 502                                                \
 503        LOCK(A);                                \
 504        LOCK(B);                                \
 505        UNLOCK(A); /* fail */                   \
 506        UNLOCK(B);
 507
 508/*
 509 * 6 testcases:
 510 */
 511#include "locking-selftest-spin.h"
 512GENERATE_TESTCASE(bad_unlock_order_spin)
 513#include "locking-selftest-wlock.h"
 514GENERATE_TESTCASE(bad_unlock_order_wlock)
 515#include "locking-selftest-rlock.h"
 516GENERATE_TESTCASE(bad_unlock_order_rlock)
 517#include "locking-selftest-mutex.h"
 518GENERATE_TESTCASE(bad_unlock_order_mutex)
 519#include "locking-selftest-wsem.h"
 520GENERATE_TESTCASE(bad_unlock_order_wsem)
 521#include "locking-selftest-rsem.h"
 522GENERATE_TESTCASE(bad_unlock_order_rsem)
 523
 524#undef E
 525
 526/*
 527 * initializing a held lock:
 528 */
 529#define E()                                     \
 530                                                \
 531        LOCK(A);                                \
 532        INIT(A); /* fail */
 533
 534/*
 535 * 6 testcases:
 536 */
 537#include "locking-selftest-spin.h"
 538GENERATE_TESTCASE(init_held_spin)
 539#include "locking-selftest-wlock.h"
 540GENERATE_TESTCASE(init_held_wlock)
 541#include "locking-selftest-rlock.h"
 542GENERATE_TESTCASE(init_held_rlock)
 543#include "locking-selftest-mutex.h"
 544GENERATE_TESTCASE(init_held_mutex)
 545#include "locking-selftest-wsem.h"
 546GENERATE_TESTCASE(init_held_wsem)
 547#include "locking-selftest-rsem.h"
 548GENERATE_TESTCASE(init_held_rsem)
 549
 550#undef E
 551
 552/*
 553 * locking an irq-safe lock with irqs enabled:
 554 */
 555#define E1()                            \
 556                                        \
 557        IRQ_ENTER();                    \
 558        LOCK(A);                        \
 559        UNLOCK(A);                      \
 560        IRQ_EXIT();
 561
 562#define E2()                            \
 563                                        \
 564        LOCK(A);                        \
 565        UNLOCK(A);
 566
 567/*
 568 * Generate 24 testcases:
 569 */
 570#include "locking-selftest-spin-hardirq.h"
 571GENERATE_PERMUTATIONS_2_EVENTS(irqsafe1_hard_spin)
 572
 573#include "locking-selftest-rlock-hardirq.h"
 574GENERATE_PERMUTATIONS_2_EVENTS(irqsafe1_hard_rlock)
 575
 576#include "locking-selftest-wlock-hardirq.h"
 577GENERATE_PERMUTATIONS_2_EVENTS(irqsafe1_hard_wlock)
 578
 579#include "locking-selftest-spin-softirq.h"
 580GENERATE_PERMUTATIONS_2_EVENTS(irqsafe1_soft_spin)
 581
 582#include "locking-selftest-rlock-softirq.h"
 583GENERATE_PERMUTATIONS_2_EVENTS(irqsafe1_soft_rlock)
 584
 585#include "locking-selftest-wlock-softirq.h"
 586GENERATE_PERMUTATIONS_2_EVENTS(irqsafe1_soft_wlock)
 587
 588#undef E1
 589#undef E2
 590
 591/*
 592 * Enabling hardirqs with a softirq-safe lock held:
 593 */
 594#define E1()                            \
 595                                        \
 596        SOFTIRQ_ENTER();                \
 597        LOCK(A);                        \
 598        UNLOCK(A);                      \
 599        SOFTIRQ_EXIT();
 600
 601#define E2()                            \
 602                                        \
 603        HARDIRQ_DISABLE();              \
 604        LOCK(A);                        \
 605        HARDIRQ_ENABLE();               \
 606        UNLOCK(A);
 607
 608/*
 609 * Generate 12 testcases:
 610 */
 611#include "locking-selftest-spin.h"
 612GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2A_spin)
 613
 614#include "locking-selftest-wlock.h"
 615GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2A_wlock)
 616
 617#include "locking-selftest-rlock.h"
 618GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2A_rlock)
 619
 620#undef E1
 621#undef E2
 622
 623/*
 624 * Enabling irqs with an irq-safe lock held:
 625 */
 626#define E1()                            \
 627                                        \
 628        IRQ_ENTER();                    \
 629        LOCK(A);                        \
 630        UNLOCK(A);                      \
 631        IRQ_EXIT();
 632
 633#define E2()                            \
 634                                        \
 635        IRQ_DISABLE();                  \
 636        LOCK(A);                        \
 637        IRQ_ENABLE();                   \
 638        UNLOCK(A);
 639
 640/*
 641 * Generate 24 testcases:
 642 */
 643#include "locking-selftest-spin-hardirq.h"
 644GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2B_hard_spin)
 645
 646#include "locking-selftest-rlock-hardirq.h"
 647GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2B_hard_rlock)
 648
 649#include "locking-selftest-wlock-hardirq.h"
 650GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2B_hard_wlock)
 651
 652#include "locking-selftest-spin-softirq.h"
 653GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2B_soft_spin)
 654
 655#include "locking-selftest-rlock-softirq.h"
 656GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2B_soft_rlock)
 657
 658#include "locking-selftest-wlock-softirq.h"
 659GENERATE_PERMUTATIONS_2_EVENTS(irqsafe2B_soft_wlock)
 660
 661#undef E1
 662#undef E2
 663
 664/*
 665 * Acquiring a irq-unsafe lock while holding an irq-safe-lock:
 666 */
 667#define E1()                            \
 668                                        \
 669        LOCK(A);                        \
 670        LOCK(B);                        \
 671        UNLOCK(B);                      \
 672        UNLOCK(A);                      \
 673
 674#define E2()                            \
 675                                        \
 676        LOCK(B);                        \
 677        UNLOCK(B);
 678
 679#define E3()                            \
 680                                        \
 681        IRQ_ENTER();                    \
 682        LOCK(A);                        \
 683        UNLOCK(A);                      \
 684        IRQ_EXIT();
 685
 686/*
 687 * Generate 36 testcases:
 688 */
 689#include "locking-selftest-spin-hardirq.h"
 690GENERATE_PERMUTATIONS_3_EVENTS(irqsafe3_hard_spin)
 691
 692#include "locking-selftest-rlock-hardirq.h"
 693GENERATE_PERMUTATIONS_3_EVENTS(irqsafe3_hard_rlock)
 694
 695#include "locking-selftest-wlock-hardirq.h"
 696GENERATE_PERMUTATIONS_3_EVENTS(irqsafe3_hard_wlock)
 697
 698#include "locking-selftest-spin-softirq.h"
 699GENERATE_PERMUTATIONS_3_EVENTS(irqsafe3_soft_spin)
 700
 701#include "locking-selftest-rlock-softirq.h"
 702GENERATE_PERMUTATIONS_3_EVENTS(irqsafe3_soft_rlock)
 703
 704#include "locking-selftest-wlock-softirq.h"
 705GENERATE_PERMUTATIONS_3_EVENTS(irqsafe3_soft_wlock)
 706
 707#undef E1
 708#undef E2
 709#undef E3
 710
 711/*
 712 * If a lock turns into softirq-safe, but earlier it took
 713 * a softirq-unsafe lock:
 714 */
 715
 716#define E1()                            \
 717        IRQ_DISABLE();                  \
 718        LOCK(A);                        \
 719        LOCK(B);                        \
 720        UNLOCK(B);                      \
 721        UNLOCK(A);                      \
 722        IRQ_ENABLE();
 723
 724#define E2()                            \
 725        LOCK(B);                        \
 726        UNLOCK(B);
 727
 728#define E3()                            \
 729        IRQ_ENTER();                    \
 730        LOCK(A);                        \
 731        UNLOCK(A);                      \
 732        IRQ_EXIT();
 733
 734/*
 735 * Generate 36 testcases:
 736 */
 737#include "locking-selftest-spin-hardirq.h"
 738GENERATE_PERMUTATIONS_3_EVENTS(irqsafe4_hard_spin)
 739
 740#include "locking-selftest-rlock-hardirq.h"
 741GENERATE_PERMUTATIONS_3_EVENTS(irqsafe4_hard_rlock)
 742
 743#include "locking-selftest-wlock-hardirq.h"
 744GENERATE_PERMUTATIONS_3_EVENTS(irqsafe4_hard_wlock)
 745
 746#include "locking-selftest-spin-softirq.h"
 747GENERATE_PERMUTATIONS_3_EVENTS(irqsafe4_soft_spin)
 748
 749#include "locking-selftest-rlock-softirq.h"
 750GENERATE_PERMUTATIONS_3_EVENTS(irqsafe4_soft_rlock)
 751
 752#include "locking-selftest-wlock-softirq.h"
 753GENERATE_PERMUTATIONS_3_EVENTS(irqsafe4_soft_wlock)
 754
 755#undef E1
 756#undef E2
 757#undef E3
 758
 759/*
 760 * read-lock / write-lock irq inversion.
 761 *
 762 * Deadlock scenario:
 763 *
 764 * CPU#1 is at #1, i.e. it has write-locked A, but has not
 765 * taken B yet.
 766 *
 767 * CPU#2 is at #2, i.e. it has locked B.
 768 *
 769 * Hardirq hits CPU#2 at point #2 and is trying to read-lock A.
 770 *
 771 * The deadlock occurs because CPU#1 will spin on B, and CPU#2
 772 * will spin on A.
 773 */
 774
 775#define E1()                            \
 776                                        \
 777        IRQ_DISABLE();                  \
 778        WL(A);                          \
 779        LOCK(B);                        \
 780        UNLOCK(B);                      \
 781        WU(A);                          \
 782        IRQ_ENABLE();
 783
 784#define E2()                            \
 785                                        \
 786        LOCK(B);                        \
 787        UNLOCK(B);
 788
 789#define E3()                            \
 790                                        \
 791        IRQ_ENTER();                    \
 792        RL(A);                          \
 793        RU(A);                          \
 794        IRQ_EXIT();
 795
 796/*
 797 * Generate 36 testcases:
 798 */
 799#include "locking-selftest-spin-hardirq.h"
 800GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_hard_spin)
 801
 802#include "locking-selftest-rlock-hardirq.h"
 803GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_hard_rlock)
 804
 805#include "locking-selftest-wlock-hardirq.h"
 806GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_hard_wlock)
 807
 808#include "locking-selftest-spin-softirq.h"
 809GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_soft_spin)
 810
 811#include "locking-selftest-rlock-softirq.h"
 812GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_soft_rlock)
 813
 814#include "locking-selftest-wlock-softirq.h"
 815GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_soft_wlock)
 816
 817#undef E1
 818#undef E2
 819#undef E3
 820
 821/*
 822 * read-lock / write-lock recursion that is actually safe.
 823 */
 824
 825#define E1()                            \
 826                                        \
 827        IRQ_DISABLE();                  \
 828        WL(A);                          \
 829        WU(A);                          \
 830        IRQ_ENABLE();
 831
 832#define E2()                            \
 833                                        \
 834        RL(A);                          \
 835        RU(A);                          \
 836
 837#define E3()                            \
 838                                        \
 839        IRQ_ENTER();                    \
 840        RL(A);                          \
 841        L(B);                           \
 842        U(B);                           \
 843        RU(A);                          \
 844        IRQ_EXIT();
 845
 846/*
 847 * Generate 12 testcases:
 848 */
 849#include "locking-selftest-hardirq.h"
 850GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_hard)
 851
 852#include "locking-selftest-softirq.h"
 853GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft)
 854
 855#undef E1
 856#undef E2
 857#undef E3
 858
 859/*
 860 * read-lock / write-lock recursion that is unsafe.
 861 */
 862
 863#define E1()                            \
 864                                        \
 865        IRQ_DISABLE();                  \
 866        L(B);                           \
 867        WL(A);                          \
 868        WU(A);                          \
 869        U(B);                           \
 870        IRQ_ENABLE();
 871
 872#define E2()                            \
 873                                        \
 874        RL(A);                          \
 875        RU(A);                          \
 876
 877#define E3()                            \
 878                                        \
 879        IRQ_ENTER();                    \
 880        L(B);                           \
 881        U(B);                           \
 882        IRQ_EXIT();
 883
 884/*
 885 * Generate 12 testcases:
 886 */
 887#include "locking-selftest-hardirq.h"
 888// GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_hard)
 889
 890#include "locking-selftest-softirq.h"
 891// GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft)
 892
 893#ifdef CONFIG_DEBUG_LOCK_ALLOC
 894# define I_SPINLOCK(x)  lockdep_reset_lock(&lock_##x.dep_map)
 895# define I_RWLOCK(x)    lockdep_reset_lock(&rwlock_##x.dep_map)
 896# define I_MUTEX(x)     lockdep_reset_lock(&mutex_##x.dep_map)
 897# define I_RWSEM(x)     lockdep_reset_lock(&rwsem_##x.dep_map)
 898#else
 899# define I_SPINLOCK(x)
 900# define I_RWLOCK(x)
 901# define I_MUTEX(x)
 902# define I_RWSEM(x)
 903#endif
 904
 905#define I1(x)                                   \
 906        do {                                    \
 907                I_SPINLOCK(x);                  \
 908                I_RWLOCK(x);                    \
 909                I_MUTEX(x);                     \
 910                I_RWSEM(x);                     \
 911        } while (0)
 912
 913#define I2(x)                                   \
 914        do {                                    \
 915                spin_lock_init(&lock_##x);      \
 916                rwlock_init(&rwlock_##x);       \
 917                mutex_init(&mutex_##x);         \
 918                init_rwsem(&rwsem_##x);         \
 919        } while (0)
 920
 921static void reset_locks(void)
 922{
 923        local_irq_disable();
 924        I1(A); I1(B); I1(C); I1(D);
 925        I1(X1); I1(X2); I1(Y1); I1(Y2); I1(Z1); I1(Z2);
 926        lockdep_reset();
 927        I2(A); I2(B); I2(C); I2(D);
 928        init_shared_classes();
 929        local_irq_enable();
 930}
 931
 932#undef I
 933
 934static int testcase_total;
 935static int testcase_successes;
 936static int expected_testcase_failures;
 937static int unexpected_testcase_failures;
 938
 939static void dotest(void (*testcase_fn)(void), int expected, int lockclass_mask)
 940{
 941        unsigned long saved_preempt_count = preempt_count();
 942        int expected_failure = 0;
 943
 944        WARN_ON(irqs_disabled());
 945
 946        testcase_fn();
 947        /*
 948         * Filter out expected failures:
 949         */
 950#ifndef CONFIG_PROVE_LOCKING
 951        if ((lockclass_mask & LOCKTYPE_SPIN) && debug_locks != expected)
 952                expected_failure = 1;
 953        if ((lockclass_mask & LOCKTYPE_RWLOCK) && debug_locks != expected)
 954                expected_failure = 1;
 955        if ((lockclass_mask & LOCKTYPE_MUTEX) && debug_locks != expected)
 956                expected_failure = 1;
 957        if ((lockclass_mask & LOCKTYPE_RWSEM) && debug_locks != expected)
 958                expected_failure = 1;
 959#endif
 960        if (debug_locks != expected) {
 961                if (expected_failure) {
 962                        expected_testcase_failures++;
 963                        printk("failed|");
 964                } else {
 965                        unexpected_testcase_failures++;
 966
 967                        printk("FAILED|");
 968                        dump_stack();
 969                }
 970        } else {
 971                testcase_successes++;
 972                printk("  ok  |");
 973        }
 974        testcase_total++;
 975
 976        if (debug_locks_verbose)
 977                printk(" lockclass mask: %x, debug_locks: %d, expected: %d\n",
 978                        lockclass_mask, debug_locks, expected);
 979        /*
 980         * Some tests (e.g. double-unlock) might corrupt the preemption
 981         * count, so restore it:
 982         */
 983        preempt_count() = saved_preempt_count;
 984#ifdef CONFIG_TRACE_IRQFLAGS
 985        if (softirq_count())
 986                current->softirqs_enabled = 0;
 987        else
 988                current->softirqs_enabled = 1;
 989#endif
 990
 991        reset_locks();
 992}
 993
 994static inline void print_testname(const char *testname)
 995{
 996        printk("%33s:", testname);
 997}
 998
 999#define DO_TESTCASE_1(desc, name, nr)                           \
1000        print_testname(desc"/"#nr);                             \
1001        dotest(name##_##nr, SUCCESS, LOCKTYPE_RWLOCK);          \
1002        printk("\n");
1003
1004#define DO_TESTCASE_1B(desc, name, nr)                          \
1005        print_testname(desc"/"#nr);                             \
1006        dotest(name##_##nr, FAILURE, LOCKTYPE_RWLOCK);          \
1007        printk("\n");
1008
1009#define DO_TESTCASE_3(desc, name, nr)                           \
1010        print_testname(desc"/"#nr);                             \
1011        dotest(name##_spin_##nr, FAILURE, LOCKTYPE_SPIN);       \
1012        dotest(name##_wlock_##nr, FAILURE, LOCKTYPE_RWLOCK);    \
1013        dotest(name##_rlock_##nr, SUCCESS, LOCKTYPE_RWLOCK);    \
1014        printk("\n");
1015
1016#define DO_TESTCASE_3RW(desc, name, nr)                         \
1017        print_testname(desc"/"#nr);                             \
1018        dotest(name##_spin_##nr, FAILURE, LOCKTYPE_SPIN|LOCKTYPE_RWLOCK);\
1019        dotest(name##_wlock_##nr, FAILURE, LOCKTYPE_RWLOCK);    \
1020        dotest(name##_rlock_##nr, SUCCESS, LOCKTYPE_RWLOCK);    \
1021        printk("\n");
1022
1023#define DO_TESTCASE_6(desc, name)                               \
1024        print_testname(desc);                                   \
1025        dotest(name##_spin, FAILURE, LOCKTYPE_SPIN);            \
1026        dotest(name##_wlock, FAILURE, LOCKTYPE_RWLOCK);         \
1027        dotest(name##_rlock, FAILURE, LOCKTYPE_RWLOCK);         \
1028        dotest(name##_mutex, FAILURE, LOCKTYPE_MUTEX);          \
1029        dotest(name##_wsem, FAILURE, LOCKTYPE_RWSEM);           \
1030        dotest(name##_rsem, FAILURE, LOCKTYPE_RWSEM);           \
1031        printk("\n");
1032
1033#define DO_TESTCASE_6_SUCCESS(desc, name)                       \
1034        print_testname(desc);                                   \
1035        dotest(name##_spin, SUCCESS, LOCKTYPE_SPIN);            \
1036        dotest(name##_wlock, SUCCESS, LOCKTYPE_RWLOCK);         \
1037        dotest(name##_rlock, SUCCESS, LOCKTYPE_RWLOCK);         \
1038        dotest(name##_mutex, SUCCESS, LOCKTYPE_MUTEX);          \
1039        dotest(name##_wsem, SUCCESS, LOCKTYPE_RWSEM);           \
1040        dotest(name##_rsem, SUCCESS, LOCKTYPE_RWSEM);           \
1041        printk("\n");
1042
1043/*
1044 * 'read' variant: rlocks must not trigger.
1045 */
1046#define DO_TESTCASE_6R(desc, name)                              \
1047        print_testname(desc);                                   \
1048        dotest(name##_spin, FAILURE, LOCKTYPE_SPIN);            \
1049        dotest(name##_wlock, FAILURE, LOCKTYPE_RWLOCK);         \
1050        dotest(name##_rlock, SUCCESS, LOCKTYPE_RWLOCK);         \
1051        dotest(name##_mutex, FAILURE, LOCKTYPE_MUTEX);          \
1052        dotest(name##_wsem, FAILURE, LOCKTYPE_RWSEM);           \
1053        dotest(name##_rsem, FAILURE, LOCKTYPE_RWSEM);           \
1054        printk("\n");
1055
1056#define DO_TESTCASE_2I(desc, name, nr)                          \
1057        DO_TESTCASE_1("hard-"desc, name##_hard, nr);            \
1058        DO_TESTCASE_1("soft-"desc, name##_soft, nr);
1059
1060#define DO_TESTCASE_2IB(desc, name, nr)                         \
1061        DO_TESTCASE_1B("hard-"desc, name##_hard, nr);           \
1062        DO_TESTCASE_1B("soft-"desc, name##_soft, nr);
1063
1064#define DO_TESTCASE_6I(desc, name, nr)                          \
1065        DO_TESTCASE_3("hard-"desc, name##_hard, nr);            \
1066        DO_TESTCASE_3("soft-"desc, name##_soft, nr);
1067
1068#define DO_TESTCASE_6IRW(desc, name, nr)                        \
1069        DO_TESTCASE_3RW("hard-"desc, name##_hard, nr);          \
1070        DO_TESTCASE_3RW("soft-"desc, name##_soft, nr);
1071
1072#define DO_TESTCASE_2x3(desc, name)                             \
1073        DO_TESTCASE_3(desc, name, 12);                          \
1074        DO_TESTCASE_3(desc, name, 21);
1075
1076#define DO_TESTCASE_2x6(desc, name)                             \
1077        DO_TESTCASE_6I(desc, name, 12);                         \
1078        DO_TESTCASE_6I(desc, name, 21);
1079
1080#define DO_TESTCASE_6x2(desc, name)                             \
1081        DO_TESTCASE_2I(desc, name, 123);                        \
1082        DO_TESTCASE_2I(desc, name, 132);                        \
1083        DO_TESTCASE_2I(desc, name, 213);                        \
1084        DO_TESTCASE_2I(desc, name, 231);                        \
1085        DO_TESTCASE_2I(desc, name, 312);                        \
1086        DO_TESTCASE_2I(desc, name, 321);
1087
1088#define DO_TESTCASE_6x2B(desc, name)                            \
1089        DO_TESTCASE_2IB(desc, name, 123);                       \
1090        DO_TESTCASE_2IB(desc, name, 132);                       \
1091        DO_TESTCASE_2IB(desc, name, 213);                       \
1092        DO_TESTCASE_2IB(desc, name, 231);                       \
1093        DO_TESTCASE_2IB(desc, name, 312);                       \
1094        DO_TESTCASE_2IB(desc, name, 321);
1095
1096#define DO_TESTCASE_6x6(desc, name)                             \
1097        DO_TESTCASE_6I(desc, name, 123);                        \
1098        DO_TESTCASE_6I(desc, name, 132);                        \
1099        DO_TESTCASE_6I(desc, name, 213);                        \
1100        DO_TESTCASE_6I(desc, name, 231);                        \
1101        DO_TESTCASE_6I(desc, name, 312);                        \
1102        DO_TESTCASE_6I(desc, name, 321);
1103
1104#define DO_TESTCASE_6x6RW(desc, name)                           \
1105        DO_TESTCASE_6IRW(desc, name, 123);                      \
1106        DO_TESTCASE_6IRW(desc, name, 132);                      \
1107        DO_TESTCASE_6IRW(desc, name, 213);                      \
1108        DO_TESTCASE_6IRW(desc, name, 231);                      \
1109        DO_TESTCASE_6IRW(desc, name, 312);                      \
1110        DO_TESTCASE_6IRW(desc, name, 321);
1111
1112
1113void locking_selftest(void)
1114{
1115        /*
1116         * Got a locking failure before the selftest ran?
1117         */
1118        if (!debug_locks) {
1119                printk("----------------------------------\n");
1120                printk("| Locking API testsuite disabled |\n");
1121                printk("----------------------------------\n");
1122                return;
1123        }
1124
1125        /*
1126         * Run the testsuite:
1127         */
1128        printk("------------------------\n");
1129        printk("| Locking API testsuite:\n");
1130        printk("----------------------------------------------------------------------------\n");
1131        printk("                                 | spin |wlock |rlock |mutex | wsem | rsem |\n");
1132        printk("  --------------------------------------------------------------------------\n");
1133
1134        init_shared_classes();
1135        debug_locks_silent = !debug_locks_verbose;
1136
1137        DO_TESTCASE_6R("A-A deadlock", AA);
1138        DO_TESTCASE_6R("A-B-B-A deadlock", ABBA);
1139        DO_TESTCASE_6R("A-B-B-C-C-A deadlock", ABBCCA);
1140        DO_TESTCASE_6R("A-B-C-A-B-C deadlock", ABCABC);
1141        DO_TESTCASE_6R("A-B-B-C-C-D-D-A deadlock", ABBCCDDA);
1142        DO_TESTCASE_6R("A-B-C-D-B-D-D-A deadlock", ABCDBDDA);
1143        DO_TESTCASE_6R("A-B-C-D-B-C-D-A deadlock", ABCDBCDA);
1144        DO_TESTCASE_6("double unlock", double_unlock);
1145        DO_TESTCASE_6("initialize held", init_held);
1146        DO_TESTCASE_6_SUCCESS("bad unlock order", bad_unlock_order);
1147
1148        printk("  --------------------------------------------------------------------------\n");
1149        print_testname("recursive read-lock");
1150        printk("             |");
1151        dotest(rlock_AA1, SUCCESS, LOCKTYPE_RWLOCK);
1152        printk("             |");
1153        dotest(rsem_AA1, FAILURE, LOCKTYPE_RWSEM);
1154        printk("\n");
1155
1156        print_testname("recursive read-lock #2");
1157        printk("             |");
1158        dotest(rlock_AA1B, SUCCESS, LOCKTYPE_RWLOCK);
1159        printk("             |");
1160        dotest(rsem_AA1B, FAILURE, LOCKTYPE_RWSEM);
1161        printk("\n");
1162
1163        print_testname("mixed read-write-lock");
1164        printk("             |");
1165        dotest(rlock_AA2, FAILURE, LOCKTYPE_RWLOCK);
1166        printk("             |");
1167        dotest(rsem_AA2, FAILURE, LOCKTYPE_RWSEM);
1168        printk("\n");
1169
1170        print_testname("mixed write-read-lock");
1171        printk("             |");
1172        dotest(rlock_AA3, FAILURE, LOCKTYPE_RWLOCK);
1173        printk("             |");
1174        dotest(rsem_AA3, FAILURE, LOCKTYPE_RWSEM);
1175        printk("\n");
1176
1177        printk("  --------------------------------------------------------------------------\n");
1178
1179        /*
1180         * irq-context testcases:
1181         */
1182        DO_TESTCASE_2x6("irqs-on + irq-safe-A", irqsafe1);
1183        DO_TESTCASE_2x3("sirq-safe-A => hirqs-on", irqsafe2A);
1184        DO_TESTCASE_2x6("safe-A + irqs-on", irqsafe2B);
1185        DO_TESTCASE_6x6("safe-A + unsafe-B #1", irqsafe3);
1186        DO_TESTCASE_6x6("safe-A + unsafe-B #2", irqsafe4);
1187        DO_TESTCASE_6x6RW("irq lock-inversion", irq_inversion);
1188
1189        DO_TESTCASE_6x2("irq read-recursion", irq_read_recursion);
1190//      DO_TESTCASE_6x2B("irq read-recursion #2", irq_read_recursion2);
1191
1192        if (unexpected_testcase_failures) {
1193                printk("-----------------------------------------------------------------\n");
1194                debug_locks = 0;
1195                printk("BUG: %3d unexpected failures (out of %3d) - debugging disabled! |\n",
1196                        unexpected_testcase_failures, testcase_total);
1197                printk("-----------------------------------------------------------------\n");
1198        } else if (expected_testcase_failures && testcase_successes) {
1199                printk("--------------------------------------------------------\n");
1200                printk("%3d out of %3d testcases failed, as expected. |\n",
1201                        expected_testcase_failures, testcase_total);
1202                printk("----------------------------------------------------\n");
1203                debug_locks = 1;
1204        } else if (expected_testcase_failures && !testcase_successes) {
1205                printk("--------------------------------------------------------\n");
1206                printk("All %3d testcases failed, as expected. |\n",
1207                        expected_testcase_failures);
1208                printk("----------------------------------------\n");
1209                debug_locks = 1;
1210        } else {
1211                printk("-------------------------------------------------------\n");
1212                printk("Good, all %3d testcases passed! |\n",
1213                        testcase_successes);
1214                printk("---------------------------------\n");
1215                debug_locks = 1;
1216        }
1217        debug_locks_silent = 0;
1218}
1219