xpcom/tests/TestDeadlockDetector.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: sw=4 ts=4 et :
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is mozilla.org code.
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Mozilla Corporation.
  20  * Portions created by the Initial Developer are Copyright (C) 2009
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Chris Jones <jones.chris.g@gmail.com>
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #include "prenv.h"
  41 #include "prerror.h"
  42 #include "prio.h"
  43 #include "prproces.h"
  44
  45 #include "nsMemory.h"
  46
  47 #include "mozilla/CondVar.h"
  48 #include "mozilla/Monitor.h"
  49 #include "mozilla/Mutex.h"
  50
  51 #include "TestHarness.h"
  52
  53 using namespace mozilla;
  54
  55 static PRThread*
  56 spawn(void (*run)(void*), void* arg)
  57 {
  58     return PR_CreateThread(PR_SYSTEM_THREAD,
  59                            run,
  60                            arg,
  61                            PR_PRIORITY_NORMAL,
  62                            PR_GLOBAL_THREAD,
  63                            PR_JOINABLE_THREAD,
  64                            0);
  65 }
  66
  67 #define PASS()                                  \
  68     do {                                        \
  69         passed(__FUNCTION__);                   \
  70         return NS_OK;                           \
  71     } while (0);
  72
  73
  74 #define FAIL(why)                               \
  75     do {                                        \
  76         fail(why);                              \
  77         return NS_ERROR_FAILURE;                \
  78     } while (0);
  79
  80 //-----------------------------------------------------------------------------
  81
  82 static const char* sPathToThisBinary;
  83 static const char* sAssertBehaviorEnv = "XPCOM_DEBUG_BREAK=abort";
  84
  85 class Subprocess
  86 {
  87 public:
  88     // not available until process finishes
  89     PRInt32 mExitCode;
  90     nsCString mStdout;
  91     nsCString mStderr;
  92
  93     Subprocess(const char* aTestName) {
  94         // set up stdio redirection
  95         PRFileDesc* readStdin;  PRFileDesc* writeStdin;
  96         PRFileDesc* readStdout; PRFileDesc* writeStdout;
  97         PRFileDesc* readStderr; PRFileDesc* writeStderr;
  98         PRProcessAttr* pattr = PR_NewProcessAttr();
  99
 100         NS_ASSERTION(pattr, "couldn't allocate process attrs");
 101
 102         NS_ASSERTION(PR_SUCCESS == PR_CreatePipe(&readStdin, &writeStdin),
 103                      "couldn't create child stdin pipe");
 104         NS_ASSERTION(PR_SUCCESS == PR_SetFDInheritable(readStdin, PR_TRUE),
 105                      "couldn't set child stdin inheritable");
 106         PR_ProcessAttrSetStdioRedirect(pattr, PR_StandardInput, readStdin);
 107
 108         NS_ASSERTION(PR_SUCCESS == PR_CreatePipe(&readStdout, &writeStdout),
 109                      "couldn't create child stdout pipe");
 110         NS_ASSERTION(PR_SUCCESS == PR_SetFDInheritable(writeStdout, PR_TRUE),
 111                      "couldn't set child stdout inheritable");
 112         PR_ProcessAttrSetStdioRedirect(pattr, PR_StandardOutput, writeStdout);
 113
 114         NS_ASSERTION(PR_SUCCESS == PR_CreatePipe(&readStderr, &writeStderr),
 115                      "couldn't create child stderr pipe");
 116         NS_ASSERTION(PR_SUCCESS == PR_SetFDInheritable(writeStderr, PR_TRUE),
 117                      "couldn't set child stderr inheritable");
 118         PR_ProcessAttrSetStdioRedirect(pattr, PR_StandardError, writeStderr);
 119
 120         // set up argv with test name to run
 121         char* const newArgv[3] = {
 122             strdup(sPathToThisBinary),
 123             strdup(aTestName),
 124             0
 125         };
 126
 127         // make sure the child will abort if an assertion fails
 128         NS_ASSERTION(PR_SUCCESS == PR_SetEnv(sAssertBehaviorEnv),
 129                      "couldn't set XPCOM_DEBUG_BREAK env var");
 130
 131         PRProcess* proc;
 132         NS_ASSERTION(proc = PR_CreateProcess(sPathToThisBinary,
 133                                              newArgv,
 134                                              0, // inherit environment
 135                                              pattr),
 136                      "couldn't create process");
 137         PR_Close(readStdin);
 138         PR_Close(writeStdout);
 139         PR_Close(writeStderr);
 140
 141         mProc = proc;
 142         mStdinfd = writeStdin;
 143         mStdoutfd = readStdout;
 144         mStderrfd = readStderr;
 145
 146         free(newArgv[0]);
 147         free(newArgv[1]);
 148         PR_DestroyProcessAttr(pattr);
 149     }
 150
 151     void RunToCompletion(PRUint32 aWaitMs)
 152     {
 153         PR_Close(mStdinfd);
 154
 155         PRPollDesc pollfds[2];
 156         PRInt32 nfds;
 157         PRBool stdoutOpen = PR_TRUE, stderrOpen = PR_TRUE;
 158         char buf[4096];
 159         PRInt32 len;
 160
 161         PRIntervalTime now = PR_IntervalNow();
 162         PRIntervalTime deadline = now + PR_MillisecondsToInterval(aWaitMs);
 163
 164         while ((stdoutOpen || stderrOpen) && now < deadline) {
 165             nfds = 0;
 166             if (stdoutOpen) {
 167                 pollfds[nfds].fd = mStdoutfd;
 168                 pollfds[nfds].in_flags = PR_POLL_READ;
 169                 pollfds[nfds].out_flags = 0;
 170                 ++nfds;
 171             }
 172             if (stderrOpen) {
 173                 pollfds[nfds].fd = mStderrfd;
 174                 pollfds[nfds].in_flags = PR_POLL_READ;
 175                 pollfds[nfds].out_flags = 0;
 176                 ++nfds;
 177             }
 178
 179             PRInt32 rv = PR_Poll(pollfds, nfds, deadline - now);
 180             NS_ASSERTION(0 <= rv, PR_ErrorToName(PR_GetError()));
 181
 182             if (0 == rv) {      // timeout
 183                 fputs("(timed out!)\n", stderr);
 184                 Finish(PR_FALSE); // abnormal
 185                 return;
 186             }
 187
 188             for (PRInt32 i = 0; i < nfds; ++i) {
 189                 if (!pollfds[i].out_flags)
 190                     continue;
 191
 192                 PRBool isStdout = mStdoutfd == pollfds[i].fd;
 193
 194                 if (PR_POLL_READ & pollfds[i].out_flags) {
 195                     len = PR_Read(pollfds[i].fd, buf, sizeof(buf) - 1);
 196                     NS_ASSERTION(0 <= len, PR_ErrorToName(PR_GetError()));
 197                 }
 198                 else if (PR_POLL_HUP & pollfds[i].out_flags) {
 199                     len = 0;
 200                 }
 201                 else {
 202                     NS_ERROR(PR_ErrorToName(PR_GetError()));
 203                 }
 204
 205                 if (0 < len) {
 206                     buf[len] = '\0';
 207                     if (isStdout)
 208                         mStdout += buf;
 209                     else
 210                         mStderr += buf;
 211                 }
 212                 else if (isStdout) {
 213                     stdoutOpen = PR_FALSE;
 214                 }
 215                 else {
 216                     stderrOpen = PR_FALSE;
 217                 }
 218             }
 219
 220             now = PR_IntervalNow();
 221         }
 222
 223         if (stdoutOpen)
 224             fputs("(stdout still open!)\n", stderr);
 225         if (stderrOpen)
 226             fputs("(stderr still open!)\n", stderr);
 227         if (now > deadline)
 228             fputs("(timed out!)\n", stderr);
 229
 230         Finish(!stdoutOpen && !stderrOpen && now <= deadline);
 231     }
 232
 233 private:
 234     void Finish(PRBool normalExit) {
 235         if (!normalExit) {
 236             PR_KillProcess(mProc);
 237             mExitCode = -1;
 238             PRInt32 dummy;
 239             PR_WaitProcess(mProc, &dummy);
 240         }
 241         else {
 242             PR_WaitProcess(mProc, &mExitCode); // this had better not block ...
 243         }
 244
 245         PR_Close(mStdoutfd);
 246         PR_Close(mStderrfd);
 247     }
 248
 249     PRProcess* mProc;
 250     PRFileDesc* mStdinfd;         // writeable
 251     PRFileDesc* mStdoutfd;        // readable
 252     PRFileDesc* mStderrfd;        // readable
 253 };
 254
 255 //-----------------------------------------------------------------------------
 256 // Harness for checking detector errors
 257 bool
 258 CheckForDeadlock(const char* test, const char* const* findTokens)
 259 {
 260     Subprocess proc(test);
 261     proc.RunToCompletion(1000);
 262
 263     if (0 == proc.mExitCode)
 264         return false;
 265
 266     PRInt32 idx = 0;
 267     for (const char* const* tp = findTokens; *tp; ++tp) {
 268         const char* const token = *tp;
 269 #ifdef MOZILLA_INTERNAL_API
 270         idx = proc.mStderr.Find(token, PR_FALSE, idx);
 271 #else
 272         nsCString tokenCString(token);
 273         idx = proc.mStderr.Find(tokenCString, idx);
 274 #endif
 275         if (-1 == idx) {
 276             printf("(missed token '%s' in output)\n", token);
 277             puts("----------------------------------\n");
 278             puts(proc.mStderr.get());
 279             puts("----------------------------------\n");
 280             return false;
 281         }
 282         idx += strlen(token);
 283     }
 284
 285     return true;
 286 }
 287
 288 //-----------------------------------------------------------------------------
 289 // Single-threaded sanity tests
 290
 291 // Stupidest possible deadlock.
 292 nsresult
 293 Sanity_Child()
 294 {
 295     mozilla::Mutex m1("dd.sanity.m1");
 296     m1.Lock();
 297     m1.Lock();
 298     return 0;                  // not reached
 299 }
 300
 301 nsresult
 302 Sanity()
 303 {
 304     const char* const tokens[] = {
 305         "###!!! ERROR: Potential deadlock detected",
 306         "=== Cyclical dependency starts at\n--- Mutex : dd.sanity.m1",
 307         "=== Cycle completed at\n--- Mutex : dd.sanity.m1",
 308         "###!!! Deadlock may happen NOW!", // better catch these easy cases...
 309         "###!!! ASSERTION: Potential deadlock detected",
 310         0
 311     };
 312     if (CheckForDeadlock("Sanity", tokens)) {
 313         PASS();
 314     } else {
 315         FAIL("deadlock not detected");
 316     }
 317 }
 318
 319 // Slightly less stupid deadlock.
 320 nsresult
 321 Sanity2_Child()
 322 {
 323     mozilla::Mutex m1("dd.sanity2.m1");
 324     mozilla::Mutex m2("dd.sanity2.m2");
 325     m1.Lock();
 326     m2.Lock();
 327     m1.Lock();
 328     return 0;                  // not reached
 329 }
 330
 331 nsresult
 332 Sanity2()
 333 {
 334     const char* const tokens[] = {
 335         "###!!! ERROR: Potential deadlock detected",
 336         "=== Cyclical dependency starts at\n--- Mutex : dd.sanity2.m1",
 337         "--- Next dependency:\n--- Mutex : dd.sanity2.m2",
 338         "=== Cycle completed at\n--- Mutex : dd.sanity2.m1",
 339         "###!!! Deadlock may happen NOW!", // better catch these easy cases...
 340         "###!!! ASSERTION: Potential deadlock detected",
 341         0
 342     };
 343     if (CheckForDeadlock("Sanity2", tokens)) {
 344         PASS();
 345     } else {
 346         FAIL("deadlock not detected");
 347     }
 348 }
 349
 350
 351 nsresult
 352 Sanity3_Child()
 353 {
 354     mozilla::Mutex m1("dd.sanity3.m1");
 355     mozilla::Mutex m2("dd.sanity3.m2");
 356     mozilla::Mutex m3("dd.sanity3.m3");
 357     mozilla::Mutex m4("dd.sanity3.m4");
 358
 359     m1.Lock();
 360     m2.Lock();
 361     m3.Lock();
 362     m4.Lock();
 363     m4.Unlock();
 364     m3.Unlock();
 365     m2.Unlock();
 366     m1.Unlock();
 367
 368     m4.Lock();
 369     m1.Lock();
 370     return 0;
 371 }
 372
 373 nsresult
 374 Sanity3()
 375 {
 376     const char* const tokens[] = {
 377         "###!!! ERROR: Potential deadlock detected",
 378         "=== Cyclical dependency starts at\n--- Mutex : dd.sanity3.m1",
 379         "--- Next dependency:\n--- Mutex : dd.sanity3.m2",
 380         "--- Next dependency:\n--- Mutex : dd.sanity3.m3",
 381         "--- Next dependency:\n--- Mutex : dd.sanity3.m4",
 382         "=== Cycle completed at\n--- Mutex : dd.sanity3.m1",
 383         "###!!! ASSERTION: Potential deadlock detected",
 384         0
 385     };
 386     if (CheckForDeadlock("Sanity3", tokens)) {
 387         PASS();
 388     } else {
 389         FAIL("deadlock not detected");
 390     }
 391 }
 392
 393
 394 nsresult
 395 Sanity4_Child()
 396 {
 397     mozilla::Monitor m1("dd.sanity4.m1");
 398     mozilla::Mutex m2("dd.sanity4.m2");
 399     m1.Enter();
 400     m2.Lock();
 401     m1.Enter();
 402     return 0;
 403 }
 404
 405 nsresult
 406 Sanity4()
 407 {
 408     const char* const tokens[] = {
 409         "Re-entering Monitor after acquiring other resources",
 410         "###!!! ERROR: Potential deadlock detected",
 411         "=== Cyclical dependency starts at\n--- Monitor : dd.sanity4.m1",
 412         "--- Next dependency:\n--- Mutex : dd.sanity4.m2",
 413         "=== Cycle completed at\n--- Monitor : dd.sanity4.m1",
 414         "###!!! ASSERTION: Potential deadlock detected",
 415         0
 416     };
 417     if (CheckForDeadlock("Sanity4", tokens)) {
 418         PASS();
 419     } else {
 420         FAIL("deadlock not detected");
 421     }
 422 }
 423
 424 //-----------------------------------------------------------------------------
 425 // Multithreaded tests
 426
 427 mozilla::Mutex* ttM1;
 428 mozilla::Mutex* ttM2;
 429
 430 static void
 431 TwoThreads_thread(void* arg)
 432 {
 433     PRInt32 m1First = NS_PTR_TO_INT32(arg);
 434     if (m1First) {
 435         ttM1->Lock();
 436         ttM2->Lock();
 437         ttM2->Unlock();
 438         ttM1->Unlock();
 439     }
 440     else {
 441         ttM2->Lock();
 442         ttM1->Lock();
 443         ttM1->Unlock();
 444         ttM2->Unlock();
 445     }
 446 }
 447
 448 nsresult
 449 TwoThreads_Child()
 450 {
 451     ttM1 = new mozilla::Mutex("dd.twothreads.m1");
 452     ttM2 = new mozilla::Mutex("dd.twothreads.m2");
 453     if (!ttM1 || !ttM2)
 454         NS_RUNTIMEABORT("couldn't allocate mutexes");
 455
 456     PRThread* t1 = spawn(TwoThreads_thread, (void*) 0);
 457     PR_JoinThread(t1);
 458
 459     PRThread* t2 = spawn(TwoThreads_thread, (void*) 1);
 460     PR_JoinThread(t2);
 461
 462     return 0;
 463 }
 464
 465 nsresult
 466 TwoThreads()
 467 {
 468     const char* const tokens[] = {
 469         "###!!! ERROR: Potential deadlock detected",
 470         "=== Cyclical dependency starts at\n--- Mutex : dd.twothreads.m2",
 471         "--- Next dependency:\n--- Mutex : dd.twothreads.m1",
 472         "=== Cycle completed at\n--- Mutex : dd.twothreads.m2",
 473         "###!!! ASSERTION: Potential deadlock detected",
 474         0
 475     };
 476
 477     if (CheckForDeadlock("TwoThreads", tokens)) {
 478         PASS();
 479     } else {
 480         FAIL("deadlock not detected");
 481     }
 482 }
 483
 484
 485 mozilla::Mutex* cndMs[4];
 486 const PRUint32 K = 100000;
 487
 488 static void
 489 ContentionNoDeadlock_thread(void* arg)
 490 {
 491     PRInt32 starti = NS_PTR_TO_INT32(arg);
 492
 493     for (PRUint32 k = 0; k < K; ++k) {
 494         for (PRInt32 i = starti; i < (PRInt32) NS_ARRAY_LENGTH(cndMs); ++i)
 495             cndMs[i]->Lock();
 496         // comment out the next two lines for deadlocking fun!
 497         for (PRInt32 i = NS_ARRAY_LENGTH(cndMs) - 1; i >= starti; --i)
 498             cndMs[i]->Unlock();
 499
 500         starti = (starti + 1) % 3;
 501     }
 502 }
 503
 504 nsresult
 505 ContentionNoDeadlock_Child()
 506 {
 507     PRThread* threads[3];
 508
 509     for (PRUint32 i = 0; i < NS_ARRAY_LENGTH(cndMs); ++i)
 510         cndMs[i] = new mozilla::Mutex("dd.cnd.ms");
 511
 512     for (PRInt32 i = 0; i < (PRInt32) NS_ARRAY_LENGTH(threads); ++i)
 513         threads[i] = spawn(ContentionNoDeadlock_thread, NS_INT32_TO_PTR(i));
 514
 515     for (PRUint32 i = 0; i < NS_ARRAY_LENGTH(threads); ++i)
 516         PR_JoinThread(threads[i]);
 517
 518     for (PRUint32 i = 0; i < NS_ARRAY_LENGTH(cndMs); ++i)
 519         delete cndMs[i];
 520
 521     return 0;
 522 }
 523
 524 nsresult
 525 ContentionNoDeadlock()
 526 {
 527     const char * func = __func__;
 528     Subprocess proc(func);
 529     proc.RunToCompletion(60000);
 530     if (0 != proc.mExitCode) {
 531         printf("(expected 0 == return code, got %d)\n", proc.mExitCode);
 532         puts("(output)\n----------------------------------\n");
 533         puts(proc.mStdout.get());
 534         puts("----------------------------------\n");
 535         puts("(error output)\n----------------------------------\n");
 536         puts(proc.mStderr.get());
 537         puts("----------------------------------\n");
 538
 539         FAIL("deadlock");
 540     }
 541     PASS();
 542 }
 543
 544
 545
 546 //-----------------------------------------------------------------------------
 547
 548 int
 549 main(int argc, char** argv)
 550 {
 551     if (1 < argc) {
 552         // XXX can we run w/o scoped XPCOM?
 553         const char* test = argv[1];
 554         ScopedXPCOM xpcom(test);
 555         if (xpcom.failed())
 556             return 1;
 557
 558         // running in a spawned process.  call the specificed child function.
 559         if (!strcmp("Sanity", test))
 560             return Sanity_Child();
 561         if (!strcmp("Sanity2", test))
 562             return Sanity2_Child();
 563         if (!strcmp("Sanity3", test))
 564             return Sanity3_Child();
 565         if (!strcmp("Sanity4", test))
 566             return Sanity4_Child();
 567
 568         if (!strcmp("TwoThreads", test))
 569             return TwoThreads_Child();
 570         if (!strcmp("ContentionNoDeadlock", test))
 571             return ContentionNoDeadlock_Child();
 572
 573         FAIL("unknown child test");
 574     }
 575
 576     ScopedXPCOM xpcom("Deadlock detector correctness");
 577     if (xpcom.failed())
 578         return 1;
 579
 580     // in the first invocation of this process.  we will be the "driver".
 581     int rv = 0;
 582
 583     sPathToThisBinary = argv[0];
 584
 585     if (NS_FAILED(Sanity()))
 586         rv = 1;
 587     if (NS_FAILED(Sanity2()))
 588         rv = 1;
 589     if (NS_FAILED(Sanity3()))
 590         rv = 1;
 591     if (NS_FAILED(Sanity4()))
 592         rv = 1;
 593
 594     if (NS_FAILED(TwoThreads()))
 595         rv = 1;
 596     if (NS_FAILED(ContentionNoDeadlock()))
 597         rv = 1;
 598
 599     return rv;
 600 }