TaskScheduler [2/9] Scheduler Lock

base/task_scheduler/scheduler_lock_unittest.cc

+// 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/task_scheduler/scheduler_lock.h"
+
+#include <stdlib.h>
+
+#include "base/compiler_specific.h"
+#include "base/macros.h"
+#include "base/synchronization/waitable_event.h"
+#include "base/threading/platform_thread.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+namespace internal {
+
+class BasicLockTestThread : public PlatformThread::Delegate {

[gab, 2016/02/19 16:08:04]

Meta comment on what this does.

[robliao, 2016/02/19 21:25:07]

Done.

+ public:
+  explicit BasicLockTestThread(SchedulerLock* lock)
+      : lock_(lock),
+        acquired_(0) {}
+
+  void ThreadMain() override {
+    for (int i = 0; i < 10; i++) {
+      lock_->Acquire();
+      acquired_++;
+      lock_->Release();
+    }
+    for (int i = 0; i < 10; i++) {
+      lock_->Acquire();
+      acquired_++;
+      PlatformThread::Sleep(TimeDelta::FromMilliseconds(rand() % 20));

[gab, 2016/02/19 16:08:04]

Use base/rand_util.h instead of stdlib's rand()

[robliao, 2016/02/19 21:25:07]

Done.

+      lock_->Release();
+    }
+  }
+
+  int acquired() const { return acquired_; }
+
+ private:
+  SchedulerLock* const lock_;
+  int acquired_;
+
+  DISALLOW_COPY_AND_ASSIGN(BasicLockTestThread);
+};
+
+class BasicLockAcquireAndWaitThread : public PlatformThread::Delegate {
+ public:
+  explicit BasicLockAcquireAndWaitThread(SchedulerLock* lock)
+      : lock_(lock),
+        lock_acquire_event_(false, false),
+        main_thread_continue_event_(false, false) {}
+
+  void ThreadMain() override {
+    lock_->Acquire();
+    lock_acquire_event_.Signal();
+    main_thread_continue_event_.Wait();
+    lock_->Release();
+  }
+
+  void WaitForLockAcquition() {

[gab, 2016/02/19 16:08:03]

WaitForLockAcquisition
                ^

[robliao, 2016/02/19 21:25:06]

Done.

+    lock_acquire_event_.Wait();
+  }
+
+  void ContinueMain() {
+    main_thread_continue_event_.Signal();
+  }
+
+ private:
+  SchedulerLock* const lock_;
+  WaitableEvent lock_acquire_event_;
+  WaitableEvent main_thread_continue_event_;
+};

[gab, 2016/02/19 16:08:03]

DISALLOW_COPY_AND_ASSIGN

[robliao, 2016/02/19 21:25:07]

Done.

+
+TEST(TaskSchedulerLock, Basic) {
+  SchedulerLock lock;
+  BasicLockTestThread thread(&lock);
+  PlatformThreadHandle handle;
+
+  ASSERT_TRUE(PlatformThread::Create(0, &thread, &handle));
+
+  int acquired = 0;
+  for (int i = 0; i < 5; i++) {
+    lock.Acquire();
+    acquired++;
+    lock.Release();
+  }
+  for (int i = 0; i < 10; i++) {
+    lock.Acquire();
+    acquired++;
+    PlatformThread::Sleep(TimeDelta::FromMilliseconds(rand() % 20));
+    lock.Release();
+  }
+  for (int i = 0; i < 5; i++) {
+    lock.Acquire();
+    acquired++;
+    PlatformThread::Sleep(TimeDelta::FromMilliseconds(rand() % 20));
+    lock.Release();
+  }
+
+  PlatformThread::Join(handle);
+
+  EXPECT_GE(acquired, 20);
+  EXPECT_GE(thread.acquired(), 20);

[gab, 2016/02/19 16:08:03]

Why GE and not EQ? (if EQ, put constant on LHS, per the macros's (expected,
actual) definition)

[robliao, 2016/02/19 21:25:07]

The original lock test had a try, so there was a case where this would fail. We
don't have try, so now updated to EQ.

