Identify the hung thread using the Wait Chain Traversal API

base/win/wait_chain_unittest.cc

Index: base/win/wait_chain_unittest.cc
diff --git a/base/win/wait_chain_unittest.cc b/base/win/wait_chain_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..d6684d5d426e4163a474c1a54e64637df84453ba
--- /dev/null
+++ b/base/win/wait_chain_unittest.cc
@@ -0,0 +1,294 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/win/wait_chain.h"
+
+#include <string>
+
+#include "base/bind.h"
+#include "base/command_line.h"
+#include "base/strings/string_number_conversions.h"
+#include "base/test/multiprocess_test.h"
+#include "base/threading/simple_thread.h"
+#include "base/win/win_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "testing/multiprocess_func_list.h"
+
+namespace base {
+namespace win {
+
+namespace {
+
+// Appends |handle| as a command line switch.
+void AppendSwitchHandle(base::CommandLine* command_line,
+                        std::string switch_name,
+                        HANDLE handle) {
+  command_line->AppendSwitchASCII(
+      switch_name, base::UintToString(base::win::HandleToUint32(handle)));
+}
+
+// Retrieves the |handle| associated to |switch_name| from the command line.
+ScopedHandle GetSwitchValueHandle(base::CommandLine* command_line,
+                                  std::string switch_name) {

[Sigurður Ásgeirsson, 2016/04/05 20:07:01]

nit: StringPiece here avoids string construction and copying.

[Patrick Monette, 2016/04/05 22:55:31]

Unfortunatly AppendSwitchASCII takes in a std::string. Maybe someone (not me!)
will change it in the future! Changed it to StringPiece to help an eventual
transition.

[Sigurður Ásgeirsson, 2016/04/06 14:57:46]

Ah, that sucks.

+  std::string switch_string = command_line->GetSwitchValueASCII(switch_name);
+  unsigned int switch_uint = 0;
+  if (switch_string.empty() ||
+      !base::StringToUint(switch_string, &switch_uint)) {
+    DLOG(ERROR) << "Missing or invalid " << switch_name << " argument.";
+    return ScopedHandle();
+  }
+  return ScopedHandle(reinterpret_cast<HANDLE>(switch_uint));
+}
+
+// Helper function to create a mutex.
+ScopedHandle CreateMutex(bool inheritable) {
+  SECURITY_ATTRIBUTES security_attributes = {sizeof(SECURITY_ATTRIBUTES),
+                                             nullptr, inheritable};
+  return ScopedHandle(::CreateMutex(&security_attributes, FALSE, NULL));
+}
+
+// Helper function to create an event.
+ScopedHandle CreateEvent(bool inheritable) {
+  SECURITY_ATTRIBUTES security_attributes = {sizeof(SECURITY_ATTRIBUTES),
+                                             nullptr, inheritable};
+  return ScopedHandle(
+      ::CreateEvent(&security_attributes, FALSE, FALSE, nullptr));
+}
+
+class SimpleThreadWithHandle : public SimpleThread {
+ public:
+  explicit SimpleThreadWithHandle(const std::string& name_prefix)
+      : SimpleThread(name_prefix) {}
+
+  // Returns a handle to the thread so that other threads can wait on it.
+  HANDLE get_thread_handle() {
+    if (!thread_handle_.Get()) {
+      thread_handle_.Set(
+          ::OpenThread(SYNCHRONIZE | THREAD_TERMINATE, FALSE, tid()));
+    }
+    return thread_handle_.Get();
+  }
+
+ private:
+  ScopedHandle thread_handle_;
+
+  DISALLOW_COPY_AND_ASSIGN(SimpleThreadWithHandle);
+};
+
+// Helper thread class that runs the callback then stops.
+class SingleTaskThread : public SimpleThreadWithHandle {
+ public:
+  explicit SingleTaskThread(const Closure& task)
+      : SimpleThreadWithHandle("WaitChainTest SingleTaskThread"), task_(task) {}
+
+  void Run() override { task_.Run(); }
+
+ private:
+  Closure task_;
+
+  DISALLOW_COPY_AND_ASSIGN(SingleTaskThread);
+};
+
+// Helper thread to cause a deadlock by acquiring 2 mutex in a given order.

[Sigurður Ásgeirsson, 2016/04/05 20:07:01]

nit: mutexes?

[Patrick Monette, 2016/04/05 22:55:31]

Done.

+class DeadlockThread : public SimpleThreadWithHandle {
+ public:
+  DeadlockThread(HANDLE mutex_1, HANDLE mutex_2)
+      : SimpleThreadWithHandle("WaitChainTest SingleTaskThread"),
+        wait_event_(CreateEvent(false)),
+        mutex_acquired_event_(CreateEvent(false)),
+        mutex_1_(mutex_1),
+        mutex_2_(mutex_2) {}
+
+  void Run() override {
+    // Acquire the mutex then signal the main thread.
+    EXPECT_EQ(WAIT_OBJECT_0, ::WaitForSingleObject(mutex_1_, INFINITE));
+    EXPECT_TRUE(::SetEvent(mutex_acquired_event_.Get()));
+
+    // Wait until both thread are holding their mutex before trying to acquire

[Sigurður Ásgeirsson, 2016/04/05 20:07:01]

nit: both threads

[Patrick Monette, 2016/04/05 22:55:31]

Done.

+    // the other one.
+    EXPECT_EQ(WAIT_OBJECT_0,
+              ::WaitForSingleObject(wait_event_.Get(), INFINITE));
+
+    // To unblock the deadlock, one of the thread will get terminated (via

[Sigurður Ásgeirsson, 2016/04/05 20:07:01]

nit: thread->threads

[Patrick Monette, 2016/04/05 22:55:31]

Done.

+    // TerminateThread()) without releasing the mutex. This causes the other
+    // thread to wake up with WAIT_ABANDONED.
+    EXPECT_EQ(WAIT_ABANDONED, ::WaitForSingleObject(mutex_2_, INFINITE));
+  }
+
+  // Blocks until a mutex is acquired.
+  void WaitForMutexAcquired() {
+    EXPECT_EQ(WAIT_OBJECT_0,
+              ::WaitForSingleObject(mutex_acquired_event_.Get(), INFINITE));
+  }
+
+  // Signal the thread to acquire the second mutex.
+  void SignalToAcquireMutex() { EXPECT_TRUE(::SetEvent(wait_event_.Get())); }
+
+ private:
+  ScopedHandle wait_event_;
+  ScopedHandle mutex_acquired_event_;
+
+  // The 2 mutex to acquire.
+  HANDLE mutex_1_;
+  HANDLE mutex_2_;
+
+  DISALLOW_COPY_AND_ASSIGN(DeadlockThread);
+};
+
+// Creates a thread that calls WaitForSingleObject() on the handle and then
+// terminates when it unblocks.
+scoped_ptr<SingleTaskThread> CreateWaitingThread(HANDLE handle) {
+  scoped_ptr<SingleTaskThread> thread(new SingleTaskThread(
+      Bind(base::IgnoreResult(&::WaitForSingleObject), handle, INFINITE)));
+  thread->Start();
+
+  return std::move(thread);
+}
+
+// Creates a thread that calls WaitForSingleObject() on the handle and then
+// terminates when it unblocks.
+scoped_ptr<DeadlockThread> CreateDeadlockThread(HANDLE mutex_1,
+                                                HANDLE mutex_2) {
+  scoped_ptr<DeadlockThread> thread(new DeadlockThread(mutex_1, mutex_2));
+  thread->Start();
+
+  // Wait until the first mutex is acquired before returning.
+  thread->WaitForMutexAcquired();
+
+  return std::move(thread);
+}
+
+// Child process to test the cross-process capability of the WCT api.
+// This process will simulate a hang while holding a mutex that the parent
+// process is waiting on.
+MULTIPROCESS_TEST_MAIN(WaitChainTestProc) {
+  base::CommandLine* command_line = base::CommandLine::ForCurrentProcess();
+
+  ScopedHandle mutex = GetSwitchValueHandle(command_line, "mutex");
+  CHECK(mutex.IsValid());
+
+  ScopedHandle sync_event(GetSwitchValueHandle(command_line, "sync_event"));
+  CHECK(sync_event.IsValid());
+
+  // Acquire mutex.
+  CHECK(::WaitForSingleObject(mutex.Get(), INFINITE) == WAIT_OBJECT_0);
+
+  // Signal back to the parent process that the mutex is hold.
+  CHECK(::SetEvent(sync_event.Get()));
+
+  // Wait on a signal from the parent process before terminating.
+  CHECK(::WaitForSingleObject(sync_event.Get(), INFINITE) == WAIT_OBJECT_0);
+
+  return 0;
+}
+
+// Start a child process and passes the |mutex| and the |sync_event| to the
+// command line.
+base::Process StartChildProcess(HANDLE mutex, HANDLE sync_event) {
+  CommandLine command_line = GetMultiProcessTestChildBaseCommandLine();
+
+  AppendSwitchHandle(&command_line, "mutex", mutex);
+  AppendSwitchHandle(&command_line, "sync_event", sync_event);
+
+  LaunchOptions options;
+  options.inherit_handles = true;

[Sigurður Ásgeirsson, 2016/04/05 20:07:02]

nit: use the handle inheritance vector:
https://code.google.com/p/chromium/codesearch#chromium/src/base/process/launc...

[Patrick Monette, 2016/04/05 22:55:31]

Huh, interesting. Done.

+  return SpawnMultiProcessTestChild("WaitChainTestProc", command_line, options);
+}
+
+// Returns true if the |wait_chain| goes through more than 1 process.
+bool WaitChainIsCrossProcess(const WaitChain& wait_chain) {
+  if (wait_chain.size() == 0)
+    return false;
+
+  // Just check that the process id changes somewhere in the chain.
+  // Note: ThreadObjects are every 2 nodes.
+  DWORD first_process = wait_chain[0].ThreadObject.ProcessId;
+  for (size_t i = 2; i < wait_chain.size(); i += 2) {
+    if (first_process != wait_chain[i].ThreadObject.ProcessId)

[Sigurður Ásgeirsson, 2016/04/05 20:07:01]

nit: EXPECT that the node type is as expected?
maybe also EXPECT that the odd nodes are of the complementary (non-thread) type?

[Patrick Monette, 2016/04/05 22:55:31]

Done.

+      return true;
+  }
+  return false;
+}
+
+}  // namespace
+
+// Creates 2 threads that acquire their designated mutex and then try to

[Sigurður Ásgeirsson, 2016/04/05 20:07:01]

love the quick description!

[Patrick Monette, 2016/04/05 22:55:31]

:)

+// acquire each others' mutex to cause a deadlock.
+TEST(WaitChainTest, Deadlock) {
+  // 2 mutexes are needed to get a deadlock.
+  ScopedHandle mutex_1 = CreateMutex(false);
+  ASSERT_TRUE(mutex_1.IsValid());
+  ScopedHandle mutex_2 = CreateMutex(false);
+  ASSERT_TRUE(mutex_2.IsValid());
+
+  scoped_ptr<DeadlockThread> deadlock_thread_1 =
+      CreateDeadlockThread(mutex_1.Get(), mutex_2.Get());
+  scoped_ptr<DeadlockThread> deadlock_thread_2 =
+      CreateDeadlockThread(mutex_2.Get(), mutex_1.Get());
+
+  // Signal the threads to try to acquire the other mutex.
+  deadlock_thread_1->SignalToAcquireMutex();
+  deadlock_thread_2->SignalToAcquireMutex();
+  // Sleep to make sure the 2 threads got a chance to execute.
+  Sleep(10);
+
+  // Create a few waiting threads to get a longer wait chain.
+  scoped_ptr<SingleTaskThread> waiting_thread_1 =
+      CreateWaitingThread(deadlock_thread_1->get_thread_handle());
+  scoped_ptr<SingleTaskThread> waiting_thread_2 =
+      CreateWaitingThread(waiting_thread_1->get_thread_handle());
+
+  WaitChain wait_chain;
+  bool is_deadlock;
+  ASSERT_TRUE(
+      GetThreadWaitChain(waiting_thread_2->tid(), &wait_chain, &is_deadlock));
+
+  EXPECT_EQ(9, wait_chain.size());
+  EXPECT_TRUE(is_deadlock);
+  EXPECT_FALSE(WaitChainIsCrossProcess(wait_chain));
+
+  ASSERT_TRUE(::TerminateThread(deadlock_thread_1->get_thread_handle(), 0));
+}
+
+// Creates a child process that acquire a mutex and then blocks. A chain of

[Sigurður Ásgeirsson, 2016/04/05 20:07:01]

nit: acquires

[Patrick Monette, 2016/04/05 22:55:31]

Done.

+// threads then blocks on that mutex.
+TEST(WaitChainTest, CrossProcess) {
+  ScopedHandle mutex = CreateMutex(true);
+  ASSERT_TRUE(mutex.IsValid());
+  ScopedHandle sync_event = CreateEvent(true);
+  ASSERT_TRUE(sync_event.IsValid());
+
+  base::Process child_process =
+      StartChildProcess(mutex.Get(), sync_event.Get());
+  ASSERT_TRUE(child_process.IsValid());
+
+  // Wait for the child process to signal when it's holding the mutex.
+  EXPECT_EQ(WAIT_OBJECT_0, ::WaitForSingleObject(sync_event.Get(), INFINITE));
+
+  ::TerminateProcess(child_process.Handle(), 0);

[Sigurður Ásgeirsson, 2016/04/05 20:07:02]

this looks out of place?

[Patrick Monette, 2016/04/05 22:55:31]

Oops! It is!

+
+  // Create a few waiting threads to get a longer wait chain.
+  scoped_ptr<SingleTaskThread> waiting_thread_1 =
+      CreateWaitingThread(mutex.Get());
+  scoped_ptr<SingleTaskThread> waiting_thread_2 =
+      CreateWaitingThread(waiting_thread_1->get_thread_handle());
+  scoped_ptr<SingleTaskThread> waiting_thread_3 =
+      CreateWaitingThread(waiting_thread_2->get_thread_handle());
+
+  WaitChain wait_chain;
+  bool is_deadlock;
+  ASSERT_TRUE(
+      GetThreadWaitChain(waiting_thread_3->tid(), &wait_chain, &is_deadlock));
+
+  EXPECT_EQ(7, wait_chain.size());
+  EXPECT_FALSE(is_deadlock);
+  EXPECT_TRUE(WaitChainIsCrossProcess(wait_chain));
+
+  // Unblock child process and wait for it to terminate.
+  ASSERT_TRUE(::SetEvent(sync_event.Get()));
+  ASSERT_TRUE(child_process.WaitForExit(nullptr));
+}
+
+}  // namespace win
+}  // namespace base