+}
+
+TEST(TaskSchedulerLock, AcquirePredecessor) {
+  SchedulerLock lock_predecessor;
+  SchedulerLock lock(&lock_predecessor);
+  lock_predecessor.Acquire();
+  lock.Acquire();
+  lock.Release();
+  lock_predecessor.Release();
+}
+
+TEST(TaskSchedulerLock, AcquireNonPredecessor) {
+  SchedulerLock lock_predecessor;

[gab, 2016/02/19 16:08:03]

s/lock_predecessor/other_lock/ (since it's not actually a predecessor?)

[robliao, 2016/02/19 21:25:06]

Changed to lock1 and lock2 to match below.

+  SchedulerLock lock;
+  EXPECT_DEBUG_DEATH({

[gab, 2016/02/19 16:08:03]

Cool :-)!! Didn't know about EXPECT_DEBUG_DEATH!

But it seems to be defined based on NDEBUG [1], so won't it fail in Release
builds with dcheck_always_on?

Perhaps we'll need some kind of include trick like:

#if DCHECK_IS_ON() && defined(NDEBUG)
// EXPECT_DEBUG_DEATH macros are defined based on NDEBUG, but they should
// trigger as well in DCHECK_ALWAYS_ON Release builds.
#undef NDEBUG
#include "testing/gtest/include/gtest/gtest.h"
#define NDEBUG
#else  // defined(DCHECK_ALWAYS_ON) && defined(NDEBUG)
#include "testing/gtest/include/gtest/gtest.h"
#endif  // defined(DCHECK_ALWAYS_ON) && defined(NDEBUG)


[1]
https://code.google.com/p/chromium/codesearch#chromium/src/testing/gtest/incl...

[robliao, 2016/02/19 21:25:06]

Turns out Release builds for tests don't have DCHECKs! Toss in a DCHECK(false)
and it doesn't trigger.

[gab, 2016/02/19 22:05:24]

Hmmm okay (they probably should and I remember a discussion that someone wanted
to add them). Either way we need to support it (my dev build is
Release+dcheck_always_on).

[robliao, 2016/02/19 23:51:11]

The right fix would be to update the EXPECT_DEBUG_DEATH or introduce
EXPECT_DCHECK_DEATH.

+    lock_predecessor.Acquire();
+    lock.Acquire();
+    lock_predecessor.Release();
+  }, "");
+}
+
+TEST(TaskSchedulerLock, AcquireMultipleLocksInOrder) {
+  SchedulerLock lock1;
+  SchedulerLock lock2(&lock1);
+  SchedulerLock lock3(&lock2);
+  lock1.Acquire();
+  lock2.Acquire();
+  lock3.Acquire();
+  lock3.Release();
+  lock2.Release();
+  lock1.Release();
+}
+
+TEST(TaskSchedulerLock, AcquireMultipleLocksInTheMiddleOfAChain) {
+  SchedulerLock lock1;
+  SchedulerLock lock2(&lock1);
+  SchedulerLock lock3(&lock2);
+  lock2.Acquire();
+  lock3.Acquire();
+  lock3.Release();
+  lock2.Release();
+}
+
+TEST(TaskSchedulerLock, AcquireMultipleLocksOutOfOrder) {
+  SchedulerLock lock1;
+  SchedulerLock lock2(&lock1);
+  SchedulerLock lock3(&lock2);

[gab, 2016/02/19 16:08:03]

Looks like this test only needs two locks. Let's keep each test to the minimal
state required.

[robliao, 2016/02/19 21:25:06]

This is actually a little different from AcquireNonPredecessor, which is the two
lock case.
This tests to make sure that you don't automatically get lock1 by transitivity.

Renamed the test

[gab, 2016/02/19 22:05:24]

Ah I see then I think we also need an "out-of-order" test (i.e. lock1,
lock2(&lock1), acquire(lock2), acquire(lock1), explode).

[robliao, 2016/02/19 23:51:11]

Done.

+  EXPECT_DEBUG_DEATH({
+    lock1.Acquire();
+    lock3.Acquire();

[gab, 2016/02/19 16:08:04]

I'd prefer if this was the last statement in the EXPECT_DEBUG_DEATH scope as
it's otherwise unclear that this is the one expected to cause the failure.

[robliao, 2016/02/19 21:25:06]

Done.

+    lock1.Release();

[gab, 2016/02/19 16:08:03]

In non-dcheck builds you have to Release lock3 or undefined behaviour ensues
(deleting an owned CRITICAL_SECTION is undefined [1] and a pthread_mutex will
fail [2]).

So how about taking this out into:

#if !DCHECK_IS_ON()
lock3.Release();
#endif
lock1.Release();

[1]
https://msdn.microsoft.com/en-us/library/windows/desktop/ms682552(v=vs.85).aspx

[2]
http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_destro...

[robliao, 2016/02/19 21:25:07]

Turns out, this is okay due to forking on non-Windows platforms.
On Windows platforms, a whole new process gets spun up and the specific test is
reexecuted with some special flags (filter to this test, pass a death test
flag).

So in this process, the body of EXPECT_DEBUG_DEATH never happens.

This also explains why the older form of the test worked on Windows as the
entire test was rerun instead of forking at this point.

https://code.google.com/p/chromium/codesearch#chromium/src/testing/gtest/src/...

+  }, "");
+}
+
+TEST(TaskSchedulerLock, AcquireLocksDifferentThreadsSafely) {
+  SchedulerLock lock1;
+  SchedulerLock lock2;
+  BasicLockAcquireAndWaitThread thread(&lock1);
+  PlatformThreadHandle handle;
+  ASSERT_TRUE(PlatformThread::Create(0, &thread, &handle));
+
+  lock2.Acquire();
+  thread.WaitForLockAcquition();
+  thread.ContinueMain();
+  lock2.Release();
+  PlatformThread::Join(handle);
+}
+
+TEST(TaskSchedulerLock, AcquireLocksWithPredecessorDifferentThreadsSafely) {
+  SchedulerLock lock1;
+  SchedulerLock lock2(&lock1);
+  BasicLockAcquireAndWaitThread thread(&lock1);
+  PlatformThreadHandle handle;
+  ASSERT_TRUE(PlatformThread::Create(0, &thread, &handle));
+

[gab, 2016/02/19 16:08:03]

Think we also need
thread.ContinueAcquireLock();
to tell the thread when it should try to acquire the lock.

i.e. the real test here is that we can grab lock2 before lock1 iff lock2 is not
obtained on the same thread at lock1.

Suggest adding a comment here like:

// TaskSchedulerLock.AcquireMultipleLocksOutOfOrder verified that
// lock2 couldn't be obtained before lock1 on the same thread, but
// it should be okay on different threads.

[robliao, 2016/02/19 21:25:06]

Clarified the test and added explicit locking order. We can approximate
ContinueAcquireLock by waiting on when we create the thread.

+  lock2.Acquire();
+  thread.WaitForLockAcquition();
+  thread.ContinueMain();
+  lock2.Release();
+  PlatformThread::Join(handle);
+}
+
+TEST(TaskSchedulerLock, SelfReferentialLock) {
+  struct SelfReferentialLock {
+    SelfReferentialLock() : lock(&lock) {}
+
+    SchedulerLock lock;
+  };
+
+  EXPECT_DEBUG_DEATH({ SelfReferentialLock lock; }, "");
+}
+
+TEST(TaskSchedulerLock, PredecessorCycle) {
+  struct LockCycle {
+    LockCycle() : lock1(&lock2), lock2(&lock1) {}
+
+    SchedulerLock lock1;
+    SchedulerLock lock2;
+  };
+
+  EXPECT_DEBUG_DEATH({ LockCycle cycle; }, "");
+}
+

[gab, 2016/02/19 16:08:04]

Ah interesting :-), thought taking predecessor as constructor prevented cycles
altogether but I guess it's possible this way. Looks like silly code, but no
harm testing for it since it's only DCHECK code.

With that in mind I think we should also test non-immediate cycles (i.e. more
than 2 elements) as those are probably more likely (hope nobody would
intentionally write the above two... though I guess they could occur by typo or
something).

[robliao, 2016/02/19 21:25:07]

Done.

+}  // namespace internal
+}  // base